Recent Updates Page 36 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:40 am on 31 March 2022 Permalink | Reply
    Tags:   

    Teaser 2867: Clumsy Meg 

    From The Sunday Times, 3rd September 2017 [link] [link]

    I arranged cards labelled ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE and TEN equally-spaced around the perimeter of a circular table. The arrangement was such that any two adjacent cards had exactly one letter in common.

    That evening Meg entered the room and accidentally knocked two adjacent cards onto the floor. In her haste to put things right, she inadvertently put the two cards back the wrong way round. Surprisingly, the one-letter property still applied.

    What were the two numbers directly opposite the two that she knocked on the floor?

    [teaser2867]

     
    • Jim Randell's avatar

      Jim Randell 8:41 am on 31 March 2022 Permalink | Reply

      I took “exactly one letter in common” to mean that there was exactly one letter of the alphabet that appeared in both words, but the letter may be repeated in one (or both) of the words.

      The following Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (subsets, intersect, ordered, update, tuples, join, printf)

# available words
words = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN')

# find words that share exactly one letter
S1 = set(ordered(*ws) for ws in subsets(words, size=2) if len(intersect(ws)) == 1)

# check two words share exactly one letter
check = lambda *ws: ordered(*ws) in S1

# generate a ring of words such that adjacent items share exactly one letter
def generate(s, ws):
  sz = s[-1]
  # are we done?
  if not ws:
    # check closure and eliminate duplicates
    if check(sz, s[0]) and s[1] < sz:
      yield s
  else:
    # extend the ring
    for (i, w) in enumerate(ws):
      if check(sz, w):
        yield from generate(s + [w], ws[:i] + ws[i + 1:])

# solve the puzzle starting with the first word
for s in generate([words[0]], words[1:]):
  # find two adjacent words that can be swapped
  for (i, w) in enumerate(s):
    if i == len(s) - 1: break
    s2 = update(s, (i + 1, i), s[i:i + 2])
    if all(check(a, b) for (a, b) in tuples(s2, 2, circular=1)):
      # the numbers opposite the swapped pair
      r = (s2[(i + 5) % 10], s2[(i + 6) % 10])
      fmt = lambda x: join(x, sep=" ", enc="()")
      printf("{r}; {s} -> {s2}", r=fmt(r), s=fmt(s), s2=fmt(s2))

      Solution: The two numbers are: SEVEN and EIGHT.

      One scenario is that the cards were initially laid out:

      ONE (O) FOUR (F) FIVE (E) TEN (T) TWO (T) EIGHT (E) SEVEN (S) SIX (I) NINE (E) THREE (E) [ONE]

      And the ONE and FOUR cards were swapped over to give

      FOUR (O) ONE (E) FIVE (E) TEN (T) TWO (T) EIGHT (E) SEVEN (S) SIX (I) NINE (E) THREE (R) [FOUR]

      Or we started with the second set and swapped ONE and FOUR to get the first set.

      Like

  • Unknown's avatar

    Jim Randell 8:47 am on 29 March 2022 Permalink | Reply
    Tags:   

    Teaser 2852: When in Rome 

    From The Sunday Times, 21st May 2017 [link] [link]

    An ancient five-by-five table of letters been found in Rome. All the ten different five-letter rows across and five-letter columns down are Roman numerals, with no letter exceeding a C. The across numbers are, in order, even, even, a cube, a prime, and a power of 2. The down numbers include a cube, the rest being even or prime.

    Which two Roman numerals cross at the middle square?

    [teaser2852]

     
    • Jim Randell's avatar

      Jim Randell 8:47 am on 29 March 2022 Permalink | Reply

      This Python program constructs candidate values for the rows and the columns, and then fills out the rows, ensuring there are always available candidates for the columns.

      Once the grid is filled out the columns are checked to ensure they meet the puzzle requirements.

      It runs in 61ms.

      from enigma import (irange, inf, cb, Primes, int2roman, union, unpack, update, delete, join, match, roman2int, printf)

# max number
N = 399

# 5-digit roman numerals, map: int -> roman
rom5 = dict()
for n in irange(1, N):
  r = int2roman(n)
  if len(r) != 5: continue
  assert not ('M' in r or 'D' in r)
  rom5[n] = r

# generate roman numerals from function f
def romans(f, a=1):
  for i in irange(a, inf):
    n = f(i)
    if n > N: break
    r = rom5.get(n)
    if r: yield r

# categorise the roman numerals into sets
evens = set(v for (k, v) in rom5.items() if k % 2 == 0)
cubes = set(romans(cb))
ps = Primes(N + 1)
primes = set(v for (k, v) in rom5.items() if k in ps)
pow2s = set(romans(lambda n: 2**n))

# row/column candidates
rcs = [evens, evens, cubes, primes, pow2s]
ccs = [union([cubes, evens, primes])] * 5

# return column candidates for rows rs
def col_cand(rs, ccs):
  ccs_ = list()
  # consider each column
  for (j, t) in enumerate(zip(*rs)):
    # make the template
    t = join(t)
    cs = list(x for x in ccs[j] if match(x, t))
    if not cs: return
    ccs_.append(cs)
  return ccs_

# fill out the grid (rows), respecting row/col candidates
# rs = partially completed grid (rows)
# rcs = row candidates; map <index> -> <candidates>
# ccs = col candidates
def solve(rs, rcs, ccs):
  # are we done?
  if not rcs:
    yield rs
  else:
    # choose a row
    (k, vs) = min(rcs.items(), key=unpack(lambda k, vs: len(vs)))
    # choose a value
    for v in vs:
      rs_ = update(rs, [k], [v])
      # check columns in the new grid match
      cs_ = col_cand(rs_, ccs)
      if cs_:
        # solve for the remaining rows
        yield from solve(rs_, delete(rcs, [k]), cs_)

# initial grid
g = ['?????'] * 5
for rs in solve(g, dict(enumerate(rcs)), ccs):
  cs = list(map(join, zip(*rs)))
  # rows and columns are all different
  if len(union([rs, cs])) != 10: continue
  # check the columns: exactly 1 is a cube, the others are even or prime
  cbs = set()
  eps = set()
  for (i, x) in enumerate(cs):
    if x in cubes: cbs.add(i)
    if x in primes or x in evens: eps.add(i)
  if not (len(cbs) == 1 and len(eps) == 4 and (not cbs.issubset(eps))): continue
  # output solution
  for (t, vs) in zip(['rows', 'cols'], (rs, cs)):
    fmt = lambda vs: join(vs, sep=" | ", enc=("[ ", " ]"))
    printf("{t}: {vs} = {ns}", vs=fmt(vs), ns=tuple(roman2int(v) for v in vs))
  printf()

      Solution: The middle row is CCXVI (216). The middle column is LXXIX (79).

      The completed grid looks like this:

      Like

    • Jim Olson's avatar

      Jim Olson 6:30 pm on 29 March 2022 Permalink | Reply

      Typo on the last column. Should be “23” which is still a prime number.

      Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 25 March 2022 Permalink | Reply
    Tags: ,   

    Teaser 3105: Roman primes 

    From The Sunday Times, 27th March 2022 [link] [link]

    Romulus played a game using several identical six-sided dice. Each die face shows a different single-character Roman numeral. He rolled two dice and was able to form a prime number in Roman numerals by arranging the two characters. Romulus rolled more dice and, after each roll, formed a prime number with one more character, rearranging the sequence as needed, until he could no longer form a prime number less than 100. He was using standard notation where a character before another that is 5 or 10 times larger is subtracted from the larger one, e.g., IX = 9.

    After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.

    In decimal notation and in ascending order, what were those prime numbers?

    I found two different scenarios that fit the puzzle text, but lead to two different answers. So I have marked the puzzle as flawed.

    [teaser3105]

     
    • Jim Randell's avatar

      Jim Randell 5:28 pm on 25 March 2022 Permalink | Reply

      To represent numbers from 1 to 99 using Roman numerals requires five characters I, V, X, L, C. So we know those must be on the dice. The other symbol is probably D (= 500), which lets us express numbers up to 899 (with sufficient dice; it takes 12 to make 888 = DCCCLXXXVIII).

      I’m assuming that Romulus rolls 2 dice, arranges them to make the first prime in the sequence. Then rolls another single die, and arranges the 3 dice (without changing the numerals shown by the first two) to make the second prime, and so on. Rolling a single new die at each step until he is unable to rearrange the dice to make a prime, or he runs out of dice.

      Then we can find a scenario where there are three primes that cannot occur in any sequence.

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (primes, int2roman, group, join, multiset, printf)

# primes less than 100
prms = list(primes.between(2, 99))

# record primes by their roman numeral content
d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))

# find length n extensions of ks in d
def extend(d, ks, n):
  ss = list(multiset.from_seq(k) for k in ks)
  for k in d.keys():
    if len(k) == n:
      s = multiset.from_seq(k)
      if any(s.issuperset(s_) for s_ in ss):
        yield k
  
# generate possible throws with increasing lengths
def generate(d, n=2):
  # start with length n sequences
  ks = list(k for k in d.keys() if len(k) == n)
  while ks:
    yield (n, ks)
    # find keys that are one longer
    n += 1
    ks = list(extend(d, ks, n))

# start with the complete set of primes
ps = set(prms)
for (n, ks) in generate(d, 2):
  # and remove those reachable after n dice
  for k in ks:
    ps.difference_update(d[k])
  # we have a solution if there are 3 primes remaining
  if len(ps) == 3:
    printf("{n} dice -> {ps}", ps=sorted(ps))

      Solution: The prime numbers are: 5, 37, 83.

      This is the solution in the scenario where Romulus has 6 dice, with the symbols I, V, X, L, C, and one other.

      5 (= V) only requires 1 die, so cannot be constructed using 2-6 dice.

      83 (= LXXXIII) requires 7 dice, so cannot be constructed using 2-6 dice.

      37 (= XXXVII) can be constructed using 6 dice, but there is no predecessor prime using 5 dice.

      Possible predecessor numbers for 37 are: 27, 32, 34, 46. None of which are prime.

      However I was able to find another scenario (see below), where Romulus has more than 6 dice, with the symbols I, V, X, L, and two others, that do not include C.

      In this scenario 5 and 37 cannot be constructed (as above), but 83 can be constructed using 7 dice.

      However the standard representation of 97 in Roman numerals is XCVII, which cannot be constructed if the symbol C is not available. (In fact none of the numbers in [90, 499] can be constructed with these dice).

      So the solution in this scenario is: 5, 37, 97.

      It seems that this second scenario is what the setter had in mind (it is the published answer), although it seems less plausible to me.

      Perhaps the following would have been a better representation of the intended puzzle:

      Romulus found a box containing a large number of identical six-sided dice. Each die face shows a different Latin character, and Romulus found that when he rolled some of the dice he was sometimes able to rearrange them so that the top faces formed a Roman numeral (using standard notation).

      He played a game where he rolled two dice and was able to form a prime number by arranging the two characters. He then rolled another die and was able to arrange the three dice to form another prime number. He carried on rolling extra dice (one die each time), until he could no longer arrange the dice to form a prime number less than 100.

      After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.

      In decimal notation and in ascending order, what were those prime numbers?

      The published solution is: “5, 37 and 97”.

      Like

    • Robert Brown's avatar

      Robert Brown 7:39 am on 26 March 2022 Permalink | Reply

      When the text says ‘after many games’ I assumed that some of these would start with II (=2) and some with XI (=11). Clearly cannot find 5 (V) as it is length 1, but I only have one more prime which cannot be made with one of the two starting pairs.

      Like

      • Jim Randell's avatar

        Jim Randell 8:57 am on 26 March 2022 Permalink | Reply

        @Robert: It looks like you are 2/3 of the way to the answer.

        There is a scenario that satisfies the wording of the puzzle text, and there are three primes that are not constructible. And each of the three primes is non-constructible for a different reason.

        Like

    • Jim Randell's avatar

      Jim Randell 12:51 pm on 26 March 2022 Permalink | Reply

      I think there is potentially an alternative scenario that also gives three non-constructible primes:

      If the dice have the symbols I, V, X, L, D, M on them (so not C), then one of the primes is not constructible (using “standard” Roman numerals), no matter how many dice are used.

      We can modify the program for this scenario by only considering primes that don’t include C when constructing the dictionary d:

      # record constructible primes by their roman numeral content
d = group(prms, by=(lambda n: join(sorted(int2roman(n)))), st=lt(90))

      Or here is a version of my code that tries all possible combinations of 6 of the 7 symbols I, V, X, L, C, D, M for the dice [ @replit ], it finds three possibilities corresponding to the two scenarios outlined above.

      from enigma import (primes, int2roman, group, join, multiset, subsets, printf)

# primes less than 100
prms = list(primes.between(2, 99))
  
# find length n extensions of ks in d
def extend(d, ks, n):
  ss = list(multiset.from_seq(k) for k in ks)
  for k in d.keys():
    if len(k) == n:
      s = multiset.from_seq(k)
      if any(s.issuperset(s_) for s_ in ss):
        yield k

def generate(d, n=2):
  # start with length n sequences
  ks = list(k for k in d.keys() if len(k) == n)
  while ks:
    yield (n, ks)
    # find keys that are one longer
    n += 1
    ks = list(extend(d, ks, n))

# solve the puzzle for allowable symbols
def solve(symbols):

  # record primes their roman numeral content
  d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))

  # remove keys with invalid symbols
  d = dict((k, v) for (k, v) in d.items() if symbols.issuperset(k))
  
  # start with the complete set of primes
  ps = set(prms)
  for (n, ks) in generate(d, 2):
    # remove those reachable after n dice
    for k in ks:
      ps.difference_update(d[k])
    # we have a solution if there are 3 primes remaining
    if len(ps) == 3:
      printf("{syms}: {n} dice -> {ps}", syms=join(sorted(symbols)), ps=sorted(ps))

# choose 6 symbols for the dice
for syms in subsets('IVXLCDM', size=6, fn=set):
  solve(syms)

      I think I prefer the original scenario given above, where a sufficient number of dice can be used to give the numbers from 1 to 899. A set of dice without C would only be able to go consecutively up to 89 (the next smallest constructible number would be 500). D and M don’t come into play until 400 and 900 respectively.

      Like

      • Jim Randell's avatar

        Jim Randell 9:58 am on 1 April 2022 Permalink | Reply

        Depending on the shape of the glyphs used on the dice, it may be possible to use a V on its side to represent C, which would leave only 2 primes non-constructible in this second scenario (unless the number of dice is limited – and then we get the same solution as my first scenario).

        Like

    • Hugh+Casement's avatar

      Hugh+Casement 1:21 pm on 26 March 2022 Permalink | Reply

      I came to the same conclusion as Robert. I feel the setter of this puzzle has played a trick on us, but Jim rumbled it (before he came up with the alternative scenario ). It would have been neater, to my mind, if the puzzle text had stated that there were just two primes less than 100 that could not occur.

      Like

      • Jim Randell's avatar

        Jim Randell 3:58 pm on 26 March 2022 Permalink | Reply

        There’s definitely some trickery going on, as what you might expect to be the normal interpretation does not give 3 non-constructible primes.

        We would need to have more information about the symbols or number of dice to work out which scenario the setter had in mind.

        Like

  • Unknown's avatar

    Jim Randell 7:40 am on 24 March 2022 Permalink | Reply
    Tags:   

    Teaser 2859: Palindromic 

    From The Sunday Times, 9th July 2017 [link] [link]

    I have assigned to each letter of the alphabet a different number from 0 to 25. Therefore, for example, a three-letter word might stand for a number of three, four, five or six digits. In fact all the letters used in PALINDROMIC have even values. Furthermore, the number represented by this word contains no zeros and is indeed palindromic.

    Find the number represented by PIN.

    [teaser2859]

     
    • Jim Randell's avatar

      Jim Randell 7:41 am on 24 March 2022 Permalink | Reply

      The representation of a word is the concatenation of the numbers representing each letter.

      There are only 10 letters present in PALINDROMIC, and there are only 10 even values that don’t contain the digit 0.

      We can use a short program to consider all possible assignments to of values to letters.

      It is not a spectacularly fast approach, but I think in this case the simplicity of the program outweighs the desire for optimisation.

      The following Python program runs in 1.69s.

      from enigma import (irange, subsets, is_palindrome, join, printf)

# collect values
vs = set(s for s in map(str, irange(2, 24, step=2)) if '0' not in s)

# assign symbols to values
for (P, A, L, I, N, D, R, O, M, C) in subsets(vs, size=10, select="P"):
  vs = (P, A, L, I, N, D, R, O, M, I, C)
  if is_palindrome(join(vs)):
    fmt = lambda s: join(s, sep=":") + " = " + join(s)
    printf("PALINDROMIC = {s1} [PIN = {s2}]", s1=fmt(vs), s2=fmt((P, I, N)))

      Solution: PIN = 24412.

      There are 2 ways to assign the values to the letters:

      PALINDROMIC = 24:6:18:4:12:22:14:8:16:4:2 = 24618412221481642; PIN = 24:4:12 = 24412
      PALINDROMIC = 24:8:16:4:12:22:14:6:18:4:2 = 24816412221461842; PIN = 24:4:12 = 24412

      In the first case we have A:L = 6:18 and O:M = 8:16.

      In the second case we have A:L = 8:16 and O:M = 6:18.

      But both cases give the same value for PIN.

      Like

      • Jim Randell's avatar

        Jim Randell 7:45 am on 24 March 2022 Permalink | Reply

        If we build up the values for the letters starting at the beginning and end of PALINDROMIC we can discard candidates that will not form a palindrome without having to assign the remaining letters.

        Here I have used the [[ SubstitutedExpression ]] solver from the enigma.py to keep things compact.

        Checking values (P, C), (PA, IC), (PAL, MIC) cuts the run time down to 86ms.

        #! python3 -m enigma -rr

SubstitutedExpression

--base=26
--digits="2,4,6,8,12,14,16,18,22,24"

# we only need this
"is_palindrome(concat(P, A, L, I, N, D, R, O, M, I, C))"

# but these conditions speed things up
--code="check = lambda x, y: zip_eq(x, reverse(y))"
"check(concat(P), concat(C))"
"check(concat(P, A), concat(I, C))"
"check(concat(P, A, L), concat(M, I, C))"

# answer to the puzzle
--answer="concat(P, I, N)"

# [optional] tidy up output
--template=""

        Like

  • Unknown's avatar

    Jim Randell 11:44 am on 22 March 2022 Permalink | Reply
    Tags:   

    Teaser 2734: Interlocking squares 

    From The Sunday Times, 15th February 2015 [link] [link]

    Place all of the digits 0 to 9 in the grid so that, reading across or down in crossword fashion, one can see a two-figure square, a three-figure square, and two four-figure squares.

    What (in increasing order) are the four squares?

    [teaser2734]

     
    • Jim Randell's avatar

      Jim Randell 11:45 am on 22 March 2022 Permalink | Reply

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 114ms.

      Run: [ @replit ]

      #! python3 -m enigma -rr

#  # A # #
#  B C D E
#  # F # G
#  H J # K

SubstitutedExpression

# across
"is_square(BCDE)"
"is_square(HJ)"

# down
"is_square(ACFJ)"
"is_square(EGK)"

# answer
--answer="ordered(BCDE, HJ, ACFJ, EGK)"

      Solution: The squares are: 49, 576, 1089, 3025.

      (49, 576, 1089, 3025) = (7², 24², 33², 55²).

      Like

    • GeoffR's avatar

      GeoffR 2:33 pm on 22 March 2022 Permalink | Reply 

      % A Solution in MiniZinc
include "globals.mzn";

%    # A # #
%    B C D E
%    # F # G
%    H J # K

var 1..9:A; var 1..9:B; var 0..9:C; var 0..9:D;
var 1..9:E; var 0..9:F; var 0..9:G; var 1..9:H;
var 0..9:J; var 0..9:K;

constraint all_different([A,B,C,D,E,F,G,H,J,K]);

% sets of 2,3 and 4-digit squares
set of int: sq2 = {n*n | n in 4..9};
set of int: sq3 = {n*n | n in 10..31};  
set of int: sq4 = {n*n | n in 32..99};  

constraint (10*H + J) in sq2;
constraint (100*E +10*G + K) in sq3;
constraint (1000*A + 100*C + 10*F + J) in sq4 
/\ (1000*B + 100*C + 10*D + E) in sq4;

solve satisfy;

output [ "[A,B,C,D,E,F,G,H,J,K] = " ++ show([A,B,C,D,E,F,G,H,J,K])];
% [1, 3, 0, 2, 5, 8, 7, 4, 9, 6]
% [A, B, C, D, E, F, G, H, J, K]
% ----------
% ==========
% Squares : HJ = 49, EGK = 576, ACFJ = 1089, BCDE = 3025

      Like

    • GeoffR's avatar

      GeoffR 8:10 am on 23 March 2022 Permalink | Reply

      A three stage permutation solution.

      from itertools import permutations
from enigma import is_square

digits = set('1234567890')

# two digit square HJ
for p1 in permutations(digits, 2):
  h, j = p1
  if h == '0':continue
  hj = int(h + j)   
  if not is_square(hj):continue
  q1 = digits.difference({h, j})
    
  # three digit square EGK
  for p2 in permutations(q1, 3):
    e, g, k = p2
    if e == '0':continue
    egk = int(e + g + k)
    if not is_square(egk):continue
        
    # two four digit squares BCDE and ACFJ
    q2 = q1.difference({e, g, k})
    for p3 in permutations(q2):
      a, b, c, d, f = p3
      if '0' in (a, b): continue
      bcde = int(b + c + d + e)
      if is_square(bcde):
        acfj = int(a + c + f + j)
        if is_square(acfj):
          print(f"HJ={hj}, EGK={egk}, ACFJ={acfj}, BCDE={bcde}")
                  
# HJ=49, EGK=576, ACFJ=1089, BCDE=3025

      Like

  • Unknown's avatar

    Jim Randell 8:29 am on 20 March 2022 Permalink | Reply
    Tags: by: S. T. Shovelton   

    Brain Teaser: An Oxford medley 

    From The Sunday Times, 21st December 1958 [link]

    Five men are up at the five colleges at which their fathers were undergraduates, though no one son is at his father’s old college.

    Each of the men spent part of the long vac as a guest at the home of one of the others and as host to another. Their five home towns are the namesakes of the five colleges, though in no case is a man’s home town, or the home town of the man he visited, the namesake of his own college or of his father’s old college.

    Jones plays soccer for the Varsity; so do the Hertford and Pembroke men, and the man who lives at Worcester. The man who lives at Exeter visited the town which is the namesake of the college at which Smith is an undergraduate. The man who visited Exeter plays fives with Jones and lives in the town which is the namesake of the college at which Robinson is an undergraduate. The Exeter man visited Jones in the long vac. The man whose father was at Exeter is at the college of which Robinson’s father was an undergraduate; it is the namesake of Black’s home town.

    What is the name of the man who was the guest in the long vac of the man whose home town is the namesake of the college at which the father of the Worcester man was an undergraduate?

    This one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. A prize of £5 was offered.

    [teaser-1958-12-21] [teaser-unnumbered]

     
    • Jim Randell's avatar

      Jim Randell 8:33 am on 20 March 2022 Permalink | Reply

      There is one college/town not mentioned in the puzzle text (I denote it with X), and also the surname of one of the students is not mentions (I denote it with Y).

      If we imagine a table with the columns representing values that are college/town names for each of the students (J, S, R, B, Y), and the rows representing the following values:

      c = college attended by the student
      t = home town of the student
      v = town visited by the student during the long vac
      f = collect attended by the student’s father

      Then each row is a permutation of the available college/town names (E, H, P, W, X) and each column consists of 4-different values.

      So each row is a derangement of the previous rows.

      This Python program runs in 139ms.

      Run: [ @replit ]

      from enigma import (irange, join, printf)

# labels for colleges/towns
labels = "HPWEX"

# indices for the students
students = (J, S, R, B, Y) = irange(5)

# produce an arrangement of values from <vs>, not already in maps <ms>
# return a forward map (array) and a reverse map (dict)
def derange(vs, ms, xs=[]):
  # are we done?
  if not vs:
    yield (tuple(xs), dict((x, i) for (i, x) in enumerate(xs)))
  else:
    # choose a value for slot k
    k = len(xs)
    for (i, x) in enumerate(vs):
      if all(m[k] != x for m in ms):
        yield from derange(vs[:i] + vs[i + 1:], ms, xs + [x])

# assign colleges to the students
# c: map student -> college
for (c, c_) in derange(labels, []):

  # "J plays soccer... so do the H and P men"
  # "the E man visited J during the long vac"
  # so, J is not at H, P, E
  if c[J] in 'HPE': continue

  # assign towns to the students
  # t: map student -> town
  for (t, t_) in derange(labels, [c]):

    # the man who live at W is not J, or the H or P man
    if t[J] == 'W': continue
    if c[t_['W']] in 'HP': continue

    # assign visits to students
    # v: map student -> town
    for (v, v_) in derange(labels, [c, t]):

      # "the E man visited J"
      if v[c_['E']] != t[J]: continue
      
      # "the man who visits E plays fives with J..."
      # so J did not visit E
      if v[J] == 'E': continue
      # "... and lives in the town which shares a name with the R's college"
      if t[v_['E']] != c[R]: continue

      # "the man who lives at E visited the town which shares a name with S's college"
      if v[t_['E']] != c[S]: continue

      # assign father's colleges to students
      # f: map student -> college
      for (f, f_) in derange(labels, [c, t, v]):

        # "the man whose father was at E is at the college attended by R's father ..."
        if c[f_['E']] != f[R]: continue
        # "... which shares a name with B's town"
        if f[R] != t[B]: continue

        # "what is the name of the man who was the guest of the man
        # whose town is the namesake of the college at which the
        # father of the W man was an undergraduate"
        r = v_[f[c_['W']]]

        # output solution
        printf("[   J S R B Y]")
        printf("[c: {c}]", c=join(c, sep=" "))
        printf("[t: {t}]", t=join(t, sep=" "))
        printf("[v: {v}]", v=join(v, sep=" "))
        printf("[f: {f}]", f=join(f, sep=" "))
        printf("answer = {r}", r="JSRBY"[r])
        printf()

      Solution: The answer is Smith.

      i.e. Smith was the guest of Robinson in Exeter (town) during the long vac. And Exeter is the college that Jones’s father attended, while Jones himself went to Worcester College (as did I).

      Like

    • Hugh+Casement's avatar

      Hugh+Casement 12:28 pm on 20 March 2022 Permalink | Reply

      I’m putting my money on Lincoln for the missing college, though there are a few other possibilities.

      If you’re looking for common surnames (for example to make up puzzles of your own), the top six in England are Smith, Jones, Williams, Taylor, Davies, and Brown. Robinson is no. 12, and I don’t think Black occurs in the first 50 (though Green and White are both among the first 25).

      Like

  • Unknown's avatar

    Jim Randell 4:43 pm on 18 March 2022 Permalink | Reply
    Tags:   

    Teaser 3104: Prime football 

    From The Sunday Times, 20th March 2022 [link] [link]

    There are more than 13 clubs in the Prime Football League, and each club plays each other twice during the football season, gaining three points for winning a match, and one point for a draw.

    At the end of last season, it was observed that the final numbers of points gained by the clubs were all different double-digit prime numbers. During the season our local club, Wessex Wanderers, won just three times as many matches as they lost. If you knew how many clubs were in the league, you could work out the final points total of Wessex Wanderers.

    How many clubs are in the league, and what was the final points total of Wessex Wanderers?

    [teaser3104]

     
    • Jim Randell's avatar

      Jim Randell 5:55 pm on 18 March 2022 Permalink | Reply

      We know there are more than 13 teams in the league, and there are only 21 primes between 10 and 99, so this puts an upper limit on the number of teams in the league.

      If there are n teams in the league, and each team plays every other team twice during a season, then there are a total of 2 × C(n, 2) matches during the season. And each team plays 2(n − 1) matches.

      So we can consider the number of draws d played by WW. The remaining matches must be 3/4 wins and 1/4 losses. So we can calculate p = WW’s points at the end of the season, and this must be a 2-digit prime number.

      We can then look to see if there is a scenario where the teams can all score a different 2-digit prime number of points, and if there is a way for this to occur then we have a viable (n, p) pair. (The program only checks that there is an n-subset of the primes, that includes p, and sums to a potentially viable total number of points awarded during the season. But it turns out this step doesn’t weed out any candidate solutions anyway, so a simpler program would find the same answer).

      This Python program looks for viable (n, p) pairs, and looks for solutions where if we knew n there is a unique value for p. It runs in 94ms.

      Run: [ @replit ]

      from enigma import (primes, irange, C, subsets, div, Record, filter_unique, printf)

# 2-digit primes
prms = set(primes.between(10, 99))

# find a viable scenario
def scenario(r):
  (n, w, d, l, p) = (r.n, r.w, r.d, r.l, r.p)
  # m = total number of number of matches
  m = 2 * C(n, 2)
  # consider possible total number of draws in all matches
  for td in irange(d, m - w - l):
    # calculate the total number of points awarded
    tp = 2 * td + 3 * (m - td)
    # can tp be made from an n-subset of primes (that includes p)?
    for ps in subsets(prms, size=n):
      if p in ps and sum(ps) == tp:
        # then this is a viable scenario
        printf("[n={n}; l={l} w={w} d={d}; p={p} -> ps={ps}]")
        yield ps

# generate viable scenarios
def generate():
  #  consider n = number of teams in the league
  for n in irange(14, len(prms)):
    # WW plays 2(n - 1) matches
    # if there are d draws, then the remaining matches are (3/4) win and (1/4) lost
    t = 2 * (n - 1)
    for l in irange(0, t // 4):
      w = 3 * l
      d = t - l - w
      # and calculate the points (a 2-digit prime)
      p = 3 * w + d
      if p not in prms: continue

      # is there a viable scenario?
      r = Record(n=n, w=w, d=d, l=l, p=p)
      for ps in scenario(r):
        yield Record.update(r, ps=ps)
        break

# find solutions if we know n we can work out p
for r in filter_unique(generate(), (lambda r: r.n), (lambda r: r.p)).unique:
  printf("n={r.n} p={r.p}")

      Solution: There are 18 clubs in the league. The final points total for Wessex Wanderers was 59.

      We find there are the following potential (n, p) pairs (grouped by n):

      n=14: p=31 (w=3, d=22); p=41 (w=9, d=14)
      n=15: p=43 (w=9, d=16); p=53 (w=15, d=8)
      n=17: p=37 (w=3, d=28); p=47 (w=9, d=20); p=67 (w=21, d=4)
      n=18: p=59 (w=15, d=14)
      n=19: p=41 (w=3, d=32); p=61 (w=15, d=16); p=71 (w=21, d=8)
      n=20: p=43 (w=3, d=34); p=53 (w=9, d=26); p=73 (w=21, d=10); p=83 (w=27, d=2)

      If each of these situations is viable then the answer is n=18, p=59, as this is the only one where knowing n gives a unique p value.

      And we can show that the n =18, p=59 situation is viable as follows:

      With 18 teams there are 2×C(18, 2) = 306 matches.

      One situation that gives each team a different 2-digit prime number of points is:

      1st: A; 97 pts = 32 wins (BCCDDEFFGGHHIIJJKKLLMMNNOOPPQQWW) + 1 draw (E)
      2nd: B; 79 pts = 25 wins (ADDEEGHHIIJKKLLMMNNOOPPQQ) + 4 draws (CCGJ)
      3rd: C; 73 pts = 21 wins (EEHHIKKLLMMNNOOPPQQWW) + 10 draws (BBDDFFGGIJ)
      4th: D; 71 pts = 22 wins(FFGGHHIJJKKLLMMNNOPPQQ) + 5 draws (CCEEO)
      5th: E; 67 pts = 19 wins (FHIJJKKLLMMNNOOPPQQ) + 10 draws (ADDFGGHIWW)
      6th: W; 59 pts = 15 wins (BBDDGGHHLLMMPQQ) + 14 draws (EEFFIJJKKNNOOP)
      7th: F; 53 pts = 13 wins (BBHHIINNOOPQQ) + 14 draws (CCEGGJJLLMMPWW)
      8th: G; 47pts = 10 wins (LLMMNOOPPQ) + 17 draws (BCCEEFFHHIIJJKKNQ)
      9th: H; 43 pts = 11 wins (KKLMNOOPPQQ) + 10 draws (EGGIIJJLMN)
      10th: I; 41 pts = 9 wins (DNOOPPQQW) + 14 draws (CEGGHHJJKLMMNW)
      11th: J; 37 pts = 6 wins (CMMPPQ) + 19 draws (BCFFGGHHIIKKNNOOQWW)
      12th: K; 31 pts = 5 wins (FFINN) + 16 draws (GGIJJLLMOOPPQQWW)
      13th: L; 29 pts = 5 wins (IJJQQ) + 14 draws (FFHIKKMMNNOOPP)
      14th: M; 23 pts = 3 wins (KOO) + 14 draws (FFHIIKLLNNPPQQ)
      15th: N; 19 pts = 1 win (Q) + 16 draws (GHIJJLLMMOOPPQWW)
      16th: O; 17 pts = 1 win (P) + 14 draws (DJJKKLLNNPQQWW)
      17th: P; 13 pts = 13 draws (FKKLLMMNNOQQW)
      18th: Q; 11 pts = 11 draws (GJKKMMNOOPP)

      This verifies that n =18, p=59 is indeed a solution to the puzzle.

      Although to show that it is the only solution would require showing that there are at least 2 viable (n, p) values for n = 14, 15, 17, 19, 20.

      I think this would be quite tedious to do by hand. But the program below verifies each of the potential situations given is viable, which means that n = 18 is the only solution.

      Like

      • Jim Randell's avatar

        Jim Randell 11:38 am on 20 March 2022 Permalink | Reply

        Here is a variation on the program above. It looks for a viable collection of matches that produces the required points for WW, and different prime numbers of points for each of the other teams.

        It uses a MiniZinc model (highlighted below) to look for viable scenarios, and it does take a while to check all possible (n, w, l, p) values, but it turns out each of them is viable, so a shorter program which doesn’t check for viability will produce the correct result.

        from enigma import (primes, irange, C, subsets, div, Record, filter_unique, update, sprintf, join, peek, printf)
from minizinc import MiniZinc

# 2-digit primes 
prms = set(primes.between(10, 99))

# check for a viable scenario (using MiniZinc)

# the model
model = """
include "globals.mzn";

% 2-digit primes
set of int: primes = {prms};

% number of teams
int: n = {n};

% decision table: x[i, j] = number of matches won by team i against team j
array [1..n, 1..n] of var 0..2: x;

constraint forall (i in 1..n) (x[i, i] = 0);
constraint forall (i, j in 1..n where i < j) (x[i, j] + x[j, i] < 3);

% calculate points for a team
function var int: wins(var int: i) = sum (j in 1..n) (x[i, j]);
function var int: loss(var int: i) = sum (j in 1..n) (x[j, i]);
function var int: points(var int: i) = 2 * (n - 1 + wins(i)) - loss(i);

% points for each team
array [1..n] of var 10..99: pts;

constraint forall (i in 1..n) (pts[i] = points(i) /\ pts[i] in primes);
constraint all_different(pts);

% specific constraints for team 1
constraint pts[1] = {p} /\ wins(1) = {w} /\ loss(1) = {l};

solve satisfy;
"""

# default environment
env = dict(primes=join(prms, sep=", ", enc="{}"))

# check for a viable scenario
def scenario(r):
  vs = update(env, Record.map(r).items())
  # create the model
  m = MiniZinc(sprintf(model, **vs), solver="minizinc --solver cbc")
  # is there a solution to the model?
  return peek(m.solve(), default=None)
  
# generate viable scenarios
def generate():
  #  consider n = number of teams in the league
  for n in irange(14, len(prms)):
    # WW plays 2(n - 1) matches
    # if there are d draws, then the remaining matches are (3/4) win and (1/4) lost
    t = 2 * (n - 1)
    for l in irange(0, t // 4):
      w = 3 * l
      d = t - l - w
      # and calculate the points (a 2-digit prime)
      p = 3 * w + d
      if p not in prms: continue

      # check for a viable scenario
      r = Record(n=n, w=w, d=d, l=l, p=p)
      if scenario(r):
        printf("[n={n}; d={d} w={w} l={l} p={p}]")
        yield r

# find solutions if we know n we can work out p
for r in filter_unique(generate(), (lambda r: r.n), (lambda r: r.p)).unique:
  printf("n={r.n} p={r.p} [{r}]")

        I found the mzn-g12mip solver and cbc solver gave run times of around 25s.

        Like

    • Alex T Sutherland's avatar

      Alex T Sutherland 3:39 pm on 21 March 2022 Permalink | Reply 

      Number_of_ Teams = [14:21] ;     Teams_Count  = [0];
Do for each Number_ of_ Teams
               Calculate Number_of_ games_ played = g
               Do for each Number_of_Losses [0 : g ]           This range can be shortened 
                        Wins= 3*Losses
                        Draws  = g - Wins -Losses
                        if Draws < 0
                             continue  to next Loss
                        Points  = a*Losses + b*g                                       a & b can easily be derived 
                        if  Points are in prime  range (11 :97]   ;     if not continue to next Loss
                              Record the data
                              Increment the count for this team number
                end 
end

      From the record obtain the data for team number who has a count = 1
      My answer has (number of teams + their number of losses ) = prime number.
      Run time :- varies between 2 and 6 ms.

      Like

  • Unknown's avatar

    Jim Randell 10:23 am on 17 March 2022 Permalink | Reply
    Tags:   

    Teaser 2722: A simple sum 

    From The Sunday Times, 23rd November 2014 [link]

    I have written down two three-figure numbers and one four-figure number: between them they use each of the digits 0 to 9 exactly once. In fact the four-figure number is the sum of the other two numbers.

    If I told you how many of the three numbers were even, then it would be possible to work out the four-figure number.

    What is it?

    [teaser2722]

     
    • Jim Randell's avatar

      Jim Randell 10:24 am on 17 March 2022 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression ]] solver, from the enigma.py library, to find possible sums, and then the [[ filter_unique ]] function to find those that give a unique result if we know the number of even numbers involved.

      It runs in 58ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, filter_unique, unpack, multiset, printf)

# find viable alphametic sums
p = SubstitutedExpression.split_sum(
  "ABC + DEF = GHIJ",
  extra=["A < D"], # remove duplicates
  answer="(ABC, DEF, GHIJ)",
)

# if we knew how many of the numbers were even, we could work out the result
rs = filter_unique(
  p.answers(verbose=0),
  (lambda ns: sum(n % 2 == 0 for n in ns)),
  unpack(lambda x, y, z: z),
)

# output possible sums
m = multiset()
for (x, y, z) in rs.unique:
  printf("[{x} + {y} = {z}]")
  m.add(z)

# output solution
for (v, n) in m.most_common():
  printf("result = {v} [{n} sums]")

      Solution: The result of the sum is 1098.

      There are 4 possible sums:

      356 + 742 = 1098
      346 + 752 = 1098
      352 + 746 = 1098
      342 + 756 = 1098

      (And another 4 where the summands are swapped around).

      Like

    • Hugh+Casement's avatar

      Hugh+Casement 8:58 am on 18 March 2022 Permalink | Reply

      Either all three numbers are even, or only one of them is.

      If just one of the three-digit numbers is even, there are 24 possible sets,
      with sum 1035, 1053, 1305, 1503, or 1089.
      If only the four-digit number is even, there are 20 possible sets,
      with sum 1026, 1062, 1206, 1602, or 1098.

      Only if both three-digit numbers are even do we have a unique sum.

      Like

    • GeoffR's avatar

      GeoffR 2:59 pm on 18 March 2022 Permalink | Reply

      A MiniZinc program does indeed confirm that two even numbers are required to sum to a unique four digit number.

      % A Solution in MiniZinc
include "globals.mzn";
 
var 1..9:A; var 0..9:B; var 0..9:C;
var 1..9:D; var 0..9:E; var 0..9:F;
var 1..9:G; var 0..9:H; var 0..9:I; var 0..9:J;

constraint all_different ([A,B,C,D,E,F,G,H,I,J]);

var 100..999:ABC = 100*A + 10*B + C;
var 100..999:DEF = 100*D + 10*E + F;
var 1000..9999:GHIJ = 1000*G + 100*H + 10*I + J;
constraint ABC > DEF;

% confirm two even 3-digit numbers are needed 
% to sum to a unique 4-digit number 
constraint ABC mod 2 == 0 /\ DEF mod 2 == 0;
constraint ABC + DEF == GHIJ;

solve satisfy;
output ["Sum is " ++ show(ABC) ++ " + " ++ show(DEF) 
++ " = " ++ show(GHIJ) ];

% Sum is 756 + 342 = 1098
% ----------
% Sum is 752 + 346 = 1098
% ----------
% Sum is 746 + 352 = 1098
% ----------
% Sum is 742 + 356 = 1098
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 9:44 am on 15 March 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 661: The logical choice 

    From The Sunday Times, 10th March 1974 [link]

    Four members who hold office in the Logic Club approve of each other. They recently decided among themselves that next year each of the four would hold an office now held by one of the other three.

    Other members wanted to know whether this was legal and who was moving to which office. So we asked them to explain themselves under the Club’s Friday rules: these rules say that a member must either make two correct statements or two incorrect statements.

    We unfortunately forgot that we were questioning them on a Tuesday, when members may keep the Friday rules or break them, just as they please.

    The President said: “What we are doing is legal. The man who will be Chairman next year keeps the Friday rules on Tuesdays”.

    The Chairman said: “I am keeping the Friday rules. I shall not become Secretary next year”.

    The Secretary said: “The Treasurer will become President next year. I am not keeping the Friday rules”.

    The Treasurer said: “The man who will be Secretary next year does not keep the Friday rules on Tuesdays. What we are doing is legal”.

    Which of them will be next year’s Chairman? Which will be next year’s Treasurer? Is what they are doing legal?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    [teaser661]

     
    • Jim Randell's avatar

      Jim Randell 9:45 am on 15 March 2022 Permalink | Reply

      If the questioning takes place on a Tuesday, where “members may keep the Friday rules (give two truth values the same) or break them (give two different truth values), just as they please”, to my mind this means the answers to the questions on a Tuesday can be any truth values, and we are none the wiser.

      I suspect we are meant to suppose that on a Tuesday the members either consistently keep the Friday rules (each pair of statements has the same truth value), or consistently break them (each pair of statements has one truth and one falsehood), and their pre-determined behaviour is known to the other officers. Then we can make progress.

      This Python program looks at all possible scenarios to find those which correspond to the described situation. It runs in 47ms.

      Run: [ @replit ]

      from enigma import (subsets, product, multiset, map2str, printf)

# f = keeping Friday rules; x, y = statements
check = lambda f, x, y: f == (x == y)

# we can populate the following variables:
#  j: map(current job -> new job);  p: map(new job -> current job)
#  f: map(current job -> keeping Friday rules
#  legal: boolean

# collect results (<next C>, <next T>, <legal>)
qs = multiset()

# consider possible assignments
people = (P, C, S, T) = "PCST"
js = subsets(people, size=4, select="D")
fs = subsets((0, 1), size=4, select="M")
for (jv, fv, legal) in product(js, fs, (0, 1)):
  j = dict(zip(people, jv))
  p = dict(zip(jv, people))
  f = dict(zip(people, fv))

  # P: "is legal; next C keeps Friday rules
  if not check(f[P], legal, f[p[C]]): continue
  
  # C: "C is keeping Friday rules; C will not become S"
  if not check(f[C], f[C], j[C] != S): continue

  # S: "T will become P; S is not keeping Friday rules"
  if not check(f[S], j[T] == P, not f[S]): continue

  # T: next S does not keep Friday rules; is legal"
  if not check(f[T], not f[p[S]], legal): continue
  
  printf("[legal={legal} j={j} f={f}]", j=map2str(j, arr="->"), f=map2str(f))
  qs.add((p[C], p[T], legal))

# output results
for ((q1, q2, q3), n) in qs.most_common():
  printf("(1) {q1} -> C; (2) {q2} -> T; (3) legal = {q3} [{n} solutions]", q3=bool(q3))

      Solution:(1) The Secretary plans to become the next Chairman; (2) The President plans to become the next Treasurer; (3) It is not legal.

      The plan for the assignment of jobs is:

      P → T
      C → P
      S → C
      T → S

      They can choose to follow Friday rules or not as they wish, except P must be the opposite of S.

      Like

  • Unknown's avatar

    Jim Randell 4:15 pm on 11 March 2022 Permalink | Reply
    Tags:   

    Teaser 3103: Empowered 

    From The Sunday Times, 13th March 2022 [link] [link]

    I have a rectangular garden whose sides are whole numbers of feet. Away from the edge, an exposed strip of ground, again a whole number of feet in width, runs straight across (not diagonally) from a shorter side of the garden to the other shorter side. I need to run an electrical cable along the ground, between two opposite corners of the garden. Where the cable crosses the exposed area, it has to be threaded through expensive linear ducting to avoid damage. Because of costs, whilst seeking to minimise the length of cable, my overriding concern is to minimise the length of ducting used.

    The straight-line distance between the two corners to be connected is 123 feet, but in minimising costs, the length of cable needed is a whole number of feet longer than this.

    What is the length of cable needed?

    [teaser3103]

     
    • Jim Randell's avatar

      Jim Randell 4:55 pm on 11 March 2022 Permalink | Reply

      The shortest amount of ducting is to cross the exposed area at right angles. The remaining length of cable required is then the diagonal of the garden with the exposed area removed.

      This Python program runs in 47ms.

      Run: [ @replit ]

      from enigma import (pythagorean_triples, irange, ihypot, printf)

# look for pythagorean triples with hypotenuse 123
for (x, y, z) in pythagorean_triples(123):
  if z != 123: continue

  # consider possible w = width of exposed area
  for w in irange(1, x - 1):
    # calculate d = length of cable required
    d = ihypot(x - w, y)
    if d is None: continue
    d += w
    # output solution
    printf("x={x} y={y} z={z}; w={w} d={d}")

      Solution: The total length of cable required is 127 feet.

      The garden is an x by y rectangle, where (x, y, 123) form a Pythagorean triple. So:

      x² + y² = 123²

      There is only one possible triple: (27, 120, 123).

      Also the width of the exposed area is w (where: w < x).

      And the amount of cable required is d we have:

      d = w + √((x − w)² + y²)
      (d − w)² = (x − w)² + y²

      So (x − w, y, d − w) is also a Pythagorean triple.

      The only triple with x < 27 and y = 120 is: (22, 120, 122).

      Hence:

      w = 5
      d = 127

      Like

    • GeoffR's avatar

      GeoffR 10:07 am on 12 March 2022 Permalink | Reply

      I looked at this teaser as two triangles with one above the horizontal strip and one below the horizontal strip. The cable length was then the sum of the two hypotenuses and the vertical crossing depth of the horizontal strip.

      It turns out that the two right angled triangles are the same, with dimensions (11, 60, 61).

      
% A Solution in MiniZinc
include "globals.mzn";

% Main rectangle x by y with z as diagonal and x horizontal dimensions
% Upper triangle is above horizontal strip (a, x1, h1) 
% ... and lower triangle (below  horizontal strip)  is (b, x2, h2)

% Cable length = Hypotenuse h1 + w(vertical) + Hypotenuse h2
% Top triangle has vertical dimension (a) above horizontal strip 
var 1..50:a; var 1..100:x1;  var 1..100:h1;

int: z == 123; % main diagonal of rectangle
var 1..200:x; var 1..100:y; % main rectangle dimensions

% w = vertical depth of strip, c = cable length
var 1..50:w; var 124..150:c;

% Bottom triangle - vertical dimension (b) below horizontal strip
var 1..50:b; var 1..100:x2;  var 1..100:h2; 

constraint x*x + y*y == z*z;  % main rectangle
constraint a*a + x1*x1 == h1*h1; % triangle above strip
constraint b*b + x2*x2 == h2*h2; % triangle below strip

constraint c == h1 + w + h2;  % cable length (> z)

% Main rectangle dimensions and part side dimensions
constraint y == a + b + w /\ x == x1 + x2;

% minimise the length of ducting used
solve minimize(w);
output ["Length of cable needed = " ++ show(c) ++ " feet"];

      Like

      • Jim Randell's avatar

        Jim Randell 12:17 pm on 12 March 2022 Permalink | Reply

        @Geoff: Of course we don’t know that (a, x1, h1) and (b, x2, h2) are all integers. But we do know a+b and h1+h2 must be integers, so we can just consider (a+b, x, h1+h2) to find the solution.

        Like

    • GeoffR's avatar

      GeoffR 1:28 pm on 12 March 2022 Permalink | Reply

      @Jim:

      True, but it seemed a reasonable assumption at the time.

      The output from the programme verified my assumption, but I understand the technical point you make about these dimensions not being specifically stated as integers.

      We do know that the length of the cable(c) is a whole number of feet longer than the diagonal(z), and that c = h1 + w + h2. This suggested to me that it would be perhaps be unlikely for any of h1, w, or h2 to be floating point numbers. My two triangle approach also needs integers to work as Pythagorean triangles, of course.

      Like

    • GeoffR's avatar

      GeoffR 7:50 am on 14 March 2022 Permalink | Reply

      A simpler solution, based on Brian’s manual solution.

      % A Solution in MiniZinc
include "globals.mzn";
 
int: z == 123; % main diagonal of rectangle
var 1..200:x; var 1..100:y; % main rectangle dimensions
 
% d = duct length, c = cable length
var 1..20:d; 
var 124..150:c;

constraint x * x + y * y = z * z;

% Moving the strip to bottom of the rectangle, to give geometrical equivalency,
% - the following formula can be derived:
constraint d == (c * c - z * z) / (2 * (c - y));

solve satisfy;
output [ "Cable length = " ++ show(c) ++" feet"];

      Like

      • Jim Randell's avatar

        Jim Randell 12:56 pm on 14 March 2022 Permalink | Reply

        @Geoff: Yes, that is what I was getting at. There is no need to split the garden into two rectangles, when we can just consider the diagonal of the garden with the exposed area removed. (And in the general case, I don’t think it would always be possible to split the remaining garden into two rectangles with integer sides, and with an integer length of cable running through them, so it is lucky that it occurs in this instance).

        And we don’t even need to derive a formula for the width of the exposed area.

        Here’s my MiniZinc model that interprets my original program:

        %#! minizinc -a

% garden is x by y (x < y), diagonal z
int: z = 123;
var 1..121: x;
var 2..122: y;
constraint  x < y;
% (x, y, z) is a pythagorean triple
constraint pow(x, 2) + pow(y, 2) = pow(z, 2);

% exposed area width = w (< x)
var 1..120: w;
constraint w < x;

% total length of cable = d
var 124..245: d;
% (x - w, y, d - w) is a pythagorean triple
constraint pow(x - w, 2) + pow(y, 2) = pow(d - w, 2);

solve satisfy;

        Like

    • Hugh+Casement's avatar

      Hugh+Casement 7:22 am on 21 March 2022 Permalink | Reply

      I find that a strange shape for a garden.
      A more realistic puzzle would have involved one 140 × 51 ft (diagonal 149 ft),
      with a path 3 ft wide, parallel to the long sides, that for practical reasons has to be traversed at right angles to its length.

      Like

  • Unknown's avatar

    Jim Randell 8:47 am on 10 March 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 682: Jigsaw 

    From The Sunday Times, 11th August 1974 [link]

    “Bend me your ears”, says Bell wittily at the pub. “I have here six cardboard squares all of different sizes and one extra rectangular piece, which is bigger than the smallest square but smaller than any of the other five”.

    “Now I fit them together as a jigsaw puzzle to make a complete rectangle. All the pieces measure an exact number of inches and nobody can make a smaller jigsaw out of any such seven pieces. Bigger and smaller, of course, means by areas”.

    “To help you I will tell you this table is 20 inches square, and the jigsaw, you can see, is smaller than that. For the first solution I shall be happy to award one pint”.

    What are the measurements of:

    (a) the six squares?
    (b) the extra piece?
    (c) the jigsaw?

    The setter is given as “the late W A Thatcher”.

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    [teaser682]

     
    • Jim Randell's avatar

      Jim Randell 8:48 am on 10 March 2022 Permalink | Reply

      This Python program uses the rectangle packing code rectpack.py, last seen in Teaser 2806.

      It considers possible values for the total area of the pieces, then sees if that area can be made from 6 squares and a rectangular piece, and then attempts to pack them into a rectangle that fits within the table.

      It runs in 261ms. (Internal runtime is 207ms).

      Run: [ @replit ]

      from enigma import (irange, inf, divisors_pairs, multiply, printf)
from rectpack import (pack, output_grid)

# construct a set of <k> square pieces and a rectangular piece of total area <t>
# s = minimal side of square
# rs = current rectangles
def pieces(t, k, s=1, rs=[]):
  # are we done?
  if k == 0:
    if len(rs) > 1:
      # final piece is a rectangle, between the smallest squares
      if multiply(rs[0]) < t < multiply(rs[1]):
        for (x, y) in divisors_pairs(t):
          if x < y < 21:
            yield rs + [(x, y)]
  else:
    # add in another square
    for x in irange(s, inf):
      x2 = x * x
      if t < k * x2 + 2: break
      yield from pieces(t - x2, k - 1, x + 1, rs + [(x, x)])

# find a minimal solution
def solve():
  # consider possible total areas
  for t in irange(93, 380):
    for (x, y) in divisors_pairs(t):
      if y > 20: continue

      for rs in pieces(t, 6):
        for ps in pack(y, x, rs):
          # output solution
          printf("t={t} x={x} y={y} -> {rs}")
          printf()
          output_grid(y, x, ps)
          printf()

          # we only need 1 packing
          return

solve()

      Solution: (a) The six squares measure: 1×1, 4×4, 5×5, 6×6, 7×7, 8×8. (b) The extra piece is a 1×4 rectangle. (c) The jigsaw is 13×15.

      Here is the layout found by the program:

      Note that the 5×5, 4×4, 1×4 pieces form sub-rectangles that can be rearranged to give additional layouts.

      There are also solutions for a 15×17 jigsaw and a 17×19 jigsaw.

      Like

  • Unknown's avatar

    Jim Randell 9:24 am on 8 March 2022 Permalink | Reply
    Tags:   

    Teaser 2873: Circular logic 

    From The Sunday Times, 15th October 2017 [link] [link]

    Ten of us (me [Ian], Alice, Arnold, Carla, Celia, Clara, Ina, Rona, Ronald and Roland) were sitting equally-spaced around a circular table. None of us was directly opposite or next to anyone whose name was an anagram of theirs, or between two people whose names were anagrams of each other. The same applied when looking at the initial letters of the names.

    Then Ari and Ira joined us. We found two extra chairs and all budged up to make two spaces. With the twelve of us equally-spaced around the circular table all the above facts remained true. I was now opposite a different person, Roland.

    Who from the twelve was then directly opposite Alice? And who was opposite Celia?

    [teaser2873]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 8 March 2022 Permalink | Reply

      We can look for viable 12-seat layouts, and then remove Ari and Ira to give a 10-seat layout, which we can check is viable.

      This Python program runs in 88ms.

      Run: [ @replit ]

      from enigma import (update, ordered, diff, join, printf)

# implement a circular list (see Tantalizer 496)
class CircularList(list):

  def __getitem__(self, i):
    return list.__getitem__(self, i % len(self))

  def copy(self):
    # list.copy() returns a list(), so re-wrap it
    return self.__class__(list.copy(self))

# find names in <ns> that can be opposite/adjacent to <ps>
def valid(ns, ps):
  # find disallowed initials and anagrams
  xis = set(p[0] for p in ps if p is not None)
  xas = set(ordered(*p) for p in ps if p is not None)
  for n in ns:
    if n[0] in xis or ordered(*n) in xas: continue
    yield n

# place names <ns> in table <t>
def place(t, ns):
  # are we done?
  if not ns:
    if t[1] < t[-1]:
      yield t
  else:
    # find the next unoccupied place
    i = t.index(None)
    # choose someone to occupy it
    for n in valid(ns, {t[i + 6], t[i - 1], t[i + 1], t[i - 2], t[i + 2]}):
      yield from place(update(t, [(i, n)]), ns.difference([n]))

# create a 12-place table
t = CircularList([None] * 12)

# place IAN at position 0 and ROLAND in position 6
t[0] = "IAN"
t[6] = "ROLAND"

# the remaining people
people = { "ALICE", "ARNOLD", "CARLA", "CELIA", "CLARA", "INA", "RONA", "RONALD", "ARI", "IRA" }

# find possible 12 place tables
for t12 in place(t, people):
  # now remove ARI and IRA to give a 10 place table
  t = CircularList(diff(t12, {"ARI", "IRA"}))
  # check ROLAND is no longer opposite IAN
  if t[5] == "ROLAND": continue
  # check t is a valid table
  if not all(n in valid([n], {t[i + 5], t[i - 1], t[i + 1], t[i - 2], t[i + 2]}) for (i, n) in enumerate(t)): continue
  
  # output solution
  printf("{t12} <- {t10}", t12=join(t12, sep=" ", enc="[]"), t10=join(t, sep=" ", enc="[]"))
  for x in ["ALICE", "CELIA"]:
    opp = t[t.index(x) + 5]
    printf("-> ({x} <-> {opp})")
  printf()

      Solution: Rona ended up opposite Alice. Ira ended up opposite Celia.

      Here is a possible layout of the 12 seats (going round the table, listing opposites):

      IAN = 0; ROLAND = 6
      ARI = 1; CLARA = 7
      RONALD = 2; INA = 8
      CARLA = 3; ARNOLD = 9
      ALICE = 4; RONA = 10
      IRA = 5; CELIA = 11

      CARLA and CLARA can swap positions to give a second layout.

      And the tables can be mirrored (go round the table anti-clockwise, instead of clockwise) to give further viable layouts.

      Like

  • Unknown's avatar

    Jim Randell 4:43 pm on 4 March 2022 Permalink | Reply
    Tags:   

    Teaser 3102: Jokers 

    From The Sunday Times, 6th March 2022 [link] [link]

    A group of us wanted to play a card game. We had a standard 52-card pack but we needed to deal out a whole pack with each person getting the same number of cards, so I added just enough “jokers” to make this possible. Then I randomly shuffled the enlarged pack (in this shuffled pack there was more than a 50:50 chance that there would be at least two jokers together). Then I dealt the cards out, each of us getting the same number (more than three). There was more than a 50:50 chance that my cards would not include a joker.

    How many of us were there?

    [teaser3102]

     
    • Jim Randell's avatar

      Jim Randell 7:04 pm on 4 March 2022 Permalink | Reply

      I think I’ve got the probability calculations right.

      If there are n numbers and we choose k of them, then there are C(n, k) ways of doing this.

      And if we consider k-tuples of non-adjacent numbers, we can use the following map:

      (n[1], n[2], n[3], …, n[k]) ↔︎ (n[1], n[2] − 1, n[3] − 2, …, n[k] − k + 1)

      to put them into 1-1 correspondence with k tuples from (n − k + 1) numbers.

      So there are C(n − k + 1, k) of them. (See: Enigma 1029).

      So, when we think about n non-joker cards and j jokers, the probability of a non-adjacent shuffle is:

      C((n + j) − j + 1, j) / C(n + j, j) = C(n + 1, j) / C(n + j, j)

      And the probability of a hand of k cards not containing a joker is:

      (n / (n + j)) × ((n − 1) / (n + j − 1)) × … × ((n − k + 1) / (n + j − k + 1))

      The following Python program runs in 52ms. (Internal runtime is 229µs).

      from enigma import (Rational, irange, inf, divisors_pairs, multiply, C, printf)

Q = Rational()
h = Q(1, 2)

def solve(N=52):
  # consider number of jokers added to the pack (at least 2)
  for j in irange(2, inf):
    # total number of cards in the pack
    n = N + j

    # probability of adjacent jokers is > 50%
    Pa = 1 - Q(C(N + 1, j), C(n, j))
    if not (Pa > h): continue

    # number of players k is a divisor of n; number of cards per player = p
    for (k, p) in divisors_pairs(n, every=1):
      if p < 4: break
      if N % k + j != k: continue

      # probability of a hand of p cards _not_ having a joker
      Ph = multiply(Q(N - i, n - i) for i in irange(0, p - 1))
      if not (Ph > h): continue

      # output solution
      printf("j={j} n={n}; k={k} p={p}; P(adj)={Pa:.3f} P(hand)={Ph:.3f}", Pa=float(Pa), Ph=float(Ph))
      return

solve()

      Solution: There were 15 in the group.

      Which required 8 jokers adding to a standard pack, to make 60 cards in total. So each player receives 4 cards in the deal.

      The probability of no 2 jokers being adjacent when the cards are shuffled is:

      C(53, 8) / C(60, 8) = 886322710 / 2558620845 ≈ 34.64%

      So it is more likely that there will be at least one pair of adjacent jokers in the shuffled pack.

      And the probability of an individual hand of 4 cards not including a joker is:

      (52/60) × (51/59) × (50/58) × (49/57) ≈ 55.52%

      I also wrote code to simulate 1 million random trials with 52 non-joker cards and 8 jokers.

      import random
from enigma import (Record, irange, join, fdiv, printf)

# run N trials
def run(N):

  # 52 non-jokers + 8 jokers
  cards = ('N' * 52) + ('J' * 8)

  # t = number of trials
  # a = number of shuffles with adjacent jokers
  # h = number of hands _not_ having a joker
  r = Record(t=0, a=0, h=0)

  # run a trial
  def trial(r):
    cs = list(cards)
    # shuffle the cards
    random.shuffle(cs)
    cs = join(cs)
    # collect stats
    r.t += 1
    if 'JJ' in cs: r.a += 1
    if 'J' not in cs[:4]: r.h += 1

  # run the trials
  for _ in irange(N):
    trial(r)

  # output results
  printf("{r.t} trials: adj = {r.a} ({a:.1%}), hand = {r.h} ({h:.1%})", a=fdiv(r.a, r.t), h=fdiv(r.h, r.t))

# run 1 million trials
run(1000000)

      The output of a typical run is:

      1000000 trials: adj = 654261 (65.4%), hand = 555384 (55.5%)

      Which match the calculated probabilities above.

      Like

      • Jim Randell's avatar

        Jim Randell 9:17 am on 5 March 2022 Permalink | Reply

        Using the same probability formulae, it is perhaps a bit neater to start by considering the number of players.

        from enigma import (Rational, irange, inf, ediv, C, multiply, printf)

Q = Rational()
h = Q(1, 2)

def solve(N=52):
  # consider number of players k
  for k in irange(3, inf):
    # how many extra jokers do we need? (at least 2)
    j = -N % k
    if j < 2: continue

    # n = total number of cards
    # p = number of cards per player
    n = N + j
    p = ediv(n, k)
    if p < 4: continue

    # probability of adjacent jokers is > 0.5
    Pa = 1 - Q(C(N + 1, j), C(n, j))
    if not (Pa > h): continue

    # probability of a hand of p cards _not_ containing a joker is > 0.5
    Ph = multiply(Q(N - i, n - i) for i in irange(0, p - 1))
    if not (Ph > h): continue

    # output (and return solution)
    printf("k={k} j={j} n={n} p={p}; P(adj)={Pa:.3f} P(hand)={Ph:.3f}", Pa=float(Pa), Ph=float(Ph))
    yield (k, j, n, p)

# find the first solution
for _ in solve():
  break

        Like

      • Tony Brooke-Taylor's avatar

        Tony Brooke-Taylor 5:01 pm on 7 March 2022 Permalink | Reply

        I am still working through understanding your probability calculations (my problem) but I can confirm that a long-hand calculation of all possible deals produces the same P(adjacent jokers) as in your solution… in about 10 minutes.

        For small numbers of jokers relative to non-jokers, I think you can get away with approximating each pair as an independent sample of two cards from the expanded pack (with replacement). I don’t think this is quicker computationally, but it is easier to get my head around.

        Alternatively, by observing how P(no jokers in my hand) and P(adjacent jokers dealt) change with respect to the number of jokers, one might be able to infer the solution after calculating all possible joker counts that meet the P(no jokers in my hand) condition.

        Like

  • Unknown's avatar

    Jim Randell 8:57 am on 3 March 2022 Permalink | Reply
    Tags:   

    Teaser 2874: An age-old progression 

    From The Sunday Times, 22nd October 2017 [link] [link]

    It is my birthday today — the same day as two of my younger relatives, Betty and Charles. I commented that the digits involved in our three ages are all different. Betty noted that the square of her age is equal to my age multiplied by Charles’s age. Then Charles added that on one of our birthdays in the next ten years the sum of our ages will be one hundred.

    What are our three ages today?

    [teaser2874]

     
    • Jim Randell's avatar

      Jim Randell 8:58 am on 3 March 2022 Permalink | Reply

      We have:

      A > B, C
      B² = A⋅C (i.e. B is the geometric mean of A and C)
      A, B, C digits are all different
      A + B + C + 3n = 100, for some n = 1 .. 10

      We can get an upper bound on B by setting A = B = C:

      A + B + C ≤ 97
      3B ≤ 97
      B ≤ 32

      This Python program finds possible values for A, B, C. It runs in 47ms.

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, is_duplicate, div, printf)

# consider values of B
for B in irange(1, 32):

  # B^2 = A.C; C < A
  for (C, A) in divisors_pairs(B, 2):
    if not (C < B < A): continue

    # calculate n
    n = div(100 - (A + B + C), 3)
    if n is None or n < 1 or n > 10: continue

    # check for repeated digits
    if is_duplicate(A, B, C): continue

    # output solution
    printf("A={A} B={B} C={C}; n={n}")

      The program finds 2 possible solutions:

      B=8; C=1 A=64; n=9
      B=21; C=7 A=63; n=3

      The second of these seems the most likely as Charles joins in the conversation. (Although it would have been nice if the first case had been ruled out explicitly by the puzzle text).

      Solution: Angela is 63. Betty is 21. Charles is 7.

      We have 21² = 441 = 7 × 63 as required.

      And in 3 years time: (63 + 3) + (21 + 3) + (7 + 3) = 100.

      Like

  • Unknown's avatar

    Jim Randell 9:57 am on 1 March 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 907: Snakes & ladders 

    From The Sunday Times, 9th December 1979 [link]

    During my recent trip into the jungle, I came across a clearing, at the centre of which was a stone with the following design:

    On closer inspection, I saw that the small squares were numbered from 1 to 10 (left to right along the bottom row), then from 11 to 20 (right to left on the next row up), 21 to 30 (left to right on the third row up), and so on. The lines joined the following pairs of squares:

    13 & 32
    25 & 48
    35 & 54
    45 & 66
    63 & 88
    79 & 94

    My guide explained that it was a very old snakes and ladders board. However, due to the ravages of time, it was not possible to tell which of the six lines were snakes and which were ladders. Fortunately the guide knew a legend concerning the board, and he told it to me.

    Many years ago, the king of that region had a beautiful daughter, and offered her in marriage to the first man who could get from square 1 to square 100 in just one turn. After many young men had tried and failed, a handsome prince from a neighbouring country had his turn, and threw 12 consecutive sixes. As he stood on square 1 to start, the first six took him to square 7. The remaining sixes took him to square 100.

    Which of the lines are snakes?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    It is also included in the book The Sunday Times Book of Brainteasers (1994).

    [teaser914]

     
    • Jim Randell's avatar

      Jim Randell 10:00 am on 1 March 2022 Permalink | Reply

      We start with 6 linked squares, but we don’t know which way they “teleport”.

      This Python program considers each roll of the dice, and progresses the player. If we reach an “unassigned” linked square we try both possible directions of teleportation. It runs in 49ms.

      Run: [ @replit ]

      from enigma import update, delete, printf

# the linked squares
links = [(13, 32), (25, 48), (35, 54), (45, 66), (63, 88), (79, 94)]

# make a dict of potential "teleports"
ps = dict()
for (x, y) in links:
  ps[x] = y
  ps[y] = x

# play the game
# rs = remaining dice rolls
# ps = potential teleports (src -> tgt)
# ts = actual teleports (src -> tgt)
# n = current position
def solve(rs, ps, n=1, ts=dict()):
  # are we done?
  if not rs:
    if n == 100:
      yield (ts, ps)
  else:
    # add in the next roll
    n += rs[0]
    if n > 100: n = 100
    n = ts.get(n, n)
    # is it a potential teleport?
    t = ps.get(n)
    if t is not None:
      ps_ = delete(ps, [n, t])
      # choose to teleport
      yield from solve(rs[1:], ps_, t, update(ts, [(n, t)]))
      # choose not to teleport
      yield from solve(rs[1:], ps_, n, update(ts, [(t, n)]))
    else:
      # move on
      yield from solve(rs[1:], ps, n, ts)

# solve for a finish in 12 throws of 6
for (ts, ps) in solve([6] * 12, ps):
  for (s, t) in sorted(ts.items()):
    printf("{s} -> {t} {x}", x=("snake" if t < s else "ladder"))
  printf("remaining = {ps}")
  printf()

      Solution: The lines (32 → 13) and (66 → 45) are snakes.

      And the rest are ladders.

      So play proceeds:

      (6) 1 → 7
      (6) 7 → 13
      (6) 13 → 19
      (6) 19 → 25 (ladder) → 48
      (6) 48 → 54
      (6) 54 → 60
      (6) 60 → 66 (snake) → 45
      (6) 45 → 51
      (6) 51 → 57
      (6) 57 → 63 (ladder) → 88
      (6) 88 → 94
      (6) 94 → 100

      Like

  • Unknown's avatar

    Jim Randell 9:56 am on 27 February 2022 Permalink | Reply
    Tags: by: N. M. Smith   

    A Holiday Brain Teaser: Mental arithmetic 

    From The Sunday Times, 3rd August 1958 [link]

    “My wife and I have two nieces staying with us”, said the Professor to his Assistant. “Yesterday, at lunch, I noticed that the sum of the ages of the three ladies was exactly twice your age; and, the product of their ages was 2,450. I am talking, by the way, only in terms of whole numbers of years. Can you tell me how old my nieces are?”

    After a few moments’ thought, the Assistant said, “You have not given me quite enough information”.

    “You are right”, said the Professor. But when I tell you that the luncheon was to celebrate my birthday, and that I was the oldest of the four present, you have all the information you need”.

    How old were the Professor, and his wife?

    This one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. A prize of £5 was offered.

    [teaser-1958-08-03] [teaser-unnumbered]

     
    • Jim Randell's avatar

      Jim Randell 9:58 am on 27 February 2022 Permalink | Reply

      We can look for decompositions of 2450 into three (reasonable) factors, and we are looking for decompositions that give the same even sum (which is twice the assistant’s age).

      The assistant (presumably) knows his own age, but we can work it out, because there is only one viable age that gives multiple decompositions.

      Knowing the professor is the oldest must allow us to eliminate all but one of the candidate ages. This means the professors age must be more than the largest factor in the first candidate (sorted by largest factor = wife’s age) and not more than the largest factor in the second candidate (otherwise that would become a possibility).

      This Python program runs in 47ms.

      Run: [ @replit ]

      from enigma import (divisors_tuples, div, Record, group, attr, printf)

# generate possible ages (nieces = a, b, wife = c, assistant = d)
def generate():
  for (a, b, c) in divisors_tuples(2450, 3):
    if c > 120: continue
    d = div(a + b + c, 2)
    if d is None: continue
    yield Record(a=a, b=b, c=c, d=d)

# group ages together by assistant's age (d)
d = group(generate(), by=attr('d'))

# find d values that are ambiguous
for (k, vs) in d.items():
  if len(vs) < 2: continue
  # sort the values by wife's age (c)
  vs.sort(key=attr('c'))
  # the answer must be the first record
  r = vs[0]
  # professor's age must be larger than wife's age in first record,
  # and not more than wife's age in second record
  prof = [r.c + 1, vs[1].c]
  printf("assistant={k} -> wife={r.c} prof={prof} [nieces=({r.a}, {r.b})]")

      Solution: The professor is 50. His wife is 49.

      And the nieces are 5 and 10. The assistant is 32.

      Like

  • Unknown's avatar

    Jim Randell 4:26 pm on 25 February 2022 Permalink | Reply
    Tags:   

    Teaser 3101: Lap progression 

    From The Sunday Times, 27th February 2022 [link] [link]

    In a charity fundraising drive, two friends completed laps of their local track. Alan, a cyclist, raised £1 for his first lap, £2 for the second, £3 for the third and so on, with each extra lap earning £1 more than the prior. Bob, who walks, raised £1 for his first lap, £2 for the second, £4 for the third and so on, with each extra lap earning double the prior. Starting together, they travelled at constant speeds, and finished their last lap simultaneously.

    After they had added up their totals, they were surprised to find they each raised an identical four-figure sum.

    Including the beginning and end of their drive, how many times did Alan and Bob cross the lap start-finish line together?

    [teaser3101]

     
    • Jim Randell's avatar

      Jim Randell 5:28 pm on 25 February 2022 Permalink | Reply

      We are looking for 4-digit numbers that are both triangular and one less than a power of 2.

      This Python program runs in 46ms.

      Run: [ @replit ]

      from enigma import (irange, inf, is_triangular, gcd, printf)

# consider powers of 2
p = 1
for n in irange(1, inf):
  p *= 2
  t = p - 1
  # we are looking for a 4-digit total
  if t < 1000: continue
  if t > 9999: break
  # that is also triangular
  r = is_triangular(t)
  if r is None: continue
  # calculate number of coincident boundaries
  g = gcd(n, r) + 1
  printf("{t} = 2^({n})-1 = T[{r}] -> {g} times")

      Solution: Alan and Bob were together at the start/finish line 7 times.

      Manually:

      There are only four 4-digit numbers that are 1 less than a power of 2:

      1023 = 2^10 − 1
      2047 = 2^11 − 1
      4095 = 2^12 − 1
      8191 = 2^13 − 1

      The triangular root of a number is given by trirt(x) = (√(8x + 1) − 1) / 2, and can be easily calculated for these 4 numbers:

      trirt(1023) = 44.735…
      trirt(2047) = 63.486…
      trirt(4095) = 90
      trirt(8191) = 127.493…

      Hence the solution occurs when Bob completes 12 laps and Alan 90 laps.

      We can then calculate the number of times they are at the start/finish together:

      gcd(12, 90) + 1 = 7

      The puzzle also works (but with a different answer) if Bob’s progression is the odd numbers, 1, 3, 5, 7, 9, ….

      Like

    • GeoffR's avatar

      GeoffR 12:22 pm on 2 March 2022 Permalink | Reply 

      
% A Solution in MiniZinc
include "globals.mzn";

% Four figure sums for Alan and Bob
var 1000..9999:A;  
var 1000..9999:B;

var 45..140:a; % triangular number range
var 10..13:b;  % power of 2 range
var 1..13:laps; % times crossing start/finish line together

constraint A == a * (a + 1) div 2 ;
constraint B =  pow(2, b) - 1 ;
constraint A == B;

% reusing Hakan's GCD Function
function var int: gcd(var int: x, var int: y) =
  let {
    int: p = min(ub(x),ub(y));
    var 1..p: g;
    constraint
       exists(i in 1..p) (
          x mod i = 0 /\ y mod i = 0
          /\
          forall(j in i+1..p) (
             not(x mod j = 0 /\ y mod j = 0)
          ) /\ g = i);
  } in g;
  
% Times Alan and Bob cross the lap start-finish line together
constraint laps == gcd(a, b) + 1;

solve satisfy;

output ["No. of coincident start/finish crossings = " ++ show(laps)];

      Liked by 1 person

  • Unknown's avatar

    Jim Randell 9:48 am on 24 February 2022 Permalink | Reply
    Tags:   

    Teaser 2846: Bingo! 

    From The Sunday Times, 9th April 2017 [link] [link]

    The infant teacher played a bingo game with his class. He had two identical dice, the numbers on the six faces of each being 1, 2, 2, 3, 3 and 3. He told the class that he would throw the pair of dice, add up the two numbers showing, and call that number out in a game of bingo. He then asked each member of the class to make their own bingo card consisting of five numbers of their own choice. He explained that they could use a number more than once on their card if they wished (and then delete just one occurrence of the number whenever it was called). Most of the class chose the five possible different totals as their bingo numbers, but one very clever girl chose the best possible selection.

    What were her five numbers?

    [teaser2846]

     
    • Jim Randell's avatar

      Jim Randell 9:51 am on 24 February 2022 Permalink | Reply

      When this puzzle was originally published it was suggested by several people on the Sunday Times Discussion Group that as 5 was the most likely outcome on each throw, then the best choice was (5, 5, 5, 5, 5). However, I wasn’t convinced.

      I considered a scenario where the class was sufficiently large that every possible bingo card was in play. In that case one of the cards would win after 5 throws of the dice, so we can generate all possible sequences of 5 throws and see which card is most likely to win.

      The card (5, 5, 5, 5, 5) can only win if every one of the throws is a 5, giving a (1/3)^5 = 1/243 = 0.4% chance. And there are 126 possible bingo cards, so there must be cards that have a better chance of winning.

      The following Python program examines all possible sequences of 5 throws, and it suggests a different answer for the best choice. It runs in 54ms.

      from enigma import (multiset, subsets, ordered, multiply, fdiv, printf)

# n = number of throws
n = 5

# the scores on the die
die = (1, 2, 2, 3, 3, 3)

# find possible throws with a pair of dice
throws = multiset.from_seq(a + b for (a, b) in subsets(die, size=2, select="M"))

# consider each sequence of n throws
r = multiset()
for ns in subsets(sorted(throws.keys()), size=n, select="M"):
  r.add(ordered(*ns), count=multiply(throws[k] for k in ns))

# output the 10 most common sequences
best = r.most_common(10)
N = pow(len(die), 2 * n)
for (k, v) in best:
  printf("{k} -> {v} [{f:.1%}]", f=fdiv(v, N))
printf()

# output interesting patterns
for k in [(5, 5, 5, 5, 5), (2, 3, 4, 5, 6), best[0][0]]:
  printf("{k} -> {v} [{f:.1%}]", v=r[k], f=fdiv(r[k], N))

      In this scenario a choice of (5, 5, 5, 5, 5) is a poor choice (in 51st place), it would only be successful 0.4% of the time (as expected). A choice of (2, 3, 4, 5, 6) fares better at 0.9% (in 35th place). However the clear winner is a choice of (4, 4, 5, 5, 6) which wins 6.4% of the time.

      (I also ran 100 million random trials with 5 throws of the dice, and got results which matched the program above).

      Solution: Her five numbers were (4, 4, 5, 5, 6).

      Another way to analyse the problem is to consider each bingo card in isolation, and calculate the number of expected throws of the dice before it wins. (i.e. On average how many throws of the dice would it take).

      We can model the problem using an absorbing Markov chain [ @wikipedia ] which allows us to calculate the expected number of steps (i.e. throws of the dice), before being absorbed (i.e. completing the bingo card).

      The set of states are the stages of completion of the bingo card, and we can fill out the transition matrix with the probabilities of a transition between states at each throw of the dice. We can then manipulate the matrix to determine the expected number of steps between the transient states (partially completed bingo card) and the absorbing state (completed bingo card). And we want the number of steps from the initial transient state (i.e. the empty bingo card).

      This Python program calculates the expected number of sets for all 126 possible bingo cards, it runs in 177ms.

      from enigma import (Rational, multiset, subsets, irange, find, Matrix, unpack, printf)

Q = Rational()

# the values on a die
die = (1, 2, 2, 3, 3, 3)

# find distribution of possible throws
throws = multiset.from_seq(a + b for (a, b) in subsets(die, size=2, select="M"))

# denominator for throws
td = throws.size()

# calculate expected number of throws for target <tgt>
def expected(tgt):
  # the states are subsets of the winning card
  m = multiset(tgt)
  ss = sorted(m.subsets(), key=(lambda x: (len(x), tuple(x))))
  ns = len(ss)

  # construct the transition matrix A = -P
  A = Matrix.create(ns, ns, 0, field=Q)

  # consider possible states
  for (i, src) in enumerate(ss):
    # and each throw
    for (x, p) in throws.items():
      # from src where does throw x get us?
      t = src.copy().add(x)
      j = find(ss, t)
      if j == -1: j = i
      A[i][j] -= Q(p, td)

  # convert to A = I - Q
  A.pop(-1)
  for (i, r) in enumerate(A):
    r[i] += 1
    r.pop(-1)

  # find the expected number of steps from each transient state
  E = A.linear_solve(1)
  # return expected number of steps from the initial state
  return E[0]


# consider possible bingo cards with 5 numbers
r = dict()
for tgt in subsets(throws.keys(), size=5, select="R"):
  # find expected number of throws for this card
  r[tgt] = expected(tgt)

# output lowest 10 expectation values
for (i, (tgt, e)) in enumerate(sorted(r.items(), key=unpack(lambda t, e: e))):
  if i == 10: break
  printf("{tgt} -> {f:.3f}", f=float(e))
printf()

# output interesting patterns
for k in [(5, 5, 5, 5, 5), (2, 3, 4, 5, 6), (4, 4, 5, 5, 6)]:
  printf("{k} -> {f:.3f}", v=r[k], f=float(r[k]))

      Using this measure (4, 4, 5, 5, 6) is again the winner, with 9.8 expected steps. (2, 3, 4, 5, 6) comes out at 38.2 steps (in 67th place), and (5, 5, 5, 5, 5) is 15.0 steps (in 28th position).

      (Again a simulation also gives matching results).

      Note that the ordering of “best” bingo cards differs depending on which measure you use, although the “best possible” card is the same in both scenarios.

      Here is a comparison of the top 10 bingo cards produced by the analyses above:

      In reality, the scenario is somewhere between these two approaches. It’s probably not the case that all 126 possible cards are in play (so the game might last longer than exactly 5 throws), but there is definitely more than 1 card in play (as most of the class chose (2, 3, 4, 5, 6)).

      If we know what cards are in play we can analyse the probability of one card winning before the others, as we have done before in puzzles that are variants on Penney’s game [ @wikipedia ]. (See: Enigma 630, Tantalizer 428, Enigma 287).

      Or we can use simulations to look at how a set of cards performs. I wrote code to play random trials for a group of cards until there is a winner.

      Playing A = (4, 4, 5, 5, 6) against B = (2, 3, 4, 5, 6) results in A winning 86.7% of the time, and B winning 15.9% of the time. (These add up to more than 100% because both cards can win on the final throw).

      Although playing C = (5, 5, 5, 5, 5) against B, shows that C is a better choice than B. With C winning 74.6% of the time, and B winning 25.4% of the time.

      Playing the top 3 performing cards from the analyses, (4, 4, 5, 5, 6), (4, 5, 5, 6, 6), (4, 5, 5, 5, 6), against (2, 3, 4, 5, 6) and (5, 5, 5, 5, 5) we get:

      (4, 4, 5, 5, 6) wins 47.5%
      (4, 5, 5, 6, 6) wins 42.9%
      (4, 5, 5, 5, 6) wins 25.0%
      (5, 5, 5, 5, 5) wins 10.5%
      (2, 3, 4, 5, 6) wins 10.1%

      Like

    • Jim Randell's avatar

      Jim Randell 4:11 pm on 22 September 2022 Permalink | Reply

      I found an article on the Royal Institution’s web site (or on an archive of it – [@archive.org]), where the setter of this puzzle is quoted:

      I wanted an interactive probability game to play with children. I wanted the game to reward good play i.e. a child who chose the best bingo card had a good chance of winning. I know from experience a lot of children (and adults, as evidenced by the response to the Sunday Times teaser!) choose all five numbers the same and choose the number that is most likely. In this case a lot of children opt for (5, 5, 5, 5, 5)  and the rest tend to opt for (2, 3, 4, 5, 6). Essentially I wanted a game where I could ask the winner ‘Why did you choose those numbers?’ and elicit an interesting response from the child that the rest of the group would find enlightening. The teaser printed by the Sunday Times was true except for the fact that the child in question was 9 years old.

      But he doesn’t reveal how either he or the 9-year-old arrived at the best solution.

      However, I did wonder if it is valid to construct an optimal card with (n + 1) numbers by adding a number to an optimal card with n numbers.

      Then using the “Win in n throws” method (rather than the Markov chains) we can quickly (and relatively easily) construct a card with 5 numbers (and also much larger cards).

      The code is as follows:

      from enigma import (multiset, subsets, append, Accumulator, arg, printf)

# number of boxes on the card
N = arg(5, 0, int)

# the values on a die
die = (1, 2, 2, 3, 3, 3)

# find distribution of possible throws (with 2 dice)
throws = multiset.from_seq(a + b for (a, b) in subsets(die, size=2, select="M"))

# construct the best sequence for an <n> throw game
(n, ts) = (0, multiset())
while n < N:
  # find the best next throw
  r = Accumulator(fn=max)
  for (t, v) in throws.items():
    ts_ = append(ts, t)
    r.accumulate_data(v * ts_.multinomial(), ts_)
  (n, ts) = (n + 1, r.data)
  printf("{n} -> {ts}", ts=list(ts.sorted()))

      Using this program we find the best choice for bingo cards with 1 – 5 numbers are:

      1 → [5]
      2 → [4, 5]
      3 → [4, 5, 6]
      4 → [4, 5, 5, 6]
      5 → [4, 4, 5, 5, 6]

      As you would expect, for 1 number [5] is the best choice, as it is the most likely number to come up.

      But as soon as we move on to 2 numbers, we see that choosing another 5 is suboptimal.

      And this is because when 2 dice are thrown there is only one way to get [5, 5], and that is if each throw is a 5. The probability of this happening is (1/3)×(1/3) = 1/9 = 11.1%.

      But by choosing [4, 5] there are two ways this could be achieved – a 4 then a 5, or a 5 then a 4. And the probability of this happening is (5/18)×(1/3) + (1/3)×(5/18) = 5/27 = 18.5%.

      And so [4, 5] is better choice than [5, 5].

      Like

      • Jim Randell's avatar

        Jim Randell 4:45 pm on 20 October 2022 Permalink | Reply

        This puzzle was also published in Significance magazine (from The Royal Statistical Society) in the December 2021 issue [@link] (with the solution appearing in the February 2022 issue).

        I was able to get access to the online version of the magazine via my local library.

        Extract from Significance, February 2022, p8:

        The answer we were looking for is 4, 4, 5, 5, 6. We’ll hand over to reader Richard Jenkins to explain the solution.

        “Each time the dice are rolled, there are five possible outcomes (sums) with the following probabilities:

        P(sum is 2) = 1/36
        P(sum is 3) = 1/9
        P(sum is 4) = 5/18
        P(sum is 5) = 1/3
        P(sum is 6) = 1/4.

        Even though a sum of 5 has the highest probability on any single roll of the dice, it is very unlikely that a sum of 5 will be rolled each time when the dice are rolled multiple times. It is more likely that a variety of sums will appear”.

        This is an important point. Many readers wrote in to suggest a bingo card of 5, 5, 5, 5, 5. But, as Kyla E. Chasalow and Scott D. Chasalow explain in their submission – a detailed, eight-page tour de force of a solution – choosing all 5s “fails to take into account that bingo cards are unordered”. Roll the dice five times and there are 120 different roll sequences that will yield a win for the card 2, 3, 4, 5, 6. But there is only one way to win with a card of 5s.

        Back to Jenkins: “By reviewing the various combinations, we see there are 126 possible bingo cards (since the order of the numbers on the card does not matter). But which bingo card is the most likely to match all numbers in exactly five rolls? By crunching the numbers, I found that the combination of 4, 4, 5, 5, 6 has the highest probability of success”.

        Jenkins gives the four bingo cards with the highest probabilities of winning in five rolls as:

        P(4, 4, 5, 5, 6) = 0.064300412
        P(4, 5, 5, 6, 6) = 0.05787037
        P(3, 4, 5, 5, 6) = 0.051440329
        P(4, 5, 5, 5, 6) = 0.051440329

        Chasalow and Chasalow also identify 4, 4, 5, 5, 6 as the bingo card with the highest overall probability of winning in five rolls, explaining that: “This card reflects a trade-off between choosing high-probability outcomes and choosing different outcomes so that there are more ways to win”.

        — The Royal Statistical Society 2022

        Like

  • Unknown's avatar

    Jim Randell 11:26 am on 22 February 2022 Permalink | Reply
    Tags: by: Dr A Alan Taylor   

    Brain-Teaser 673: Crux numerorum 

    From The Sunday Times, 9th June 1974 [link]

    Professor Digby-Nite was excavating near Hadrian’s Wall last summer when he came across a clay tablet inscribed with this diagram and the words “CRUX NUMERORUM”.

    The clues when translated read:

    Across:
    I. Multiple of XXXVII.
    II. Multiple of LXXIII.
    III. A non-prime factor of I down.

    Down:
    I. A square.
    II. Multiple of VII.
    III. Calpurnia’s age.

    How old was Calpurnia?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    [teaser673]

     
    • Jim Randell's avatar

      Jim Randell 11:26 am on 22 February 2022 Permalink | Reply

      The grid is (of course) to be completed using Roman numerals.

      The following Python program runs in 50ms.

      Run: [ @replit ]

      from enigma import (int2roman, roman2int, irange, divisors, is_prime, catch, printf)

# find length k romans
def romans(ns, k=3):
  for n in ns:
    r = int2roman(n)
    if len(r) == k:
      yield r

# multiples for i across
n = roman2int('XXXVII')
m1as = list(romans(irange(n, 5000, step=n)))

# multiples for ii across
n = roman2int('LXXIII')
m2as = list(romans(irange(n, 5000, step=n)))

# multiples for ii down
n = roman2int('VII')
m2ds = list(romans(irange(n, 5000, step=n)))

# squares
sqs = list(romans(i * i for i in irange(1, 70)))

# i down (= ADG) is a square
for (A, D, G) in sqs:

  # ii across is a multiple of 73
  for (D_, E, F) in m2as:
    if D_ != D: continue

    # i across is a multiple of 37
    for (A_, B, C) in m1as:
      if A_ != A: continue

      # ii down is a multiple of 7
      for (B_, E_, H) in m2ds:
        if B_ != B or E_ != E: continue

        # iii across is a non-prime factor of i down
        for (G_, H_, I) in romans(d for d in divisors(roman2int(A + D + G)) if not is_prime(d)):
          if G_ != G or H_ != H: continue

          # answer (must be valid roman)
          ans = catch(roman2int, C + F + I)
          if ans is None: continue

          # output solution
          printf("ans = {ans} [{A} {B} {C} / {D} {E} {F} / {G} {H} {I}]")

      Solution: Calpurnia is 19.

      The completed grid looks like this:

      Like

      • Jim Randell's avatar

        Jim Randell 1:54 pm on 22 February 2022 Permalink | Reply

        Manually:

        There is only one length 3 multiple of 73 (for II across):

        DXI = 511 = 7×73

        And there are only three length 3 squares (for I down):

        XVI = 16 = 4²
        XXV = 25 = 5²
        MDC = 1600 = 40²
        MMD = 2500 = 50²

        Of these, only MDC interlocks with DXI.

        There are only three length 3 multiple of 37 (for I across):

        CXI = 111 = 3×37
        DLV = 555 = 15×37
        MCX = 1110 = 30×37

        Of these, only MCX interlocks with MDC.

        Which leaves II down = “a multiple of VII” that matches “CX_”, it must be:

        CXL = 140 = 20×7

        And III across = “a non-prime divisor of 1600”, that matches “CL_”, it must be:

        CLX = 160 = 1600 / 10

        The grid is now complete and III down = XIX = 19.

        Like

  • Unknown's avatar

    Jim Randell 10:24 am on 20 February 2022 Permalink | Reply
    Tags: by: F. V. Rowden,   

    Brain-Teaser: Saturday’s child 

    From The Sunday Times, 22nd December 1957 [link]

    “How old are you, John?”, I asked my friend. He replied: “My father, his elder brother and I were all born in the summer, and we were all born on the same day of the week. Although our anniversaries are on different dates, this year they all fell on a Saturday”.

    “That’s very interesting”, I said, “but it isn’t very helpful, is it?”

    “It should be helpful”, said John, “because when I tell you that the years of our birth are all prime numbers there is no possible doubt about my age”.

    After argument, John convinced me he was right.

    How old are John, his father and his uncle?

    This one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. A prize of £5 was offered.

    [teaser-1957-12-22] [teaser-unnumbered]

     
    • Jim Randell's avatar

      Jim Randell 10:25 am on 20 February 2022 Permalink | Reply

      The following Python program runs in 47ms.

      from datetime import (date, timedelta)
from enigma import (defaultdict, primes, subsets, printf)

# consider possible prime birth years
years = set(primes.between(1835, 1956))

# find Saturdays in the summer of 1957
d = date(1957, 6, 1)
while d.isoweekday() != 6:
  d += timedelta(days=1)

r = defaultdict(set)
while d.month < 9:
  # record previous years by day of the week
  for y in years:
    b = date(y, d.month, d.day)
    r[b.isoweekday()].add(y)
  d += timedelta(days=7)

for (k, vs) in r.items():
  if len(vs) < 3: continue

  # select 3 birth years (Uncle, Father, John)
  for (U, F, J) in subsets(sorted(vs), size=3):
    # siblings are within 20 years
    if not (F - U < 21): continue
    # John's father is 18-40 years older than him
    if not (17 < J - F < 41): continue
    # output solution
    age = lambda x: 1957 - x
    printf("U = {U} ({u}); F={F} ({f}); J={J} ({j})", u=age(U), f=age(F), j=age(J))

      I found multiple solutions to this puzzle:

      John’s uncle was born in 1861. In 1957 he would be 96.
      John’s father was born in 1867 (6 years later). In 1957 he would be 90.
      John was born in 1889 (22 years later again). In 1957 he would be 68.

      John’s uncle was born in 1861. In 1957 he would be 96.
      John’s father was born in 1867 (6 years later). In 1957 he would be 90.
      John was born in 1901 (34 years later again). In 1957 he would be 56.

      John’s uncle was born in 1861. In 1957 he would be 96.
      John’s father was born in 1867 (6 years later). In 1957 he would be 90.
      John was born in 1907 (40 years later again). In 1957 he would be 50.

      John’s uncle was born in 1873. In 1957 he would be 84.
      John’s father was born in 1879 (6 years later). In 1957 he would be 78.
      John was born in 1913 (34 years later again). In 1957 he would be 44.

      The published solution is that John was 44, his father 78, and his uncle 84. Which is the last of the above solutions.

      If we assume that the actual dates of birth were not on Saturdays, then this is the only remaining solution. However I don’t think the puzzle text can be read to include this additional restriction. (In fact, the title of the puzzle, “Saturday’s child”, implies that they were all born on a Saturday, and so would exclude the final solution).

      This might account for comment given with the solution (5th January 1958):

      “More than 600 readers sent in their solution, but there was a fair proportion of erroneous answers.”

      Like

← Older posts

Newer posts →

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started