Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 5:09 pm on 6 March 2020 Permalink | Reply
    Tags:   

    Teaser 2998: Football league 

    From The Sunday Times, 8th March 2020 [link] [link]

    In our league three points are awarded to a team for a win and one point goes to each team in a drawn match. In each division, the teams play each other twice per season.

    Comparison of the results of the two divisions at the end of last season showed that:

    (a) Division II had one more team than Division I.

    (b) The same total number of points was awarded in each division.

    (c) For the division with the larger number of drawn matches, that number was equal to the number of matches not drawn in the other division.

    (d) The number of drawn matches in one division was a multiple of the (3-digit) number of drawn matches in the other.

    How many teams were in Division II?

    The puzzle text has been reworded slightly to reduce ambiguity.

    [teaser2998]

     
    • Jim Randell's avatar

      Jim Randell 5:54 pm on 6 March 2020 Permalink | Reply

      If there are n teams in a division, and each team plays each other team twice, then the total number of matches played is:

      2 C(n, 2) = n(n − 1)

      So, if Division I has n teams the total number of matches played is:

      t1 = n(n − 1)

      And Division II has n + 1 teams, so the total number of matches played is:

      t2 = (n + 1)n

      These totals are divided into drawn matches and not-drawn matches. If the division with the lower number of drawn matches has x drawn matches (x is a 3-digit number), then the other division has kx draws (where k > 1), and this means the original division has kx not-drawn matches.

      So the total number of matches for the division with the lower number draws is also expressible as (k + 1)x, and the total number of points is:

      pts = 2x + 3kx = (2 + 3k)x

      If the division with the higher number of draws (kx draws) has y not-draws, then we also have:

      pts = 2kx + 3y

      This Python 3 program runs in 73ms.

      Run: [ @repl.it ]

      from enigma import (irange, inf, printf)

# check the total number of matches works
# tl = total number of matches for the division with the fewer draws
# th = total number of matches for the other division
# d = division with fewer draws
# return: (pts, (n1, t1, md1, mn1), (n2, t2, md2, mn2))
def check(d, tl, th, nl, nh):
  # divide the total into (k + 1) and x
  for k in irange(2, inf):
    (x, r) = divmod(tl, k + 1)
    if x < 100: break
    if r > 0 or x > 999: continue
    # calculate the number of points
    pts = (2 + 3 * k) * x
    y = th - k * x
    if 2 * k * x + 3 * y != pts: continue
    # return solution
    s = ((nl, tl, x, k * x), (nh, th, k * x, y))
    yield (pts,) + (s if d == 1 else s[::-1])

# find number of teams in each division
def solve():
  for n in irange(2, inf):
    (t1, t2) = (n * (n - 1), (n + 1) * n)
    yield from check(1, t1, t2, n, n + 1)
    yield from check(2, t2, t1, n + 1, n)

# output the first solution
for (pts, (n1, t1, md1, mn1), (n2, t2, md2, mn2)) in solve():
  printf("pts={pts} -> D1: n={n1} t={t1} md={md1} mn={mn1}; D2: n={n2} t={t2} md={md2} mn={mn2}")
  break

      Solution: There were 20 teams in Division II.

      There were 19 teams in Division I, giving a total of 342 matches. 114 of the matches were drawn, and the remaining 228 were won outright, giving a total number of points of 2×114 + 3×228 = 912.

      The 20 teams in Division II played a total of 380 matches. 228 of the matches were drawn (twice the number of drawn matches in Division I, and the same as the number of not-drawn matches in Division I), and the remaining 152 were won outright, giving a total number of points of 2×228 + 3×152 = 912.

      Like

    • Robert Brown's avatar

      Robert Brown 11:11 am on 7 March 2020 Permalink | Reply

      I found the first solution working by hand on the back of an envelope! But there are many solutions, and I don’t see anything in the text restricting the size of the divisions.

      Like

      • Jim Randell's avatar

        Jim Randell 11:13 am on 7 March 2020 Permalink | Reply

        @Robert: Are you sure you are using all the information? I found there was only one solution (even though my program only outputs the first solution it finds, but I did have it check for divisions with up to 5000 teams).

        Like

        • Jim Randell's avatar

          Jim Randell 12:02 pm on 7 March 2020 Permalink | Reply

          Some analysis allows us to fully explore the solution space, and confirm that there is only a single solution.

          We can derive the following expressions for x and k:

          x = n (n − 7) / 2
          k = (n + 5) / (n − 7)

          The values for n are thus limited by the acceptable values for x and k.

          Here is a Python 3 program that determines possible values for n:

          from enigma import (irange, inf, div, printf)

for n in irange(8, inf):
  x = div(n * (n - 7), 2)
  if x < 100: continue
  if x > 999: break
  k = div(n + 5, n - 7)
  if k is None or k < 2: continue
  (t1, t2) = ((n - 1) * n, n * (n + 1))
  printf("pts={(2 + 3 * k) * x} -> D1: n={n} t={t1} md={x} mn={k * x}; D2: n={n + 1} t={t2} md={k * x} mn={t2 - k * x}")

          Or the solution can be determined analytically:

          Restricting the value of n to positive integers, we have the following:

          x is a 3-digit number:

          100 ≤ n (n − 7) / 2 ≤ 999
          19 ≤ n ≤ 48

          k is a non-trivial integer multiplier:

          (n + 5) / (n − 7) ≥ 2
          n ≤ 19

          From which we see there is only a single possible value for n, which gives us the solution, and the values of the other parameters can be calculated.

          Like

    • GeoffR's avatar

      GeoffR 11:09 am on 8 March 2020 Permalink | Reply 

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

var 1..50: Nteams;   % Division 2 teams
var 1..50: Mteams;   % Division 1 teams

var 100..999: Nnon_draw; var 100..999: Ndraw;
var 100..999: Mnon_draw; var 100..999: Mdraw;

% Number of matches for both divisions
constraint  Nteams * (Nteams - 1) == Nnon_draw + Ndraw;
constraint  Mteams * (Mteams - 1) == Mnon_draw + Mdraw;

% (a) Division 2 held one more team than Division I
constraint Nteams == Mteams + 1;

% (b) The same total number of points was awarded in each division
constraint Mnon_draw * 3 + Mdraw * 2 = Nnon_draw * 3 + Ndraw * 2;

% (c) For the division with the larger number of draws (drawn matches), 
% that number was equal to the number of matches not drawn in the other division.
constraint  Ndraw == Mnon_draw;

% (d) The number of draws in one division was a multiple 
% of the (3-digit) number of draws in the other
constraint Mdraw mod Ndraw == 0 \/ Ndraw mod Mdraw == 0; 

solve satisfy;

output [ "Division 2 teams = " ++ show(Nteams) ++ " No."
++ "\n" ++ "Division 1 teams = " ++ show(Mteams)  ++ " No."
++ "\n" ++ "Div2 draw = " ++ show(Ndraw) ++ ", Div2 non-draw = " ++ show(Nnon_draw) 
++ "\n" ++ "Div1 draw = " ++ show(Mdraw) ++ ", Div1 non-draw = " ++ show(Mnon_draw) 
 ];

      Like

    • Robert Brown's avatar

      Robert Brown 1:46 pm on 8 March 2020 Permalink | Reply

      I had made the classic error of awarding 1 point per draw to each division. As the points are awarded to teams, you get 2 points for every drawn match. Sorry about that!

      Like

  • Unknown's avatar

    Jim Randell 7:30 am on 3 March 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 514: [Picnic buns] 

    From The Sunday Times, 18th April 1971 [link]

    On the occasion of the Early Risers Aquatic Club Easter Regatta, Mrs Perch packed a large picnic hamper, including nine dozen small buns, and dispatched her husband with seven of their children, all of different ages under 17, to enjoy the occasion.

    At lunch time the family party attacked the buns with gusto, but Mr Perch, having eaten more buns than any of the children, felt rather uncomfortable and managed to persuade Mr Fish, the President, to dispose of as many buns as he (Mr Perch) and his oldest child had eaten between them.

    Each of the children had eaten at least one bun, and there were sufficient left for each of the family party to eat another two at tea time and a further three on the journey home, which they dutifully did, returning home with an empty hamper.

    It happened that both after lunch and after tea, two of the children had each consumed three times as many buns and two of the children had consumed twice as many buns as one or other of the other children, and that by the time they arrived home each of the children had eaten exactly as many buns as he was years of age.

    How many buns were given to Mr Fish?

    This puzzle was originally published with no title.

    [teaser514]

     
    • Jim Randell's avatar

      Jim Randell 7:31 am on 3 March 2020 Permalink | Reply

      There are seven children of different ages, less than 17. Each child’s age is also the total number of buns eaten by that child during the day, so the minimum possible value is 6.

      This Python program considers possible ages, and checks that the numbers of buns consumed meet the required conditions. It runs in 70ms.

      from enigma import subsets, irange, div, icount_exactly as icount, printf

# check numbers in the list s (each reduced by d) have exactly 2
# matches that are 2x and 3x other numbers on the list
def check(s, d):
  # calculate the required list
  s = list(x - d for x in s)
  # two must be 3x and two must be 2x other numbers on the list
  return all(icount(s, (lambda x: k * x in s), 2) for k in (2, 3))

# consider possible ages for the children
for s in subsets(irange(6, 16), size=7):
  # so the total number of buns eaten by the children is...
  t = sum(s)
  # the remaining buns are eaten by...
  # the father: x + 5
  # fish: (x + g - 5)
  # giving a total of: 2x + g
  g = s[-1]
  x = div(108 - t - g, 2)
  if x is None or not(x > g - 5): continue

  # the total number of buns eaten by the children after lunch and tea
  if not (check(s, 5) and check(s, 3)): continue

  # calculate the number of buns eaten by fish
  f = x + g - 5
  printf("fish = {f} [father = {x5}; ages = {s}]", x5=x + 5)

      Solution: Mr. Fish ate 21 of the buns.

      The children are aged: 6, 7, 8, 9, 12, 14, 15.

      And this is the total number of buns consumed by them at the end of the day. Accounting for 71 buns in total.

      They each ate 3 buns on the journey home, so after tea the bun tally was: 3, 4, 5, 6, 9, 11, 12.

      We see that two of the children have consumed 3× the number of buns as some other child: 9 (=3× 3), 12 (=3× 4).

      And also two of the children have consumed 2× the number of buns as some other child: 6 (=2× 3), 12 (=2× 6).

      And before that they each had 2 buns at tea time, so after lunch the bun tally was: 1, 2, 3, 4, 7, 9, 10.

      Again we have: 3 (=3× 1), 9 (=3× 3); and: 2 (=2× 1), 4 (=2× 2).

      So the children consumed 71 buns in all, leaving 37 to be accounted for.

      Of these Mr Fish ate 21, this being the same number that the father ate at lunch, plus the number the eldest child ate at lunch (= 10).

      So the father must have eaten 11 buns at lunch (which is more than the eldest child). With the 2 at tea, and 3 on the way home, this brings the fathers total to 16.

      So adding the total number of buns eaten by the children, the father and Mr. Fish we get: 71 + 16 + 21 = 108, exactly 9 dozen (= 9 × 12).

      Like

  • Unknown's avatar

    Jim Randell 5:10 pm on 28 February 2020 Permalink | Reply
    Tags:   

    Teaser 2997: Cemetery lottery symmetry 

    From The Sunday Times, 1st March 2020 [link] [link]

    Our local cemetery conservation lottery tickets have four numbers for a line. Using eight different numbers, my two lines have several symmetries. For each line: just one number is odd; there is one number from each of the ranges 1-9, 10-19, 20-29 and 30-39, in that order; the sum of the four numbers equals that sum for the other line; excluding 1 and the numbers themselves, the 1st and 2nd numbers share just one factor — as do the 2nd and 3rd (a different factor) and the 3rd and 4th (another different factor) and, finally, the 4th and 1st.

    Printed one line directly above the other, my top line includes the largest of the eight numbers.

    What is the bottom line?

    [teaser2997]

     
    • Jim Randell's avatar

      Jim Randell 5:31 pm on 28 February 2020 Permalink | Reply

      This Python program runs in 129ms. (Internal runtime is 65ms).

      Run: [ @replit ]

      from enigma import (defaultdict, irange, subsets, gcd, divisors, intersect, singleton, printf)

# check x and y share a single divisor (not 1, x, y)
def divisor(x, y):
  return singleton(intersect(divisors(n) for n in (x, y)).difference([1, x, y]))

# collect sets of 4 numbers by sum
ns = defaultdict(list)

# consider possible values for the units digits
for (a, b, c, d) in subsets(irange(0, 9), size=4, select="M"):
  # a cannot be 0
  if a == 0: continue
  # only one of them is odd
  if sum(x % 2 == 1 for x in (a, b, c, d)) != 1: continue
  # construct the numbers
  b += 10
  c += 20
  d += 30
  # each consecutive pair shares a single divisor
  s = list(divisor(x, y) for (x, y) in ((a, b), (b, c), (c, d), (d, a)))
  if None in s: continue
  if len(set(s[:3])) != 3: continue

  ns[a + b + c + d].append((a, b, c, d))

# consider possible sums
for (t, vs) in ns.items():
  # choose two lines
  for (p, q) in subsets(vs, size=2):
    if len(set(p + q)) != 8: continue
    # the largest number is on the top line
    if max(q) > max(p): (p, q) = (q, p)
    printf("{p} / {q}")

      Solution: The numbers on the bottom line are: 6, 15, 20, 34.

      The numbers on the top line are: 4, 14, 21, 36.

      These are the only two candidate lines that have the same sum (they both sum to 75).

      There are three other candidate lines, but they all have different sums.

      The full list of candidate lines is:

      sum=69: (4, 14, 21, 30)
      sum=73: (8, 14, 21, 30)
      sum=75: (4, 14, 21, 36) (6, 15, 20, 34)
      sum=79: (6, 15, 20, 38)

      Like

    • Frits's avatar

      Frits 12:26 pm on 24 December 2020 Permalink | Reply 

      from enigma import SubstitutedExpression

# check if four combinations of 2 digits all have one common factor
def one_common_factor(s):
  # build list where nth and (n+1)th entry of <s> have only one common factor
  li = [a[0] for a in list(factors(x, y) for x, y in zip(s, s[1:] + s[:1])) 
        if len(a) == 1]
  # first three numbers in a list of four must be different
  return len(li) == 4 and len(set(li[:3])) == 3
  
# return common factors of <x> and <y> except 1 and numbers it self  
factors = lambda x, y: [i for i in range(2, min(x, y) // 2 + 1) 
                        if x % i == 0 and y % i == 0]
 
# the alphametic puzzle
p = SubstitutedExpression(
  [
  # top line      A, 10 + D, 20 + F, 30 + H
  # bottom line   I, 10 + K, 20 + M, 30 + O
   
  # the sum of the four numbers equals that sum for the other line
  "A + D + F + H == I + K + M + O",
  
  # just one number per line is odd
  "sum(x % 2 == 1 for x in (A, D, F, H)) == 1",
  "sum(x % 2 == 1 for x in (I, K, M, O)) == 1",
  
  # my top line includes the largest of the eight numbers
  "H > O",
  
  # the 1st and 2nd numbers share just one factor as do the 2nd and 3rd 
  # (a different factor) and the 3rd and 4th (another different factor) 
  # and, finally, the 4th and 1st.
  "one_common_factor([A, 10 + D, 20 + F, 30 + H])",
  "one_common_factor([I, 10 + K, 20 + M, 30 + O])",
  
  # eight different numbers
  "A != I",
  "D != K",
  "F != M",
  "H != O",
  ],
  answer="(A, 10 + D, 20 + F, 30 + H), (I, 10 + K, 20 + M, 30 + O)",
  # exclude single digit prime numbers
  d2i=dict([(k, "AI") for k in range(0, 4)] + [(5, "AI")] + [(7, "AI")]),
  env=dict(one_common_factor=one_common_factor),
  distinct="",
  verbose=0)   

# print answers 
for (_, ans) in p.solve():
  print(f"{ans}")
  
# ((4, 14, 21, 36), (6, 15, 20, 34))

      Like

  • Unknown's avatar

    Jim Randell 11:50 am on 27 February 2020 Permalink | Reply
    Tags:   

    Brainteaser 1785: Back to front 

    From The Sunday Times, 1st December 1996 [link]

    Given a row of eleven playing cards:

    [J] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]

    I wish to reverse the order to give:

    [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [J]

    To do this we are allowed at any stage to make a “move” of the following type:

    remove any section of adjacent cards from the pack and move them elsewhere.

    For example, one possible move from the starting position would be to take:

    [9] [8] [7]

    and move it to the right to give:

    [J] [10] [6] [5] [9] [8] [7] [4] [3] [2] [1]

    What is the minimum number of moves required to reverse them?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book and differs slightly from the original puzzle.

    [teaser1785]

     
    • Jim Randell's avatar

      Jim Randell 11:51 am on 27 February 2020 Permalink | Reply

      (See also: Puzzle #32).

      We can measure the “disorderedness” of a list by going through it and looking how each element compares to the next element. If it is less than the next element, then it is “ordered”. If it is greater than the next element, then it is “disordered”.

      Looking at the initial list we have:

      [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

      which gives the following pairs:

      (11, 10) (10, 9) (9, 8) (8, 7) (7, 6) (6, 5) (5, 4) (4, 3) (3, 2) (2, 1)

      all of which are disordered, giving the initial list a score of 10.

      The target list is:

      [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

      which gives the following pairs:

      (1, 2) (2, 3) (3, 4) (4, 5) (5, 6) (6, 7) (7, 8) (8, 9) (9, 10) (10, 11)

      all of which are ordered, give the target list a score of 0.

      Suppose the list is:

      [? … a] [b … c] [d … e] [f … ?]

      And we move the [b … c] section to between e and f.

      Then we end up with

      [? … a] [d … e] [b … c] [f … ?]

      In the process we lose the adjacent pairs (a, b) (c, d) (e, f) and we gain the adjacent pairs (a, d) (e, b) (c, f).

      So the best improvement we could hope for is if the first three pairs are disordered, and the second three pairs are ordered, then we has reduced the disorderedness score by 3.

      For this to happen we need:

      a > b
      c > d
      e > f

      and:

      a < d
      e < b
      c < f

      We can write all six inequalities as the following chain:

      a < d < c < f < e < b < a

      So it is not possible for all the inequalities to hold simultaneously. So the best we can hope for in a move is to reduce the disorderedness score by 2.

      A similar argument holds if a block is moved to the left.

      Furthermore, if we consider the first move, we know the values a, b, c, d, e, f are in descending order. So the pairs (a, b), (c, d), (e, f) are disordered, and of the pairs (a, d) (e, b) (c, f) only (e, b) is ordered, so we can only reduce the disorderedness by 1 on the first move.

      Similarly, on the final move the list ends up correctly ordered, and a similar argument shows that we can only reduce the disorderedness by 1 on the final move.

      So, for a sequence of length 11, we start with a disorderedness score of 10, and to reduce this to a disorderedness score of 0 will require at least 6 moves (the score being reduced by 1+2+2+2+2+1 = 10). In general reversing a sequence of length n > 2 will require at least 1 + [n / 2] moves (where [x] denotes the integer part of x).

      But can we achieve a reversal in 6 moves?

      I wrote a program to try.

      The following program can be used to examine the behaviour of sequences up to length 9 in less than 7s (and length 10 takes 23 minutes). All of these were achievable with the expected minimum number of moves. Unfortunately we want to know about sequences of length 11 (which takes 93m).

      However, in my experiments with smaller sequences, I found that the minimal sequence found always had as an initial move, removing the two leftmost elements, and then re-inserting them at position (m − 1) // 2 (where m is the length of the original sequence).

      Using this as the first move reduces the run time for a length 10 sequence to 6s, and produces a solution of 6 moves for a length 11 sequence in just 29s.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, first, arg, printf)

# start with a [1..m] list, reversed
m = arg(9, 0, int)
f = arg(1, 1, int)
printf("[m={m}, f={f}]")

# collect possible different moves
move = dict()
s = list(irange(0, m - 1))
for (i, j) in subsets(irange(0, m - 1), size=2):
  for k in irange(1, m - j + i - 1):
    if k == i: continue
    r = s[i:j + 1]
    t = s[:i] + s[j + 1:]
    r = t[:k] + r + t[k:]
    if r not in move.values():
      move[(i, j, k)] = r

# disorderedness score
def score(s):
  r = 0
  a = None
  for b in s:
    if a is not None: r += (a > b)
    a = b
  return r

# sort s in n (or fewer moves)
def solve(s, n, d, ms=[]):
  # are we done?
  if d == 0:
    yield ms
  elif n > 0:
    # choose a move
    (diff1, diff2) = (list(), 0)
    for (m, v) in move.items():
      s1 = list(s[x] for x in v)
      d1 = score(s1)
      diff = d - d1
      if diff == 2:
        # try diff 2
        yield from solve(s1, n - 1, d1, ms + [m])
        diff2 += 1
      elif diff == 1:
        # save up diff 1
        diff1.append((s1, d1, m))
    # try any diff 1 moves
    if not diff2:
      for (s1, d1, m) in diff1:
        yield from solve(s1, n - 1, d1, ms + [m])

s0 = list(irange(m, 1, step=-1))
for n in irange(1 + m // 2, inf):

  # make an initial move...
  if f:
    m1 = (0, 1, (m - 1) // 2)
    s1 = list(s0[x] for x in move[m1])
    (s, n, ms) = (s1, n - 1, [m1])
  else:
    (s, ms) = (s0, [])

  ss = first(solve(s, n, score(s), ms), 1)
  for ms in ss:
    # output solution
    printf("n={n}: {ms}", n=len(ms))
    s = s0
    for (i, j, k) in ms:
      t = list(s[x] for x in move[(i, j, k)])
      printf("  [{i}, {j}] @ {k}: {s} -> {t} ({ss} -> {st})", ss=score(s), st=score(t))
      s = t
    printf()
  if ss: break

      Solution: The minimum number of moves required is 6.

      Here is one set of 6 moves that achieves the reversal:

      (Adjacent pairs that are ordered are linked with a hyphen).

      Like

    • Jim Randell's avatar

      Jim Randell 11:19 am on 1 March 2020 Permalink | Reply

      John Crabtree has come up with the following procedure to reverse a sequence using a minimal number of moves.

      The first move partitions the sequence into an ordered sequence (to the left) and a subsequence from which ordered pairs can be removed and inserted into the ordered sequence (to the right). The total number of moves required is 1 + [n / 2].

      Here is the procedure used to reverse a length 11 sequence in 6 moves:

      And here is the procedure encapsulated in a Python program:

      Run: [ @replit ]

      from enigma import (irange, tuples, arg, printf)

# generate the moves to reverse a sequence of length n
def reverse(n):
  if n < 3:
    if n == 2: yield (1, 1, 0)
    return
  (h, r) = divmod(n, 2)
  # 1st move
  yield (h + r, n - 1, r)
  # then move successive pairs into position
  for k in irange(0, h - 1):
    i = k + h + r - 1
    j = i + 1
    yield (i, j, k)
    

# disorderedness score
score = lambda s: sum(a > b for (a, b) in tuples(s, 2))

# make a block move
def move(s, i, j, k):
  r = s[i:j + 1]
  t = s[:i] + s[j + 1:]
  return t[:k] + r + t[k:]

n = arg(11, 0, int)

# collect the moves
ms = list(reverse(n))
printf("[n={n}, {m} moves]", m=len(ms))
s = list(irange(n, 1, step=-1))
for (i, j, k) in ms:
  t = move(s, i, j, k)
  printf("  [{i}, {j}] @ {k}: {s} -> {t} ({ss} -> {st})", ss=score(s), st=score(t))
  s = t
printf()

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 2:01 am on 18 October 2024 Permalink | Reply

      Very nice analysis!

      Liked by 1 person

  • Unknown's avatar

    Jim Randell 8:16 am on 25 February 2020 Permalink | Reply
    Tags:   

    Teaser 2880: Golfing greats 

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

    Following the success of this summer’s programmes about cricketing greats, there is to be an equivalent series about golfers. On each of the next seven evenings a different media pundit will advocate the merits of two golfers.

    The pundits are: Coltart, Critchley, Harmon, Livingstone, Lee, Murray, Roe.

    The fourteen golfers to be discussed are: Chappell, Els, Faldo, Harrington, Hogan, Mcllroy, Moore, Nicklaus, Poulter, Reed, Singh, Snead, Stenson, Woods.

    Each evening, looking at the names of the pundit and the two golfers, then for any two out of the three names there are just two letters of the alphabet that occur (once or more) in both.

    (a) Which golfers will Critchley advocate?
    (b) Which golfers will Harmon advocate?

    [teaser2880]

     
    • Jim Randell's avatar

      Jim Randell 8:17 am on 25 February 2020 Permalink | Reply

      This puzzle can be solved using the [[ grouping ]] functionality in the enigma.py library.

      The following program runs in 72ms.

      Run: [ @repl.it ]

      from enigma import grouping

pundits = (
  'Coltart', 'Critchley', 'Harmon', 'Livingstone', 'Lee', 'Murray', 'Roe'
)
subjects = (
  'Chappell', 'Els', 'Faldo', 'Harrington', 'Hogan', 'Mcllroy', 'Moore',
  'Nicklaus', 'Poulter', 'Reed', 'Singh', 'Snead', 'Stenson', 'Woods'
)

# form the 2-gangs
grouping.solve_gangs(2, pundits, subjects, grouping.share_letters(2))

      Solution: Critchley advocates Moore and Reed. Harmon advocates Singh and Snead.

      The full schedule is:

      Coltart → Hogan, Stenson
      Critchley → Moore, Reed
      Harmon → Singh, Snead
      Livingstone → Faldo, Woods
      Lee → Chappell, Els
      Murray → Nicklaus, Poulter
      Roe → Harrington, Mcllroy

      Like

  • Unknown's avatar

    Jim Randell 5:22 pm on 21 February 2020 Permalink | Reply
    Tags:   

    Teaser 2996: Piece it together 

    From The Sunday Times, 23rd February 2020 [link] [link]

    I have some jigsaw-type pieces each consisting of one, two, three or four 1cm-by-1cm squares joined together without overlapping. The pieces are black on one side and white on the other, and they are all different. I have used all my pieces to simultaneously make some different-sized white squares in jigsaw fashion, with each square using more than one piece. Even if you knew what all my pieces were like, you would not be able to determine the sizes of my squares.

    How many pieces do I have?

    [teaser2996]

     
    • Jim Randell's avatar

      Jim Randell 8:55 pm on 21 February 2020 Permalink | Reply

      (See also: Enigma 321).

      There are only a limited number of 1-sided, 1-, 2-, 3-, 4-onimoes, and as the pieces are all different this gives us an upper limit to the total area of the squares.

      It is fairly straightforward to narrow the required answer down to one of two values on the back of an envelope. But it is fun to make a constructive solution from scratch, so here goes…

      The following program looks for possible total areas that can be made into multiple different squares.

      We then select pieces with the appropriate area and attempt to construct the different sets of squares.

      This Python 3 program is adapted from my initial solution to Enigma 321. It’s not hugely fast, but it does solve the problem in 19s.

      from itertools import product
from copy import deepcopy
from enigma import (irange, inf, subsets, diff, first, printf)

# possible pieces in all possible orientations
pieces = [

  # 1 square - 1x1 block ["O1"]
  (
    [(0, 0)],
  ),

  # 2 squares - 2x1 block ["I2"]
  (
    [(0, 0), (1, 0)],
    [(0, 0), (0, 1)],
  ),

  # 3 squares - linear, 3x1 block ["I3"]
  (
    [(0, 0), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (0, 2)],
  ),

  # 3 squares - L shape ["V3"]
  (
    [(0, 0), (1, 0), (1, 1)],
    [(1, 0), (0, 1), (1, 1)],
    [(0, 0), (1, 0), (0, 1)],
    [(0, 0), (0, 1), (1, 1)],
  ),

  # 4 squares - 4x1 block, ["I4"]
  (
    [(0, 0), (1, 0), (2, 0), (3, 0)],
    [(0, 0), (0, 1), (0, 2), (0, 3)],
  ),

  # 4 squares - square, 2x2 block ["O4"]
  (
    [(0, 0), (1, 0), (0, 1), (1, 1)],
  ),

  # 4 squares - T shape ["T4"]
  (
    [(1, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 1), (0, 2)],
    [(0, 0), (1, 0), (2, 0), (1, 1)],
    [(1, 0), (0, 1), (1, 1), (1, 2)],
  ),

  # and now the chiral ones

  # 4 squares - Z shape ["Z4"]
  (
    [(0, 1), (1, 1), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],
  ),

  # 4 squares - S shape ["Z4'", "S4"]
  (
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(1, 0), (1, 1), (0, 1), (0, 2)],
  ),

  # 4 squares - L shape ["L4"]
  (
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(1, 0), (1, 1), (1, 2), (0, 2)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
  ),

  # 4 squares - L shape ["L4'", "R4"]
  (
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 1), (1, 1), (2, 1), (2, 0)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (0, 1), (1, 0), (2, 0)],
  ),
]

# try to place piece <p> at <x>, <y> in grid <grid> of dimensions <a>, <b>
# using label <n>
def place(p, y, x, n, grid, a, b):
  g = deepcopy(grid)
  for (dy, dx) in p:
    (py, px) = (y + dy, x + dx)
    try:
      q = g[py][px]
    except IndexError:
      return None
    if q is not None:
      return None
    g[py][px] = n
  return g

# try to fit pieces <ps> into grid <grid> of dimensions <a>, <b>
def fit(ps, n, grid, a, b):
  if not ps:
    yield grid
  else:
    # choose a piece
    for p in ps[0]:
      # try to place the piece at x, y
      for (y, x) in product(irange(0, a - 1), irange(0, b - 1)):
        g = place(p, y, x, n, grid, a, b)
        if g is not None:
          yield from fit(ps[1:], n + 1, g, a, b)

# select at least <n> pieces from <ps> with a total area of <k>
def select(ps, k, n):
  for i in irange(n, len(ps)):
    f = 0
    for s in subsets(ps, size=i):
      t = sum(len(p[0]) for p in s) 
      if t == k:
        yield s
      if not (t > k):
        f += 1
    if f == 0: break

# fit the pieces <ps> into squares with sides <squares>
def fit_squares(ps, squares, ss=[]):
  # are we done?
  if not ps:
    yield ss
  else:
    # try to fill the next square
    s = squares[0]
    # choose pieces with the right area
    for fs in select(ps, s * s, 2):
      # create an s x s empty grid and assemble the pieces in it
      grid = list([None] * s for _ in irange(1, s))
      for g in fit(fs, 1, grid, s, s):
        # fit the remaining squares
        yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])

# find an example fit of the pieces <ps> into each of the list of squares <ss>
def solve(ps, ss):
  fs = list()
  for s in ss:
    f = first(fit_squares(ps, s))
    if not f: return
    fs.extend(f)
  return fs


# express n as a sum of increasing squares (minimum: m)
def sum_of_squares(n, m=1, s=[]):
  if n == 0:
    if len(s) > 1:
      yield s
  else:
    for i in irange(m, inf):
      i2 = i * i
      if i2 > n: break
      yield from sum_of_squares(n - i2, i + 1, s + [i])

# consider increasing total area of the squares
T = sum(len(p[0]) for p in pieces)
for n in irange(4 + 9, T):
  sqs = list(sum_of_squares(n, 2))
  if len(sqs) < 2: continue
  printf("total area = {n} -> squares = {sqs}")

  # choose some of the squares
  for ss in subsets(sqs, min_size=2):

    # make a set of polyominoes with the appropriate total area
    for ps in select(pieces, n, 2 * max(len(s) for s in ss)):

      # try and fit them into the squares
      fs = solve(ps, ss)
      if fs is None: continue

      # output solution (number of pieces), and constructed squares
      printf("  {m} pieces", m=len(ps))
      for (s, f) in zip(ss, fs):
        printf("  {s} -> {f}")
      printf()

      There is only a single candidate area that can be expressed as the sum of different, non-unit squares in multiple ways.

      There are two sets of pieces that can be assembled into the required squares, but they both have the same number of pieces (one set is a mirror image of the other), and so this gives the answer.

      Solution: There are 9 jigsaw pieces.

      The 9 pieces have a total area of 29, and can be assembled into a set of (2×2, 3×3, 4×4) squares, or a set of (2×2, 5×5) squares.

      Here is a solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4.

      Note that we can’t turn the pieces over, so L4 and its mirror image (L4′) are different pieces (you cannot rotate one of them to give the same shape as the other), as are Z4 and its mirror image (Z4′).

      And here is another solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4′.

      The second set uses Z4′ instead of Z4. These pieces are mirror images of each other, so any solution for the first set also gives a solution for the second set, by reflecting it.

      There are no further solutions, even if we were are allowed to have squares that are the same size.

      It occurred to me that the squares are the same sizes as the collection of Rubik’s cubes I have available to me, so here are the diagrams made with cubes:

      (I’ve only got one 2×2×2 cube, so it has to be shared between the sets of squares).

      Like

      • Jim Randell's avatar

        Jim Randell 10:55 am on 23 February 2020 Permalink | Reply

        I encapsulated the code that deals with polyominoes into a separate file [[ polyominoes.py ]] that can be used to solve this puzzle (and Enigma 321), and I switched to using Knuth’s Algorithm X, rather than the simplistic [[ fit() ]].

        So the following program runs in a more reasonable 858ms.

        Run: [ @repl.it ]

        import polyominoes
from enigma import irange, inf, subsets, diff, first, printf

# select at least <n> pieces from <ps> with a total area of <k>
def select(ps, k, n):
  for i in irange(n, len(ps)):
    f = 0
    for s in subsets(ps, size=i):
      t = sum(len(p[0]) for p in s) 
      if t == k:
        yield s
      if not(t > k):
        f += 1
    if f == 0: break

# fit the pieces <ps> into squares with sides <squares>
def fit_squares(ps, squares, ss=[]):
  # are we done?
  if not ps:
    yield ss
  else:
    # try to fill the next square
    s = squares[0]
    # choose pieces with the right area
    for fs in select(ps, s * s, 2):
      # create an s x s empty grid and assemble the pieces in it
      for g in polyominoes.fit(fs, s, s):
        # fit the remaining squares
        yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])

# find an example fit of the pieces <ps> into each of the list of squares <ss>
def solve(ps, ss):
  fs = list()
  for s in ss:
    f = first(fit_squares(ps, s))
    if not f: return
    fs.extend(f)
  return fs


# express n as a sum of increasing squares (minimum: m)
def sum_of_squares(n, m=1, s=[]):
  if n == 0:
    if len(s) > 1:
      yield s
  else:
    for i in irange(m, inf):
      i2 = i * i
      if i2 > n: break
      yield from sum_of_squares(n - i2, i + 1, s + [i])

# available pieces, and total area
pieces = polyominoes.shapes("O1 I2 I3 V3 O4 I4 T4 Z4 Z4' L4 L4'", "ONE_SIDED")

# consider increasing total area of the squares
T = sum(len(p[0]) for p in pieces)
for n in irange(4 + 9, T):
  sqs = list(sum_of_squares(n, 2))
  if len(sqs) < 2: continue
  printf("total area = {n} -> squares = {sqs}")

  # choose some of the squares
  for ss in subsets(sqs, min_size=2):

    # make a set of polyominoes with the appropriate total area
    for ps in select(pieces, n, 2 * max(len(s) for s in ss)):

      # try and fit them into the squares
      fs = solve(ps, ss)
      if fs is None: continue

      # output solution (number of pieces), and constructed squares
      printf("  {m} pieces", m=len(ps))
      for (s, f) in zip(ss, fs):
        printf("  {s} -> {f}")
      printf()

        Like

    • Robert Brown's avatar

      Robert Brown 12:57 pm on 25 February 2020 Permalink | Reply

      This teaser reminds me of enigma 1491 (not on your site?) from 2008. Box of tiles 1×3, 2×4, 3×5 etc. Takes tiles out in order, one at a time, and tries to make a rectangle. Required to find a) smallest possible rectangle & b) next largest. Everyone could all do a) by hand, but b) needed a fairly complex program. Ongoing discussions gradually simplified the program algorithm, and ultimately we got it down to a series of steps that could be followed manually – could be done in about 10 minutes. It’s all on the newenigma site, but you need a user name & password to log in!

      Like

    • Robert Brown's avatar

      Robert Brown 1:03 pm on 25 February 2020 Permalink | Reply

      Sorry, I misquoted that slightly – should say ‘required to find how many tiles for smallest rectangle’ (which of course has no gaps or overlaps)

      Like

      • Jim Randell's avatar

        Jim Randell 2:20 pm on 25 February 2020 Permalink | Reply

        I remember Enigma 1491. It was a fun puzzle. My notes for it are here [ @enigmaticcode ].

        When it was originally published in 2008 I wrote a Perl program to solve it, but that took 50 minutes to run. So while it was running I coded up the same algorithm in C, and that ran in 11 seconds.

        When I came to add the puzzle to the Enigmatic Code site in 2012 I wrote a Python program using a slightly different approach, and found that it ran in 9.2s. Now the same program runs in just 2.5s (probably due to improvements in the PyPy environment — I’m still using the same laptop I was using in 2012).

        Like

  • Unknown's avatar

    Jim Randell 8:10 am on 18 February 2020 Permalink | Reply
    Tags:   

    Teaser 2881: A month of meetings 

    From The Sunday Times, 10th December 2017 [link] [link]

    In one particular month this year I had one-day meetings in each of Geneva, London, Rome, Tallinn, Venice and York. For any two of these cities their names had at least one letter in common precisely when the days of their meetings (1st, 2nd, 3rd …) had no common factor larger than one. No two meetings were on the same day of the week (e.g., no two meetings were on Wednesdays). The Geneva meeting was the first and the London meeting was the last, the London meeting being on a Friday.

    What was the date of the Tallinn meeting (month and day)?

    The original puzzle text used the spelling “Tallin”. In the text above I’ve used the more usual spelling, but the puzzle works with either.

    [teaser2881]

     
    • Jim Randell's avatar

      Jim Randell 8:11 am on 18 February 2020 Permalink | Reply

      This Python 3 program runs in 372ms.

      Run: [ @repl.it ]

      from datetime import date
from enigma import (irange, gcd, unpack, cached, printf)

# the set of letters in a string
def letters(s):
  return set(x for x in s.lower() if x.isalpha())

# return the number of letters shared by two strings
@cached
def share_letters(a, b):
  return len(letters(a).intersection(letters(b)))

# find dates for places <ps>, starting from date <d0>
# s = (place, date) pairs allocated so far
def solve(ps, d0, s=[]):
  # are we done?
  if not ps:
    yield s
  else:
    p = ps[0]
    # choose a date
    for d in irange(d0, 31):
      # no meetings are on the same day of the week
      if any((d - d1) % 7 == 0 for (p1, d1) in s): continue
      # places have a letter in common iff their dates are coprime
      if any(bool(share_letters(p, p1)) != (gcd(d, d1) == 1) for (p1, d1) in s): continue
      # solve for the remaining places
      yield from solve(ps[1:], d0, s + [(p, d)])

# the Geneva meeting was first, so choose a date for that
for dG in irange(1, 26):
  # solve for the remaining places (except London)
  for s1 in solve(['Rome', 'Tallinn', 'Venice', 'York'], dG + 1, [('Geneva', dG)]):
    # and then solve for London (last meeting)
    dM = max(d for (p, d) in s1)
    for s in solve(['London'], dM + 1, s1):
      # find a month in 2017 where the London meeting is a Friday
      (_, dL) = s[-1]
      for m in irange(1, 12):
        try:
          d = date(2017, m, dL)
        except ValueError:
          continue
        # Friday is weekday 4
        if d.weekday() != 4: continue

        # output a solution (ordered by date)
        for (p, d) in sorted(s, key=unpack(lambda p, d: d)):
          printf("{d} {p}", d=date(2017, m, d).strftime("%a %d %b %Y"))
        printf()

      Solution: The Tallinn meeting was on Wednesday 22nd March 2017.

      There are two possible itineraries:

      Sun 05 Mar 2017 Geneva
      Sat 11 Mar 2017 Rome
      Tue 21 Mar 2017 Venice
      Wed 22 Mar 2017 Tallinn
      Thu 30 Mar 2017 York
      Fri 31 Mar 2017 London

      Sun 05 Mar 2017 Geneva
      Sat 11 Mar 2017 Rome
      Wed 22 Mar 2017 Tallinn
      Mon 27 Mar 2017 Venice
      Thu 30 Mar 2017 York
      Fri 31 Mar 2017 London

      Like

  • Unknown's avatar

    Jim Randell 8:32 am on 16 February 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 513: [Famiy tree] 

    From The Sunday Times, 11th April 1971 [link]

    Damon Rigby is my grandfather, and his four children (including Henry) are all married. Aunt Fanny is the youngest and at her wedding to Charlie Jones last week I met four of my cousins; only two of our number have the same surnames and only one is married.

    My mother’s name is Mary Rigby and I am her only child. My first name is that of the husband of my oldest aunt, but it is a tradition in our family that blood relations do not carry the same first name.

    Aunt Fanny has a niece whose surname is Finch. Amanda has the same surname as Agatha’s sister. Aunt Doris has but a single daughter. Jack Prior has an aunt married to Tom whose niece is Amy Brown. The first name of Margaret’s father is the same as my father’s.

    What are the full names of the five cousins?

    This puzzle was originally published with no title.

    [teaser513]

     
    • Jim Randell's avatar

      Jim Randell 8:33 am on 16 February 2020 Permalink | Reply

      I assumed a simple scenario with male/female marriages, and no couple having children from outside their marriages.

      I wasn’t really sure on the best way to program a solution, so I started looking at bits I could simplify, and ended up with a complete manual solution. As follows:

      There are four uncle/aunt pairs. And there are five cousins in total – the setter, plus the four cousins he met.

      Assuming that Fanny and Charles don’t have any children. The setter is an only (male) child (of one of the other three uncle/aunt pairs). Another of the pairs has a single female child (Aunt Doris + husband). Which leaves the one remaining aunt/uncle pair with three offspring. Only one of the cousins is married, and only two share the same surname. So of these three one of them must be be a female, who married and changed her name. Leaving the other two unmarried and sharing the same family surname.

      So this gives us the basic structure of the family tree:

      [0] Grandparents; 4 children.

      [1] Henry + Mary; 1 child [setter, male, unmarried]

      [2] Doris + (husband); 1 child [female, unmarried]

      [3] (wife) + (husband); 3 children [1 female, married; 2 unmarried]

      [4] Fanny + Charles; no children.

      Of the aunts/uncles generation there will be a (Henry) Rigby family, and a (Charlie) Jones family, and the remaining two families are from (Finch, Prior, Brown) with the unused one being the name of the married cousin.

      The other two offspring of Damon (other than Henry and Fanny) must also be female (Doris and (not-Doris)) and have changed their names on marriage.

      The setter must be the son of Henry Rigby and Mary (unknown), so he is (unknown) Rigby, sharing a name with the husband of Doris or (not-Doris).

      So, with unknown values in brackets, we have the following 4 families:

      [1] Henry Rigby + Mary (unknown) → (unknown) Rigby [setter, male, unmarried]

      [2] Doris Rigby + (unknown) (Finch/Prior/Brown) → (unknown) (F/P/B) [female, unmarried]

      [3] (not-Doris) Rigby + (unknown) (F/P/B) → (unknown) (was F/P/B) [female, married]; (unknown) (F/P/B) [unmarried]; (unknown) (F/P/B) [unmarried]

      [4] Fanny Rigby + Charlie Jones

      Jack Prior must be one of the unmarried cousins in family [3], so the family name is Prior. He has an aunt married to Tom, this must be family [2], Doris Rigby (married to Tom (Finch or Brown)). Tom has a niece Amy Brown, so Amy Brown must be the married child in family [3], and parents of family [2] are Doris Rigby + Tom Finch.

      [1] Henry Rigby + Mary (unknown) → (unknown) Rigby [setter, male, unmarried]

      [2] Doris Rigby + Tom Finch → (unknown) Finch [female, unmarried]

      [3] (not-Doris) Rigby + (unknown) Prior → Amy Brown (was Prior) [married]; Jack Prior [unmarried]; (unknown) Prior [unmarried]

      [4] Fanny Rigby + Charlie Jones

      Now, “the first name of Margaret’s father is the same as my father” (i.e. Henry). So Margaret can’t be the child in family [2] (as her father’s name is Tom), so she must be in family [3], and the father is Henry Prior.

      [1] Henry Rigby + Mary (unknown) → (unknown) Rigby [setter, male, unmarried]

      [2] Doris Rigby + Tom Finch → (unknown) Finch [female, unmarried]

      [3] (not-Doris) Rigby + Henry Prior → Amy Brown (was Prior) [married]; Jack Prior [unmarried]; Margaret Prior [unmarried]

      [4] Fanny Rigby + Charlie Jones

      The setter’s first name is the same as the husband of his eldest aunt, i.e. Tom Finch or Henry Prior, but the setter can’t be called Henry, as that is his father’s name, so the setter must be Tom Rigby.

      Finally, “Amanda has the same surname as Agatha’s sister”. The child from family [2] does not have a sister, so Agatha must be the mother of family [3], and Agatha’s sister is Doris Finch, so Amanda Finch is her daughter.

      Giving us the complete family tree of:

      [0] Damon Rigby + (unknown) (unknown) → [1]; [2]; [3]; [4]

      [1] Henry Rigby + Mary (unknown) → Tom Rigby [setter, unmarried]

      [2] Doris Rigby + Tom Finch → Amanda Finch [unmarried]

      [3] Agatha Rigby + Henry Prior → Amy Brown (was Prior) [married]; Jack Prior [unmarried]; Margaret Prior [unmarried]

      [4] Fanny Rigby + Charlie Jones

      We don’t know the first name or the maiden name of the grandmother (Mrs Rigby), or the maiden name of Mary Rigby (the setter’s mother), or the first name of Amy’s husband (Mr Brown).

      Solution: The five cousins are: Tom Rigby (the setter); Amanda Finch; Amy Brown, Jack Prior, Margaret Prior.

      Like

  • Unknown's avatar

    Jim Randell 4:58 pm on 14 February 2020 Permalink | Reply
    Tags:   

    Teaser 2995: Pub celebration 

    From The Sunday Times, 16th February 2020 [link] [link]

    While celebrating with friends in the pub, it was my round, and I worked out the number of ways that I could get everybody else’s drink wrong. I could remember the drinks (and they all wanted different drinks), but not who wanted which drink.

    More friends arrived (there were fewer than twenty of us in total), and everyone still wanted different drinks. Again assuming that I could remember the drinks but not who wanted which drink, I worked out the number of ways that I could get everybody else’s drink wrong, and found that the number was 206 times the first number. Fortunately, it was no longer my round!

    What was the second number?

    [teaser2995]

     
    • Jim Randell's avatar

      Jim Randell 5:07 pm on 14 February 2020 Permalink | Reply

      The number of derangements [ @wikipedia ] of a set of n objects is known as subfactorial(n), denoted !n. (See: Teaser 2779).

      This Python program calculates !n recursively. It runs in 72ms.

      Run: [ @repl.it ]

      from enigma import irange, div, cached, printf

# count the number of derangements of n objects (!n)
@cached
def subfactorial(n):
  if n == 0: return 1
  return n * subfactorial(n - 1) + (-1 if n % 2 else 1)

# look for numbers p, q such that !q / !p = 206
for q in irange(2, 19):
  sq = subfactorial(q)
  m = div(sq, 206)
  if m is None: continue
  for p in irange(1, q - 1):
    sp = subfactorial(p)
    if sp == m:
      printf("!{p} = {sp} -> !{q} = {sq}")

      Solution: The second number is 1854.

      Initially the setter has 4 friends (!4 = 9), so there were 5 people in the group.

      After the additional people arrived the setter had 7 friends (!7 = 1854 = 206 × 9), so there were 8 people in the group.

      Manually we can use use the following recurrence relation to count derangements:

      d(0) = 1
      d(n) = n . d(n − 1) + {1 if n is even, −1 if n is odd}

      This makes it easy to calculate values on a calculator, and is enough to find that d(7) ÷ 206 = d(4).

      However beyond d(13) = 2290792932 my physical calculator runs out of digits. The Calculator app on my laptop has just enough digits to “manually” determine that d(19) (which has 17 digits) is also divisible by 206, but the result of the division is not a d value we have already encountered, so the solution is unique. (Of course Python has built-in bigint support, so doesn’t have a problem with the larger numbers).

      Like

      • Jim Randell's avatar

        Jim Randell 9:24 am on 15 February 2020 Permalink | Reply

        And here is a solution that calculates !n iteratively.

        Run: [ @repl.it ]

        from enigma import inf, div, printf

# generate (n, !n) pairs
def subfactorials(k=inf):
  (n, d, x) = (0, 1, -1)
  while n < k:
    yield (n, d)
    n += 1
    d = n * d + x
    x = -x

ds = list()
for (n, d) in subfactorials(20):
  m = div(d, 206)
  if m is not None:
    for (i, x) in enumerate(ds):
      if x == m:
        printf("!{i} = {m} -> !{n} = {d}")
  ds.append(d)

        We only need to check for the smaller case when !n is divisible by 206, which only happens in 2 non-trivial cases for the range of values applicable to the puzzle.

        The program also accumulates the sequence of subfactorials in the array [[ ds ]]. (See OEIS A000166 [ @oeis.org ]).

        Like

    • GeoffR's avatar

      GeoffR 1:09 pm on 17 February 2020 Permalink | Reply 

      
# Uses a recurrent expression identified by Euler:
# i.e. a(n) = n * a(n-1) + (-1) ^ n

from itertools import combinations
from collections import defaultdict

d = defaultdict(list)

# initial values in derangement sequence of drinks wrong
D1, D2, D3 = 0, 1, 2

# further derangement values use Euler's recurrent sequence
# e.g. D4 is derangement value for four people
# ten derangements are sufficient to solve this teaser
# as D10 = 1,334,961 and D19 is 17 digits long

D4 = 4 * D3 + (-1)**4
D5 = 5 * D4 + (-1)**5
D6 = 6 * D5 + (-1)**6
D7 = 7 * D6 + (-1)**7
D8 = 8 * D7 + (-1)**8
D9 = 9 * D8 + (-1)**9
D10 = 10 * D9  + (-1)**10

# form a dictionary with keys as number of friends
# and values as number of ways drinks wrong for each group
d = {2:1, 3:2, 4:D4, 5:D5, 6:D6, 7:D7, 8:D8, 9:D9, 10:D10}

for k1, k2 in combinations(d.keys(),2):
  if k2 > k1 :
    # second number was 206 times the first number
    d1, r1 = divmod( d[k2], d[k1] )
    if d1 == 206 and r1 == 0:
      print (f"1st group of friends = {k1} No.")
      print (f"2nd group of friends = {k2} No.")

      Like

    • Frits's avatar

      Frits 2:22 pm on 3 September 2020 Permalink | Reply

      Fooling around after expressing subfactorial formulas (n+1, n+2 and n+3) in terms of !(n-1).

      I am pretty sure that for n+4 a term n*(n+1)*(n+2)*(n+3)*(n+4) will occur.
      This factor is too high (even for n=2).

       
from enigma import irange, cached
 
# count the number of derangements of n objects (!n)
# an alternative formula is n * subfactorial(n - 1) + (-1 if n % 2 else 1)
@cached
def subfactorial(n):
  if n == 0: return 1
  if n == 1: return 0
  return (n - 1) * (subfactorial(n - 1) + subfactorial(n - 2))
 
# !(n+1) / !(n-1) = n*(n+1) +/- n / !(n-1)
# !(n+2) / !(n-1) = n*(n+1)*(n+2) +/- (n+1)^2 / !(n-1)
# !(n+3) / !(n-1) = n*(n+1)*(n+2)*(n+3) +/- (n*(2n^2+4n+3)) / !(n-1)

minplus = [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1]

for n in irange(3, 12):
  sn = subfactorial(n-1)
 
  if n*(n+1) + minplus[n]*n // sn == 206: 
    print(f"!{n-1} = {sn} -> !{n+1} = \
{n*(n+1)*sn + minplus[n]*n}")
  
  if n*(n+1)*(n+2) + minplus[n]*(n+1)**2 // sn == 206: 
    print(f"!{n-1} = {sn} -> !{n+2} = \
{n*(n+1)*(n+2)*sn + minplus[n]*(n+1)**2}")
  
  if n*(n+1)*(n+2)*(n+3) + minplus[n]*n*(2*n**2+4*n+3) // sn == 206: 
    print(f"!{n-1} = {sn} -> !{n+3} = \
{n*(n+1)*(n+2)*(n+3)*sn + minplus[n]*n*(2*n**2+4*n+3)}")
    
# Output:
#
# !4 = 9 -> !7 = 1854

      Like

  • Unknown's avatar

    Jim Randell 5:22 pm on 7 February 2020 Permalink | Reply
    Tags:   

    Teaser 2994: Consecutive sums 

    From The Sunday Times, 9th February 2020 [link] [link]

    Amelia noticed that 15 is equal to 1+2+3+4+5 or 4+5+6 or 7+8, so there are three possible ways that it can be expressed as the sum of consecutive whole numbers. She then told Ben that she had found a three-digit number which can be expressed as the sum of consecutive whole numbers in just two different ways. “That’s interesting”, said Ben. “I’ve done the same, but my number is one more than yours”.

    What is Ben’s number?

    [teaser2994]

     
    • Jim Randell's avatar

      Jim Randell 5:36 pm on 7 February 2020 Permalink | Reply

      The following Python program runs in 221ms.

      Run: [ @replit ]

      from enigma import (defaultdict, subsets, irange, tri, printf)

# collect consecutive sums for 3-digit numbers
d = defaultdict(list)
for (i, j) in subsets(irange(1, 500), size=2):
  n = tri(j) - tri(i - 1)
  if 99 < n < 1000:
    d[n].append((i, j))

# find consecutive numbers expressible in 2 different ways
for (n, vs) in d.items():
  if len(vs) == 2:
    vs1 = d.get(n + 1, None)
    if vs1 and len(vs1) == 2:
      printf("{n} -> {vs}; {n1} -> {vs1}", n1=n + 1)

      Solution: Ben’s number is 289.

      289 can be expressed as:

      289 = 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25
      289 = 144 + 145

      Amelia’s number is 288, which can be expressed as:

      288 = 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36
      288 = 95 + 96 + 97

      Like

      • Jim Randell's avatar

        Jim Randell 6:36 pm on 7 February 2020 Permalink | Reply

        Here is a neater program that uses the technique described in the comments of Enigma 1. It runs in 83ms.

        Run: [ @replit ]

        from enigma import (divisors, irange, cache, printf)

S = cache(lambda n: sum(d % 2 for d in divisors(n)))

# find 2 consecutive 3-digit numbers with S(n) == 3
for a in irange(100, 998):
  b = a + 1
  if S(a) == 3 and S(b) == 3:
    printf("{a}, {b}")

        Analytically:

        In order for the numbers to have exactly 3 odd divisors they must be of the form:

        n = (2^k)(p^2)

        where p is an odd prime.

        And we are looking for two consecutive numbers, so one will be even and one will be odd (k = 0).

        We can look for 3-digit numbers manually, or programatically:

        from enigma import (primes, tuples, printf)

# collect 3-digit numbers with S(n) = 3
ns = list()

# consider p^2 term
for p in primes.between(3, 31):
  n = p * p
  while n < 1000:
    if n > 99: ns.append(n)
    n *= 2
ns.sort()

# find consecutive pairs
for (a, b) in tuples(ns, 2):
  if b == a + 1:
    printf("{a}, {b}")

        We find the following 3-digit numbers with exactly 3 odd divisors:

        [p=3] 144, 288, 576
        [p=5] 100, 200, 400, 800
        [p=7] 196, 392, 784
        [p=11] 121, 242, 484, 968
        [p=13] 169, 338, 676
        [p=17] 289, 578
        [p=19] 361, 722
        [p=23] 529
        [p=29] 841
        [p=31] 961

        And there are only two consecutive numbers in this list:

        288 = (2^5)(3^2)
        289 = (2^0)(17^2)

        Like

        • Frits's avatar

          Frits 10:52 pm on 3 August 2020 Permalink | Reply

          Over the first 500 million numbers (> 99) only 2 consecutive numbers exist.

          from enigma import Primes, printf, irange
 
# collect 3-digit numbers with S(n) = 3
ns = list()
test = 500000000
 
# consider p^2 term
for p in Primes(test).irange(3, test):
  n = p * p
  #print(n)
  while n < test**2:
    if n > 99: ns.append(n)
    n *= 2
ns.sort()

# find consecutive pairs

for i in irange(0, len(ns) - 2):
  if ns[i+1] == ns[i] + 1:
    printf("{ns[i]}, {ns[i+1]}")

          Output:

          288, 289
          1681, 1682

          Like

          • Jim Randell's avatar

            Jim Randell 10:24 am on 4 August 2020 Permalink | Reply

            @Frits: I found some notes (and a program) that I wrote at the time on looking for larger solutions:

            For consecutive numbers one of the following equations must hold:

            p² − (2^k)q² = +1
            p² − (2^k)q² = −1

            where p and q are odd primes.

            So we can consider solutions to the following forms of Pell’s Equation:

            x² − 2y² = +1
            x² − 2y² = −1

            and look for solutions where x is an odd prime and y is an odd prime multiplied by a power of 2.

            I have the following code (in a file called pells.py) that uses SymPy to solve Pell’s equations:

            try:
  # newer versions of SymPy
  from sympy.solvers.diophantine.diophantine import diop_DN
except ImportError:
  # older versions of SymPy
  from sympy.solvers.diophantine import diop_DN

# interleave a sequence of iterators
def interleave(ss):
  while ss:
    xs = list()
    for (i, s) in enumerate(ss):
      try:
        yield next(s)
      except StopIteration:
        xs.insert(0, i)
    for i in xs:
      del ss[i]

# initial values from a sequence of iterators
def initial(ss):
  for s in ss:
    try:
      yield next(s)
    except StopIteration:
      pass

def solutions(D, N, x, y):
  # initial solution
  yield (D, N, x, y)
  # to go further we need the fundamental solution to (D, 1)
  if N == 1:
    (u, v) = (x, y)
  else:
    [s] = diop_DN(D, 1)
    (u, v) = map(int, s)
  while True:
    t = (x, y)
    (x, y) = (u * x + D * v * y, v * x + u * y)
    if (x, y) == t: break
    assert x * x - D * y * y == N
    yield (D, N, x, y)

# generate solutions to Pell's equations
#
#  x^2 - D.y^2 = N
#
# each equation may have multiple infinite families of solutions
#
# return values are (D, N, x, y), satisfying the above equation
#
# fn=interleave will generate solutions from each family interleaved
#
# fn=initial will generate just the first solution from each family
#
# Python 3 style definition: def pells(*DNs, fn=interleave):
def pells(*DNs, **kw):
  fn = kw.get('fn', interleave)
  ss = list()
  for (D, N) in DNs:
    # consider fundamental solutions
    for s in diop_DN(D, N):
      (x, y) = map(int, s)
      ss.append(solutions(D, N, x, y))
  return fn(ss)

            Which I then use in the following program:

            Run: [ @replit ]

            from pells import pells
from enigma import (irange, is_prime_mr, drop_factors, first, printf)

is_prime = lambda n: is_prime_mr(n, r=10)

# look for possible solutions (from the first 60)
for (D, N, x, y) in first(pells((2, 1), (2, -1)), 60):
  # extract p, q
  p = x
  if not (p > 2 and is_prime(p)): continue
  (k, q) = drop_factors(y, 2)
  if not (q > 2 and is_prime(q)): continue
  # output solution
  (a, b) = (x * x, 2 * y * y)
  printf("{a} - {b} = {N} [p={p} q={q}]")

            I used the program to check up to 6,000 solutions to the Pell’s equations (by which time the numbers under consideration are huge), and found the following pairs:

            [p² − (2^k)q² = +1]

            289 − 288 = 1
            [n=1; p=17 q=3]

            [p² − (2^k)q² = −1]

            49 − 50 = −1
            [n=1; p=7 q=5]

            1681 − 1682 = −1
            [n=2; p=41 q=29]

            3971273138702695316401 − 3971273138702695316402 = −1
            [n=14; p=63018038201 q=44560482149]

            367680737852094722224630791187352516632102801 − 367680737852094722224630791187352516632102802 = −1
            [n=29; p=19175002942688032928599 q=13558774610046711780701]

            Like

            • Frits's avatar

              Frits 8:51 am on 7 August 2020 Permalink | Reply

              @Jim,

              On PuzzlingInPython [{broken link removed}] the Pell equation has been reduced to:

              (x_{k+1}, y_{k+1}) = (3x_k+4y_k,2x_k+3y_k)

              In an overnight run with this formula I checked up to 7000 solutions (only using one core) finding no more than you did.

              Like

    • Frits's avatar

      Frits 8:10 pm on 3 August 2020 Permalink | Reply

      Where did you find formula n = (2^k)(p^2) ?
      I only found a reference at OEIS A072502 ?

      from enigma import irange, printf, tau

# The requested numbers appear in OEIS as A072502
# Gary Detlefs suggested the tau equation
S = lambda n: tau(2*n) == (tau(n) + 3)
 
for a in irange(100, 998):
  b = a + 1
  if S(a) and S(b) :
    printf("{a}, {b}")

      Like

      • Jim Randell's avatar

        Jim Randell 9:58 am on 4 August 2020 Permalink | Reply

        @Frits:

        If a number is a power of 2 (= 2^n) then it will have only 1 odd divisor: 1.

        If a number has exactly 1 odd prime factor (= (2^n)p), then it will have exactly 2 odd divisors: 1, p.

        If a number has exactly 2 different odd prime factors (= (2^n)(p.q)), then it will have exactly 4 odd divisors: 1, p, q, p.q.

        But if the 2 odd prime factors are the same (so the number is (2^n)(p^2)), then it will have exactly 3 odd divisors: 1, p, p².

        Like

    • Jim Randell's avatar

      Jim Randell 7:39 am on 14 June 2025 Permalink | Reply

      I’ve written some code for solving the following general quadratic diophantine equation in 2 variables, without using SymPy:

      a.X^2 + b.Y^2 = c

      The code is available from the enigma_plus repository as pells.py.

      The program given above can then be revised to use the new solver:

      from enigma import (is_prime_mr, drop_factors, merge, ifirst, printf)
import pells

is_prime = lambda n: is_prime_mr(n, r=10)

# look for possible solutions (from the first 60 candidates)
sols = (pells.diop_quad(1, -2, N) for N in [+1, -1])
for (x, y) in ifirst(merge(sols, uniq=1), 60):
  # extract p, q
  p = x
  if not (p > 2 and is_prime(p)): continue
  (k, q) = drop_factors(y, 2)
  if not (q > 2 and is_prime(q)): continue
  # output solution
  (a, b) = (x * x, 2 * y * y)
  printf("{a} - {b} = {N} [p={p} q={q}]", N=a - b)

      Like

  • Unknown's avatar

    Jim Randell 5:37 pm on 31 January 2020 Permalink | Reply
    Tags:   

    Teaser 2993: Baker’s weights 

    From The Sunday Times, 2nd February 2020 [link] [link]

    A baker’s apprentice was given a 1kg bag of flour, scales and weights, each engraved with a different whole number of grams. He was told to separately weigh out portions of flour weighing 1g, 2g, 3g, and so on up to a certain weight, by combining weights on one side of the scales. He realised that he couldn’t do this if there were fewer weights, and the largest weight was the maximum possible for this number of weights, so he was surprised to find after one of these weighings that the whole bag had been weighed out. Upon investigation, he discovered that some of the weights weighed 1g more than their engraved weight. If I told you how many of the weights were too heavy, you would be able to work out what they all were.

    What were the actual weights (in ascending order)?

    [teaser2993]

     
    • Jim Randell's avatar

      Jim Randell 8:24 am on 1 February 2020 Permalink | Reply

      When I first read the puzzle it didn’t seem to make any sense, or have a solution.

      So I set about investigating the parts of the text that are unambiguous:

      (a) The apprentice has a set of weights, some of which are mislabelled (weighing 1g more than labelled).

      (b) The apprentice is weighing amounts of 1g, 2g, 3g, … until at some point he unexpectedly has used up exactly 1000g of flour.

      With k weights we can make (2^k − 1) different non-empty collections of weights. Using weights that are powers of 2 (i.e. 1g, 2g, 4g, 8g, …) allows us to weigh all the amounts between 1 and (2^k − 1).

      So we can start weighing out increasing amounts, look at what weights have been used and look at when a collection of mislabelled weights would bring the total amount weighed out to exactly 1000g.

      This Python program runs in 77ms.

      Run: [ @replit ]

      from enigma import (multiset, irange, inf, subsets, nsplit, seq_ordered as ordered, filter_unique, item, printf)

# record possible solutions:
# (<number of weighings>, <number of mislabelled weights>, <sequence of weights>)
ss = list()

# record the labels of the weights used
s = multiset()

# consider possible number of weighings, and total expected amount weighed out
t = 0
for n in irange(1, inf):
  t += n
  if t > 1000: break
  # calculate the required weights
  ws = list(2**i for (i, m) in enumerate(reversed(nsplit(n, base=2))) if m)
  printf("{n} -> {t}; {ws}")

  # add in the weights
  s.update_from_seq(ws)
  assert t == sum(k * v for (k, v) in s.items())

  # now consider a subset of the weights that actually weigh 1g more than labelled
  for xs in subsets(s.keys(), min_size=1):
    # the total extra weight being...
    x = sum(s[x] for x in xs)
    # does this bring the total to exactly 1kg?
    if t + x == 1000:
      k = len(xs)
      printf(" -> {xs}; +{x}; {k}")
      ss.append((n, k, ordered(w + (w in xs) for w in s.keys())))

# find solutions unique by the number of mislabelled weights (= item 1)
for (n, k, ws) in filter_unique(ss, item(1)).unique:
  # output solutions
  printf("n={n} k={k} ws={ws}")

      Solution: The actual weights were: 2g, 3g, 5g, 9g, 17g, 32g.

      So the apprentice has a set of six weights, labelled: 1g, 2g, 4g, 8g, 16g, 32g. Which, if correct, could be used to weigh any integer amount between 1g and 63g.

      However, five of the weights are mislabelled. The 1g, 2g, 4g, 8g, 16g weights all weigh 1g more than their label suggests.

      After the apprentice has weighed out amounts corresponding to 1g, 2g, 3g, …, 42g using the weights he would expect to have used 903g of flour, but with this set of weights he has actually used a total of 1000g of flour.

      The apprentice may have set out to make weights up to 42g (expecting to use 903g of flour), up to 43g (expecting to use 946g of flour), or up to 44g (expecting to use 990g of flour). For higher amounts 1000g of flour would not be enough to complete the task.

      There are also potential solutions when apprentice gets to 43g. With the set of six weights he would expect to have weighed out 946g of flour. But there are four combinations of 3 mislabelled weights, which would bring the total to exactly 1000g. (If the (1, 4, 32), (1, 8, 32), (2, 4, 32) or (2, 8, 32) weights are mislabelled).

      But we are told that if we knew the number of mislabelled weights we could work out the actual weights in the set. So we must be dealing with the case where 5 of the weights are mislabelled.

      The most reasonable scenario seems to be that apprentice was given a 1kg bag of flour and a set of 6 weights, labelled: 1g, 2g, 4g, 8g, 16g, 32g, and asked to weigh out amounts from 1g to 44g.

      The total amount to be weighed out is T(44) = 990g, so he would be expecting to have 10g of flour left at the end.

      However, after one of the weighings he has used up exactly 1000g of flour (assuming the bag of flour was actually 1000g in the first place).

      There 5 ways this can happen:

      After weighing 42g using weights (2, 3, 5, 9, 17, 32) [5 mislabelled weights]
      After weighing 43g using weights (2, 2, 5, 8, 16, 33) [3 mislabelled weights]
      After weighing 43g using weights (2, 2, 4, 9, 16, 33) [3 mislabelled weights]
      After weighing 43g using weights (1, 3, 5, 8, 16, 33) [3 mislabelled weights]
      After weighing 43g using weights (1, 3, 4, 9, 16, 33) [3 mislabelled weights]

      We are told that if we knew the number of mislabelled weights we could work out which they were, so we must be dealing with the first situation with 5 mislabelled weights.

      Like

    • Robert Brown's avatar

      Robert Brown 8:45 pm on 1 February 2020 Permalink | Reply

      He’s told to weigh portions up to a certain weight, must be <=44 as that uses 990g of flour. Binary set of weights goes up to 63g, so some of the weights could be smaller. Text says 'the largest weight was max possible for this number of weights' – I took this to mean there's a weight engraved 32g, but others seem to think it means the largest portion was the max possible for this number of weights. We all get the same answer, but using my method I didn't need to be told how many of the weights were too heavy. Does your program incorporate this?

      Like

      • Jim Randell's avatar

        Jim Randell 8:59 pm on 1 February 2020 Permalink | Reply

        @Robert: I originally thought “the largest weight was the maximum possible for this number of weights” would refer to the largest portion that the apprentice was to weigh out. So it would have to be 31g (with 5 weights) or 63g (with 6 weights), but neither of these can give a solution.

        In the end I assumed that the set of weights used was labelled as powers of 2 (i.e. 1g, 2g, 4g, 8g, …), and then used the program to look for amounts where we would expect (if the weights were correctly labelled) to have weighed out a cumulative amount less than 1000g, but if some of the weights were 1g heavier than labelled the cumulative amount is actually exactly 1000g.

        I found one set with 5 mislabelled weights where this happens, and four sets with 3 mislabelled weights.

        The puzzle text says if we knew the number of mislabelled weights we would know what the actual set of weights was, so the answer we want is the the set with 5 mislabelled weights.

        I think the wording of the puzzle could have been clearer.

        Like

    • Robert Brown's avatar

      Robert Brown 3:49 pm on 3 February 2020 Permalink | Reply

      Jim: I agree with everything that you say, but Brian Gladman seems to think “the largest weight etc” refers to the “certain weight” that the apprentice was told to use as a limit. He then thinks it’s reasonable to set this to 63g. But the person giving instructions to the apprentice would know this was impossible, as even with correct weight labels, the flour would run out after he weighed 44 portions. Of course we don’t know if that person was aware that some of the weights were wrong, which muddies the waters a bit. But Brian’s telling me that I’m effectively solving a different problem, but as far as I can see, it’s the same problem that you have solved.
      In fact, the four sets with 3 mislabelled weights occur at weighing 43, while the the set with 5 mislabelled weights occur at weighing 42. So I discounted weighing 43, which means that I didn’t need to be told the number of mislabelled weights.

      Because the weights we used can give up to 63g, I looked to see what alternatives could give every 1g step up to 44, and found 323 ways to do this, (if the 32g weight is omitted). Beyond my abilities to analyse all of these to see if there’s an alternative solution!

      Like

      • Jim Randell's avatar

        Jim Randell 9:46 am on 4 February 2020 Permalink | Reply

        I think that “the largest weight was the maximum possible for this number of weights” is a roundabout way of saying that that the weights are powers of 2. In a set of 6 (correctly labelled) weights this would mean that the largest weight was 32g, so the remaining 5 weights have to be able to weigh 1g-31g, which means they also have to be powers of 2.

        Using a set of weights that is powers of 2, means that there is only one combination of weights that makes up any specific amount, so when looking for how many times each weight is used in the weighings there is a single answer. Otherwise we may have to consider multiple different ways to make up a specific amount, which could give us different actual weights. So I think this would be a much harder problem (and maybe not have a unique solution).

        If we take “the largest weight was the maximum possible for this number of weights” to mean that the largest amount the apprentice was asked to weigh out was the largest possible for the number of weights, then if the set has 6 weights he would have been asked to weight out amounts up to 63g. This also implies that the set of weights is a “powers of 2” set. But also means that the apprentice was being set an impossible task. (Although there is a long tradition of sending apprentices on futile or impossible tasks, and as it turns out he has been given a doctored set of weights, so his task does indeed turn out to be impossible).

        I think the most reasonable interpretation is that the apprentice was given a set of 6 weights, labelled 1g, 2g, 4g, 8g, 16g, 32g and asked to weigh out amounts up to 42g, 43g or 44g (but we don’t know which). Each of these would appear to be an achievable task.

        As the apprentice weighs out the amounts he finds that the entire bag has been used up after one of the weighings. This is possible in one way after weighing out the 42g portion, and 4 ways after weighing out the 43g portion. We are told that if we knew the number of mislabelled weights, then we could work out which ones they were, so I think we need to take all these cases into account.

        So I think the most reasonable scenario was that the apprentice was asked to weigh out amounts up to 44g, a task which initially looks possible, but depending on the actual set of weights means you would run out of flour after weighing the 42g or 43g portion, making it impossible to complete the task.

        Of the 5 possible sets of weights that lead to exactly 1000g of flour being used before we get to the 44g weight, one of them involves 5 weights being doctored and four of them involved 3 of the weights being doctored. So the answer we want is the set with 5 weights.

        Like

  • Unknown's avatar

    Jim Randell 5:40 pm on 24 January 2020 Permalink | Reply
    Tags:   

    Teaser 2992: Crystal cleavage calamity! 

    From The Sunday Times, 26th January 2020 [link] [link]

    My “mystic” crystal stood on its triangular end face, with every side of the triangle being less than 10cm. It had three vertical sides and an identical triangular top end face, with the height being under 50cm. Unfortunately, during dusting, it fell and broke in two. The break was a perfect cleavage along an oblique plane that didn’t encroach on the end faces, so I then had two, pointed, pentahedral crystals.

    Later, I found that the nine edge lengths, in cm, of one of these were all different whole numbers — the majority prime — and their total was also a prime number. Curiously, the total of the nine, whole-number, edge lengths, in cm, of the other piece was also a prime number.

    What was the total for this latter piece?

    [teaser2992]

     
    • Jim Randell's avatar

      Jim Randell 9:44 am on 25 January 2020 Permalink | Reply

      Here’s my first stab at a program. It’s a bit simplistic and slow, but it finds the required solution.

      Run: [ @replit ]

      from enigma import (subsets, irange, diff, ihypot, is_prime, printf)

# choose lengths for the base (a, b, c)
for (a, b, c) in subsets(irange(1, 9), size=3):

  if not (a + b > c and a + c > b and b + c > a): continue

  # choose lengths for the the verticals
  for (x, y, z) in subsets(diff(irange(1, 48), (a, b, c)), size=3, select="P"):

    # calculate the cut lengths
    d = ihypot(a, x - z)
    e = ihypot(b, x - y)
    f = ihypot(c, y - z)
    if d is None or e is None or f is None: continue

    # edge lengths are all different, and the majority prime
    edges = (a, b, c, x, y, z, d, e, f)
    if not len(set(edges)) == 9: continue
    if not sum(is_prime(x) for x in edges) > 4: continue
    # and the total is prime
    t1 = sum(edges)
    if not is_prime(t1): continue

    # consider possible total height
    for h in irange(max(x, y, z) + 1, 49):
      # and the total of the edge lengths of the other piece
      t2 = a + b + c + (h - x) + (h - y) + (h - z) + d + e + f
      if not is_prime(t2): continue

      printf("a={a} b={b} c={c}; x={x} y={y} z={z}; d={d} e={e} f={f}; t1={t1}; h={h} t2={t2}")

      Solution: The total is 113 cm.

      The crystal is a triangular prism. The base of which forms a triangle with sides of 5cm, 7cm, 9cm.

      There are two possible sizes for the original crystal – either 44 cm tall or 48 cm tall.

      Each of these two sizes can break in two different ways, but in each scenario the sum of the edges of the “other” piece is always 113 cm.

      If we think about the triangular prism as a cardboard tube then we can “unroll” it to get the following flat diagram:

      The base of the prism consists of a triangle of sides a, b, c, and the overall height of the prism is h.

      The fracture is formed by the red line, and the lengths of the fracture line across the vertical faces are d, e, f.

      Note that d, e, f are the hypotenuses of right-angled triangles with bases of a, b, c respectively.

      And in order for the fracture to line up the lengths of two of the vertical sides of these triangles must sum to the length of the third.

      Subject to the fact all the distances are integers such that: a, b, c < 10; h < 50, we can find candidate solutions for a, b, c; d, e, f; x, y, z, such that each takes on a different value, the majority of them are prime, and their total sum is prime.

      We can then consider possible values for h that make the edges of the top piece a, b, c; d, e, f; h − x, h − y, h − z also sum to a prime number.

      We find there is only one possible shape for the base of the prism (a (5, 7, 9) triangle), and for the corresponding lengths of the fracture lines (13, 25, 15).

      There are two possible values for overall height of the prism (44 or 48), and in each case there are two possible sets of x, y, z values, giving us 4 possible solutions.

      a=5, b=7, c=9; d=13, e=25, f=15; x=31, y=43, z=19; t1=167; h=44, t2=113
      a=5, b=7, c=9; d=13, e=25, f=15; x=31, y=19, z=43; t1=167; h=44, t2=113
      a=5, b=7, c=9; d=13, e=25, f=15; x=35, y=47, z=23; t1=179; h=48, t2=113
      a=5, b=7, c=9; d=13, e=25, f=15; x=35, y=23, z=47; t1=179; h=48, t2=113

      However in each one the sum of the lengths of the edges of the top piece is 113 (the lengths of the edges for the top piece are always: 5, 7, 9; 13, 25, 15; 13, 1, 25).

      Here are the diagrams corresponding to the four possible solutions:

      Like

      • Jim Randell's avatar

        Jim Randell 4:09 pm on 25 January 2020 Permalink | Reply

        Here’s a faster program. It constructs the possible lengths of the fractures (which are the hypotenuses of right-angled triangles) up front, and then uses these to construct possible prism shapes.

        It runs in a much more respectable 180ms.

        Run: [ @replit ]

        from enigma import (irange, ihypot, subsets, is_prime, printf)

# form right angled triangles with side p, find q and hypotenuse h
tris = list()
for p in irange(1, 11):
  for q in irange(1, 49):
    h = ihypot(p, q)
    if h is None: continue
    tris.append((p, q, h))

# now consider 3 different p values for the base of the prism
for ((a, q1, d), (b, q2, e), (c, q3, f)) in subsets(tris, size=3):

  # check a, b, c form a triangular base of the prism
  if not (a + b > c and a + c > b and b + c > a): continue

  # choose a slice
  for (m1, m2, m3) in subsets((+1, -1), size=3, select="M"):

    # choose a start point for the fracture
    for x in irange(1, 49):
      y = x + m1 * q1
      z = y + m2 * q2
      if not (0 < y < 50 and 0 < z < 50 and z + m3 * q3 == x): continue

      # edge lengths for the broken piece are all different, and the majority prime
      edges = (a, b, c, x, y, z, d, e, f)
      if not len(set(edges)) == 9: continue
      if not sum(is_prime(x) for x in edges) > 4: continue
      # and the total is prime
      t1 = sum(edges)
      if not is_prime(t1): continue

      # consider possible total height
      for h in irange(max(x, y, z) + 1, 49):
        # calculate the total of the edge lengths of the other piece
        t2 = a + b + c + (h - x) + (h - y) + (h - z) + d + e + f
        if not is_prime(t2): continue

        printf("a={a} b={b} c={c}; d={d} e={e} f={f}; x={x} y={y} z={z}; t1={t1}; h={h} t2={t2}")

        Like

        • Frits's avatar

          Frits 4:21 pm on 15 August 2025 Permalink | Reply

          Adding the two prime total formulas together leads to 3*h being even or that h must be even.

          Like

    • GeoffR's avatar

      GeoffR 9:03 am on 30 January 2020 Permalink | Reply

      I also found two possible solutions, with the same edge total of the second piece.

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

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x)))))
((i < x) -> (x mod i > 0));

% the base triangle edges
var 1..9:a; var 1..9:b; var 1..9:c;

% d is above a, e above b, and f above c
% the cleavage plane triangle edges
var 1..49:d; var 1..49:e; var 1..49:f; 

% the vertical edges of the first lower piece
var 1..49:x; var 1..49:y; var 1..49:z; 

% triangle constraints  
constraint a < b /\ a + b > c /\ b + c > a /\ c + a > b;

% order the vertical edges
constraint x < y /\ y < z;

% all edges different
constraint all_different([a, b, c, d, e, f, x, y, z]);

% height of unbroken crystal
var 1..49: ht;

% edge length sum of base and cleavage triangles
var 10..200: bc_sum = a + b + c + d + e + f;

% the vertical edge sum
var 10..200: v_sum = x + y + z;

% edge length sum of first lower piece
var 20..300: edge_sum1 = bc_sum + v_sum;

% edge length sum of second upper piece
var 20..300: edge_sum2 = bc_sum + 3 * ht - v_sum;

% pythagorean constraints on three prism faces
constraint d * d == a * a + (y - x) * (y - x);
constraint e * e == b * b + (z - x) * (z - x);
constraint f * f == c * c + (z - y) * (z - y);

% more than half  the lower prism edges are prime
constraint ( bool2int(is_prime(a)) + bool2int(is_prime(b))
 + bool2int(is_prime(c)) + bool2int(is_prime(d)) 
 + bool2int(is_prime(e)) + bool2int(is_prime(f)) 
 + bool2int(is_prime(x)) + bool2int(is_prime(y)) 
 + bool2int(is_prime(z)) ) > 4;

constraint is_prime(edge_sum1) /\ is_prime(edge_sum2);   

constraint ht > z;

solve satisfy;

output ["Base triangle sides are: " 
++ show(a) ++ ", " ++ show(b) ++ ", " ++ show(c)]

++ ["\nHeights to fracture plane: " ++
show(x) ++ ", " ++ show(y) ++ ", " ++ show(z)]

++ ["\nSides of fracture plane: "
++ show(d) ++ ", " ++ show(e) ++ ", " ++ show(f)]

++["\nEdge total length of 2nd piece: " ++ show(edge_sum2)];

% Base triangle sides are: 5, 7, 9
% Heights to fracture plane: 23, 35, 47
% Sides of fracture plane: 13, 25, 15
% Edge total length of 2nd piece: 113
% % time elapsed: 0.02 s
% ----------
% Base triangle sides are: 5, 7, 9
% Heights to fracture plane: 19, 31, 43
% Sides of fracture plane: 13, 25, 15
% Edge total length of 2nd piece: 113
% % time elapsed: 0.58 s
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 9:42 am on 22 January 2020 Permalink | Reply
    Tags:   

    Teaser 2991: Super Street 

    From The Sunday Times, 19th January 2020 [link] [link]

    George and Martha and their five daughters with their families have moved into six houses in Super Street. I define a “super prime number” as a prime number which has at least two digits adding up to a prime number (e.g. 11 and 23). Similarly for “super squares” (e.g. 36) and “super cubes”. Houses in Super Street are numbered with the lowest 31 super numbers of the above types.

    The elderly couple live in the highest-numbered house on the street. They noticed that the last digits of their daughters’ houses were five consecutive digits and the sum of their five house numbers was a perfect square. Furthermore, the ordinal positions (lowest-numbered house is 1 and so on) of all but one of the houses were prime.

    Which five houses did the daughters occupy?

    [teaser2991]

     
    • Jim Randell's avatar

      Jim Randell 9:43 am on 22 January 2020 Permalink | Reply

      I took the definition of a “super-p” number n to be as follows:

      n has property p;
      The digit sum of n also has property p;
      n has more than 1 digit.

      This seems to be the required interpretation (a possible alternative interpretation gives no solutions).

      This Python program runs in 140ms.

      Run: [ @replit ]

      from heapq import merge
from enigma import (nsplit, primes, irange, inf, is_square, is_cube, first, uniq, subsets, tuples, printf)

# generate "super" numbers from iterator <s> must have at least 2
# digits, and the digit sum must satisfy <f>
def sup(s, f):
  for n in s:
    if n < 10: continue
    if f(sum(nsplit(n))):
      yield n

# "super" primes, squares, cubes
sp = sup(primes, primes.is_prime)
ss = sup((x**2 for x in irange(1, inf)), is_square)
sc = sup((x**3 for x in irange(1, inf)), is_cube)

# select the first 31 "super" numbers
ns = first(uniq(merge(sp, ss, sc)), 31)
printf("[ns={ns}]")

# G+M live in the highest numbered house
GM = ns.pop(-1)
printf("GM = {GM}")

# map the remaining numbers to ordinal values (starting at 1)
m = dict((n, i) for (i, n) in enumerate(ns, start=1))

# check a sequence is consecutive
is_consecutive = lambda s: all(a + 1 == b for (a, b) in tuples(s, 2))

# consider numbers of the five daughters
for ds in subsets(ns, size=5):
  # sum of the numbers is a square
  if not is_square(sum(ds)): continue
  # the units digits form a consecutive sequence
  if not is_consecutive(sorted(d % 10 for d in ds)): continue
  # exactly 4 of their ordinals are prime
  if not (sum(primes.is_prime(m[d]) for d in ds) == 4): continue
  # output solution
  printf("ds = {ds}")

      Solution: The house numbers of the daughters are: 23, 125, 137, 144, 196.

      George and Martha live at house number 199 (super-prime).

      The daughters live at the following house numbers:

      23 (super-prime, 2nd house)
      125 (super-cube, 17th house)
      137 (super-prime, 19th house)
      144 (super-square, 21st house)
      196 (super-square, 29th house)

      The sum of the house numbers is 625 (= 25²).

      And the units digits form the sequence: (3, 4, 5, 6, 7).

      The ordinal of house number 144 is not prime, but the rest are.

      If we allow single digit “super” numbers, then we get the following solution:

      George and Martha live at house number 157 (super-prime).

      The daughters live at the following house numbers:

      2 (super-prime, 2nd house)
      41 (super-prime, 13th house)
      100 (super-square, 21st house)
      113 (super-prime, 23rd house)
      144 (super-square, 29th house)

      The sum of the house numbers is 400 (= 20²).

      And the units digits form the sequence: (0, 1, 2, 3, 4).

      The ordinal of house number 100 is not prime, but the rest are.

      Like

    • Frits's avatar

      Frits 10:59 pm on 22 December 2020 Permalink | Reply

      Preprocessing was necessary to get run time under a second. While doing that I also could have stored the generated super numbers.

      from enigma import SubstitutedExpression, is_prime, is_square, is_cube

def is_super(n):
  A = n // 100
  B = (n % 100) // 10
  C = n % 10
  return (is_square(n) != None and is_square(A+B+C) != None) or \
         (is_cube(n) != None and is_cube(A+B+C) != None) or \
         (is_prime(n) and is_prime(A+B+C))

# calculate ordinal number (inefficient but infrequently called)         
ord = lambda n: sum(is_super(i) for i in range(11, n)) + 1

(t, min_d2i, sup31) = (0, 0, 0)
# find 31st super number 
for i in range(11, 220):
  if is_super(i): t += 1
  if t == 31:
    min_d2i = (i // 100) + 1
    sup31 = i
    break


# the alphametic puzzle
p = SubstitutedExpression(
  [
  # 5 daughters live at super numbers
  "is_super(ABC)",
  "ABC > 9",
  "is_super(DEF)",
  "DEF > 9",
  "is_super(GHI)",
  "GHI > 9",
  "is_super(JKL)",
  "JKL > 9",
  "is_super(MNO)",
  "MNO > 9",
  
  "ABC < DEF",
  "DEF < GHI",
  "GHI < JKL",
  "JKL < MNO",
  
  # the last digits of their daughters' houses were five consecutive digits
  "max([C, F, I, L, O]) - min([C, F, I, L, O]) == 4",
  
  # all different numbers
  "len([ABC, DEF, GHI, JKL, MNO]) == len(set([ABC, DEF, GHI, JKL, MNO]))",
  
  # the sum of their five house numbers was a perfect square
  "is_square(sum([ABC, DEF, GHI, JKL, MNO]))",
    
  # houses in Super Street are numbered with the lowest 31 super numbers.
  # the elderly couple live in the highest-numbered house on the street. 
  "max([ABC, DEF, GHI, JKL, MNO]) < " + str(sup31),
 
  # the ordinal positions (lowest-numbered house is 1 and so on) 
  # of all but one of the houses were prime.
  "sum([is_prime(ord(ABC)), is_prime(ord(DEF)), is_prime(ord(GHI)), \
is_prime(ord(JKL)), is_prime(ord(MNO))]) == 4",
  
  ],
  answer="ABC, DEF, GHI, JKL, MNO",
  d2i=dict([(k, "ADGJM") for k in range(min_d2i, 10)]),
  env=dict(is_super=is_super, ord=ord),
  # last digits of their daughters' houses are different
  distinct="CFILO",
  verbose=0)   

# print answers 
for (_, ans) in p.solve():
  print(f"{ans}")

      Like

  • Unknown's avatar

    Jim Randell 5:07 pm on 10 January 2020 Permalink | Reply
    Tags:   

    Teaser 2990: Squares and cubes 

    From The Sunday Times, 12th January 2020 [link] [link]

    Jenny is pleased that she has found two whole numbers with a remarkable property. One of them is a single digit greater than zero while the other one has two digits. The remarkable thing is that the difference of their squares is a perfect cube and the difference of their cubes is a perfect square.

    Her sister Sarah is not impressed, however. She has found two three-digit numbers for which the difference of their squares is also a perfect cube and the difference of their cubes is also a perfect square.

    In ascending order, what are the four numbers?

    [teaser2990]

     
    • Jim Randell's avatar

      Jim Randell 5:24 pm on 10 January 2020 Permalink | Reply

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

      The following Python program runs in 179ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, sprintf as f, cproduct)

# solve for alphametic n1, n2 (where n1 < n2)
def solve(label, n1, n2, **kw):
  p = SubstitutedExpression(
    [ f("is_cube(sq({n2}) - sq({n1}))"), f("is_square(cb({n2}) - cb({n1}))") ],
    distinct="",
    answer=f("({n1}, {n2})"),
    **kw
  )
  ss = list()
  for ans in p.answers(verbose=0):
    print(f("{label}: {ans}"))
    ss.append(ans)
  return ss

# find the answers for each girl
jss = solve("Jenny", "A", "BC", d2i={ 0: "AB" })
sss = solve("Sarah", "ABC", "DEF")

# output solutions
for (js, ss) in cproduct([jss, sss]):
  print(f("numbers = {ns}", ns=js + ss))

      Solution: The four numbers are: 6, 10, 384, 640.

      Jenny’s numbers are 6 and 10:

      10² − 6² = 64 = 4³
      10³ − 6³ = 784 = 28²

      Sarah’s numbers are 384 and 640:

      640² − 384² = 262144 = 64³
      640³ − 384³ = 205520896 = 14336²

      They are related in that Sarah’s numbers are 64 (=2^6) times Jenny’s.

      For any (n, m) solution, then (k.n, k.m) is also a solution, where k = z^6.

      m^2 − n^2 = x^3
      m^3 − n^3 = y^2
      (k.m)^2 − (k.n)^2 = (k^2)(m^2) − (k^2)(n^2) = (k^2)(m^2 − n^2) = (k^2)(x^3) = ((z^4)x)^3
      (k.m)^3 − (k.n)^3 = (k^3)(m^3) − (k^3)(n^3) = (k^3)(m^3 − n^3) = (k^3)(y^2) = ((z^9)y)^2

      This method accounts for the first three solutions (by increasing x):

      (6, 10)
      (384, 640) = (6, 10) × 2^6
      (4374, 7290) = (6, 10) × 3^6

      but not all solutions are multiples of (6, 10) – the next few are:

      (5687, 8954)
      (64350, 70434)
      (24576, 40960) = (6, 10) × 4^6
      (27783, 55566)
      (17576, 52728)
      (93750, 156250) = (6, 10) × 5^6
      (354375, 405000)
      (279936, 466560) = (6, 10) × 6^6
      …

      Like

    • Jim Randell's avatar

      Jim Randell 10:20 pm on 11 January 2020 Permalink | Reply

      The following Python program generates (n, m) and (x, y) pairs where:

      n < m
      m² − n² = x³
      m³ − n³ = y²

      It runs in 104ms to solve this puzzle, but the [[ generate() ]] function can be used to generate larger numbers with the required property.

      Run: [ @replit ]

      from enigma import (irange, inf, divisors_pairs, div, is_square, cproduct, printf)

# generate (n, m, x, y) where m^2 - n^2 = x^3, m^3 - n^3 = y^2
def generate(start=1):
  for x in irange(start, inf):
    cube = x**3
    for (a, b) in divisors_pairs(cube):
      m = div(a + b, 2)
      if m is None: continue
      n = m - a
      if n < 1: continue
      y = is_square(cube * m + a * n * n)
      if y is None: continue
      yield (n, m, x, y)

# find the answers for each girl
(jss, sss) = (list(), list())
for (n, m, x, y) in generate():
  if n < 10 and 9 < m < 100:
    printf("Jenny: ({n}, {m}) -> ({x}, {y})")
    jss.append((n, m))
  if 99 < n and m < 1000:
    printf("Sarah: ({n}, {m}) -> ({x}, {y})")
    sss.append((n, m))
  if n > 999:
    break

# output solutions
for (js, ss) in cproduct([jss, sss]):
  printf("numbers = {ns}", ns=js + ss)

      Like

    • GeoffR's avatar

      GeoffR 9:32 am on 12 January 2020 Permalink | Reply 

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

% Jenny's numbers are A and BC
var 1..9:A; var 10..99:BC;

% Sarah's numbers are DEF and GHI
var 100..999:DEF; var 100..999:GHI;
constraint GHI > DEF;

predicate is_cube(var int: c) =
   let {
      var 0..ceil(pow(int2float(ub(c)),(1/3))): z
   } in z*z*z = c;
   
predicate is_sq(var int: c) =
   let {
      var 0..ceil(pow(int2float(ub(c)),(1/2))): z
   } in z*z = c;
   
% Jenny's numbers   
constraint is_cube(BC * BC - A * A);
constraint is_sq(BC * BC * BC - A * A * A);

% Sarah's numbers
constraint is_cube(GHI * GHI - DEF * DEF);
constraint is_sq(GHI * GHI * GHI - DEF * DEF * DEF);

solve satisfy;

output["Four numbers are " ++ show(A) ++ ", " ++ show(BC) 
++ ", " ++ show(DEF) ++ ", " ++ show(GHI)];

      Like

    • Frits's avatar

      Frits 7:24 pm on 25 July 2020 Permalink | Reply 

      from enigma import SubstitutedExpression, printf

# the alphametic puzzle
p = SubstitutedExpression([
    "A != 0",
    "is_cube((BC * BC) - (A * A))",
    "is_square(BC * BC * BC - A * A * A)",
    "DEF != GHI",
    "is_cube(GHI * GHI - DEF * DEF)",
    "is_square(GHI * GHI * GHI - DEF * DEF * DEF)",
  ],
  answer="(A, BC, DEF, GHI)",
  distinct="", # allow symbols with same values
)

# print answers
for (_, ans) in p.solve(verbose=0):
  printf("answer = {ans}")

      I modified the is_cube() function in my enigma.py version to first eliminate almost 95% of the cases. The above code ran approx 3 time faster.

      if n % 819 not in {
    0,1,8,27,64,90,91,99,118,125,161,181,190,216,252,260,
    287,307,343,350,351,377,378,441,442,468,469,476,512,
    532,559,567,603,629,638,658,694,701,720,728,729,755,
    792,811,818
  }:
    return False

      Hi Jim, is there a place where general questions (like why you sometimes do it the hard way) or technical questions (like if the code can be changed to allow p = SubstitutedExpression( […] ) constructs to use comments)?

      Like

      • Jim Randell's avatar

        Jim Randell 11:08 pm on 25 July 2020 Permalink | Reply

        @Frits: Thanks for your comment. I’ve cleaned up the formatting a bit.

        If there are any specific questions about my code I’m happy to try and answer them for you.

        I did write a run file for this puzzle that uses a single [[ SubstitutedExpression() ]] recipe (see: [ @repl.it ]), but I preferred to treat the two parts as separate recipes, which would be better if there were multiple solutions (although there aren’t, but I prefer the general approach).

        In the end though I wrote a specialised routine to generate numbers with the described behaviour, that can be used to solve this puzzle, and also find larger numbers with the same property. (I put a list up here [ @repl.it ]).

        I special cased the [[ is_square() ]] function to do early rejection as it is used a lot in puzzles, but the [[ is_cube() ]] function is just wrapper around [[ is_power() ]], but I’ll look at adding in some early rejection as you suggest.

        I’m not sure what you mean about adding comments into the [[ SubstitutedExpression() ]] solver. If you use it in a regular Python program (as you have) you can just use normal Python comments, and if you encapsulate it in a run-file (as I have above), then you can use “shell like” comments, which are discarded when the file is executed by enigma.py.

        Like

    • Frits's avatar

      Frits 7:49 pm on 26 July 2020 Permalink | Reply

      @Jim: Thanks for the quick response.

      I am only a beginning developer in Python.

      Is there a reason why in the is_square function you don’t check the “is_square.residues” set with the “not in” operator?

      You now generate the list “is_square.reject” from the set “is_square.residues”.
      A direct lookup of a list item is of O(1) complexity but as I have understood the set “not in” also has a complexity O(1) (avg). Do you know if collisions can be expected?

      I did some performance testing with “get item” for a list and a “not in” for a set (the mod 819 numbers) and saw no difference.

      Do you also consider adding a minimize/maximize function within SubstitutedExpression?

      I have seen you using the Accumulator function for this need (but outside SubstitutedExpression).

      Like

      • Jim Randell's avatar

        Jim Randell 11:00 pm on 26 July 2020 Permalink | Reply

        @Frits: I hope you enjoy using Python. I was new to it myself when I started coding Enigma puzzles on Enigmatic Code. But I find it is usually quite succinct and understandable. The enigma.py library represents my accumulation of useful routines and refinements from the last 10 years of solving this kind of puzzle. I hope you find it useful.

        With regards to the code in [[ is_square ]] I was looking at it yesterday and couldn’t see any reason for the reject dictionary, so I’ve changed the code to just using residues directly (and also added similar code to the [[ is_cube ]] function, as you suggested. This is available in the 2020-07-27 version of enigma.py. (It was quite old code, and I didn’t use to use set() as much back then).

        I have thought once or twice about adding some collection functionality for answers inside the [[ SubstitutedExpression() ]] solver, but it isn’t used in very many alphametic puzzles, and (as you say) it can be achieved using other functionality already present in enigma.py, so it’s never quite made it to the top of my list of things to do.

        Like

      • Jim Randell's avatar

        Jim Randell 10:32 am on 29 July 2020 Permalink | Reply

        In enigma.py version 2020-07-29 I’ve added a [[ accumulate ]] parameter to the [[ SubstitutedExpression() ]] solver.

        The [[ SubstitutedExpression.run() ]] method (formerly called [[ go() ]]) finds and outputs solutions to the alphametic problem specified, and counts the number of solutions. The number of solutions is returned in the [[ n ]] attribute of the return value.

        If the [[ answer ]] parameter has been specified, then the result of the specified expression is collection for each solution, and all answers are returned as a [[ multiset() ]] in the [[ answer ]] attribute of the return value.

        If, additionally, the [[ accumulate ]] parameter has been specified, then the result of applying the specified function(s) to the collected answers is returned in the [[ accumulate ]] attribute of the return value.

        See my comment on Teaser 2947 for an example of this functionality in use.

        (I am also working on allowing the [[ verbose ]] parameter to be specified as a collection of flags, rather than a number, but that’s not ready yet).

        Like

    • Frits's avatar

      Frits 4:08 pm on 13 August 2020 Permalink | Reply

      Generate solver code:

      from enigma import is_cube, is_square 
from re import findall

not_cube = lambda l, m: not(is_cube(l*l - m*m))
not_square = lambda l, m: not(is_square(l*l*l - m*m*m))

# "DEF" --> "DEF = D*100+E*10+F"
formula = lambda w: w + " = " + "".join(w[i]+"*"+str(10**(len(w)-i-1))+"+"  
                 for i in range(len(w)-1))+w[-1]

# do all elements in a reside in b?
within = lambda a, b: all(i in b for i in a)

# "1-9" --> "range(1,10)"
def rng(s):      
  a = s.split("-", 1)
  return "range("+a[0]+","+str(int(a[1])+1)+")"
  

exprs = []
# 0: loop letter, 1: range, 2: dismiss condition 
exprs.append(["B",  "1-9", ""])
exprs.append(["C",  "0-9", ""])
exprs.append(["A",  "1-9", "not_square(BC, A) or not_cube(BC, A)"])
exprs.append(["D",  "1-9", ""])
exprs.append(["EF", "0-9", ""])
exprs.append(["G",  "1-9", ""])
exprs.append(["HI", "0-9", "DEF == GHI"])
exprs.append(["", "", "not_square(GHI, DEF) or not_cube(GHI, DEF)"])


# Build list of multi-letter words
words = set()
for expr in exprs:
  if expr[2] != "": 
    for w in findall('[A-Z]{2,}', expr[2]):
       words.add(w)

done = []
ex = ind = letters = ""

# Generate nested code
for j in range(0, len(exprs)):
  expr = exprs[j]
  # add range
  if expr[0] != "":
    if '-' in expr[1]: lrange = rng(expr[1])
    else: lrange = expr[1]
    for let in expr[0]:
      ex += ind + "for " + let + " in " + lrange + ":\n"
      ind += "  "
      letters += let
  
      # expand variable if needed
      if len(letters) > 0: 
        for w in words:
          if not(w in done) and within(w, letters):
            ex += ind + formula(w) + "\n"
            done.append(w)

  # add dismiss condition 
  if expr[2] != "": 
    ex += ind +"if " + expr[2] + ": continue\n"
 
  # last exprs element?
  if len(exprs) - j < 2:
    ex += ind + "print(A,BC,DEF,GHI)\n"
    
#print(ex)

print("A BC DEF GHI")
print("------------")
exec(ex)

# A BC DEF GHI
# ------------
# 6 10 384 640

      Generated code:

      for B in range(1,10):
  for C in range(0,10):
    BC = B*10+C
    for A in range(1,10):
      if not_square(BC, A) or not_cube(BC, A): continue
      for D in range(1,10):
        for E in range(0,10):
          for F in range(0,10):
            DEF = D*100+E*10+F
            for G in range(1,10):
              for H in range(0,10):
                for I in range(0,10):
                  GHI = G*100+H*10+I
                  if DEF == GHI: continue
                  if not_square(GHI, DEF) or not_cube(GHI, DEF): continue
                  print(A,BC,DEF,GHI)

      Enigma.py sometimes calculates BC too many times as the first 3 loops of the SubstitutedExpression generated code are over A, B and C instead of B, C and A. Option “reorder=1” doesn’t seem to recognize this. The issue is minor.

      Example 1:

      p = SubstitutedExpression(
  [ "is_cube((A * A) + (BC * BC))" ,
    "is_square(BC * BC * BC - A * A * A)" ,     
    "DEF != GHI" ,
    "is_cube(GHI * GHI - DEF * DEF)" ,
    "is_square(GHI * GHI * GHI - DEF * DEF * DEF)" ,
  ],
  answer="(A,BC,DEF,GHI)",
  d2i={ 0: "ABDG" },
  verbose=256,
  reorder=1,
  distinct="",    # allow symbols with same values
)

      loops over A, B and C

      Example 2:

      p = SubstitutedExpression(
  [ "is_cube((BC * BC) - (A * A))" ,
    "is_square(BC * BC * BC - A * A * A)" ,     
    "DEF != GHI" ,
    "is_cube(GHI * GHI - DEF * DEF)" ,
    "is_square(GHI * GHI * GHI - DEF * DEF * DEF)" ,
  ],
  answer="(A,BC,DEF,GHI)",
  d2i={ 0: "ABDG" },
  verbose=256,
  reorder=1,
  distinct="",    # allow symbols with same values
)

      loops over B,C and A (as BC is the first variable)

      Like

      • Jim Randell's avatar

        Jim Randell 11:45 am on 14 August 2020 Permalink | Reply

        @Frits:

        The [[ reorder ]] parameter only affects the order that the solver considers the expressions. If it is enabled (the default) it will use a heuristic that chooses the next expression by considering how much work is required to give values to the symbols involved in it. If it is disabled the expressions are just considered in the order they are presented.

        The solver does no introspection of the expression, other than to determine what symbols are used in it. So when it sees: [[ "is_cube(YZ**2 - X**2)" ]] it just sees it as an expression involving X, Y, Z, and generates the appropriate code. The actual loops will be generated in an arbitrary order.

        The [[ verbose ]] level 128 will output the strategy that the solver is using, showing the order the expressions will be evaluated in, and a [x+y] count where x is the number of symbols to consider, and y is the number of additional symbols that can then be determined.

        I do have a TODO note in the code for [[ SubstitutedExpression() ]] to look at ordering the symbols in such a way that alphametic words can be constructed as soon as possible, but I don’t think it will give a significant improvement in run times. However, I might look at it again when I have some time.

        Like

    • Frits's avatar

      Frits 1:03 pm on 14 August 2020 Permalink | Reply

      @ Jim,

      Thanks. It might be worthwile to look at list comprehensions for generated code in SubstitutedExpression.

      I got a performance improvement when I replaced code like:

      for S in range(1,10):
          if S in {G,D,L,A}: continue

      with

      notIn = lambda w: [x for x in range(1,10) if x not in w]

and

for S in notIn({D,G,L,A}):

      Like

      • Jim Randell's avatar

        Jim Randell 10:44 pm on 15 August 2020 Permalink | Reply

        @Frits: Thanks for the suggestion. I’ve done some testing and unfortunately generating code as you suggest doesn’t give a speed improvement for me (compared to the current approach). Performance figures are of course very dependent on the precise nature of the system that you are running the tests on.

        Like

    • GeoffR's avatar

      GeoffR 10:00 am on 7 December 2024 Permalink | Reply 

      def is_sq(n):
  if round(n ** 0.5) ** 2 == n:
    return True
  return False

def is_cube(n):
  if round(n ** (1/3)) ** 3 == n:
    return True
  return False

# Jenny's single and 2-digit numbers
for a in range(1, 10):
    for b in range(10, 100):
        c1 = b**2 - a**2
        if not is_cube(c1):continue
        sq1 = b**3 - a**3
        if not is_sq(sq1):continue
        
        # Sarah's two 3-digit numbers
        for n1 in range(100, 999):
            for n2 in range(n1 + 1, 999):
                if not is_cube(n2**2 - n1**2):continue
                if not is_sq(n2**3 - n1**3):continue
                print(f"The four numbers are {a}, {b}, {n1} and {n2}.")

# The four numbers are 6, 10, 384 and 640.

      Like

  • Unknown's avatar

    Jim Randell 8:55 am on 4 January 2020 Permalink | Reply
    Tags:   

    Teaser 2989: Pot luck 

    From The Sunday Times, 5th January 2020 [link] [link]

    Liam had a bag of snooker balls containing 6 colours (not red) and up to 15 red balls. He drew out balls at random, the first being a red. Without replacing this he drew another ball; it was a colour. He replaced this and drew another ball. This was a red (not replaced), and he was able to follow this by drawing another colour. The probability of achieving a red/colour/red/colour sequence was one in a certain whole number.

    After replacing all the balls, Liam was able to “pot” all the balls. This involved “potting” (i.e., drawing) red/colour/red/colour… red/colour (always replacing the colours but not the reds), then “potting” the six colours (not replaced) in their correct sequence. Strangely, the probability of doing this was also one in a whole number.

    What are the two whole numbers?

    [teaser2989]

     
    • Jim Randell's avatar

      Jim Randell 9:30 am on 4 January 2020 Permalink | Reply

      This Python program calculates P(k, n), the probability of selecting n consecutive red/colour pairs (with the red not replaced and the colour replaced), if k reds are available initially (and 6 colours).

      It runs in 83ms.

      Run: [ @replit ]

      from enigma import (Rational, irange, factorial, printf)

Q = Rational()

# calculate the probability of a red/colour sequence of length n
# with k reds available (and m colours)
def P(k, n, m=6):
  t = k + m
  p = Q(1)
  for _ in irange(1, n):
    p *= Q(k, t)
    k -= 1
    t -= 1
    p *= Q(m, t)
  return p

# consider possible numbers of reds (between 2 and 15)
for k in irange(2, 15):
  # calculate probability of 2 (red, colour) pairs
  p2 = P(k, 2)
  if not (p2.numerator == 1): continue

  # and of k (red, colour) pairs
  pk = P(k, k)

  # the probability of drawing the six colours in order = 1/6!
  p = Q(pk, factorial(6))
  if not (p.numerator == 1): continue

  # output solution
  printf("[k={k}] P({k}, 2) = {p2}; P({k}, {k}) = {pk}; p = {p}")

      Solution: The two numbers are 15 and 352,800 (i.e. the probabilities are 1/15 and 1/352,800).

      When there are k reds available (and 6 colours) the probability of selecting a red (not replaced) followed by a colour (to be replaced) is:

      P(k, 1) = (k / (k + 6)) × (6 / (k + 5)) = 6k / (k + 5)(k + 6)

      When there are 4 reds available the probability of select the first red/colour pair is:

      P(4, 1) = 4/15

      There are now 3 reds available, and the probability of selecting a second red/colour pair is:

      P(3, 1) = 1/4

      Multiplying these together we get a probability of select two red/colour pairs in a row as:

      P(4, 2) = P(4,1) × P(3,1) = 4/15 × 1/4 = 1/15

      The probabilities of selecting a third and fourth red/colour pair are:

      P(2, 1) = 3/14
      P(1, 1) = 1/7

      Combining all these we get:

      P(4, 4) = P(4, 1) × P(3, 1) × P(2, 1) × P(1, 1) = 4/15 × 1/4 × 3/14 × 1/7 = 1/490

      The probability of selecting the six colours in the correct order is: 1/6! = 1/720.

      Giving a probability of “clearing the table” of:

      p = P(4, 4) / 6! = 1/352,800

      Like

  • Unknown's avatar

    Jim Randell 9:42 am on 2 January 2020 Permalink | Reply
    Tags: by: Sir Bryan Thwaites   

    Brainteaser 1783: Nine, eight, seven, … 

    From The Sunday Times, 17th November 1996 [link]

    If you place a digit in each of the above boxes then you can read some numbers horizontally (left to right), vertically (top to bottom) and diagonally (top left to bottom right and bottom left to top right).

    Your task is to place:

    • nine digits, one in each box, so that you can then read …
    • eight three-figure numbers, at least …
    • seven of which are different primes, and so that at least …
    • six of the eight are palindromic, and so that at least …
    • five of the digits in the bottom two rows are odd.

    Fill in the boxes.

    This puzzle is included in the book Brainteasers (2002) under the title “Nine, Eight, Seven, Six, …”. The puzzle text above is taken from the book. In the original puzzle the final condition (“five …”) was not included, and the required answer was just the value of the digit in the central box.

    [teaser1783]

     
    • Jim Randell's avatar

      Jim Randell 9:44 am on 2 January 2020 Permalink | Reply

      If we label the grid as follows:

      then the 8 numbers we are interested in are:

      ABC, DEF, GHI, ADG, BEH, CFI, AEI, GEC

      We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve the puzzle directly, but it is a bit slow. (It takes over 5 minutes to run to completion).

      #! python -m enigma -rr

SubstitutedExpression

--distinct=""

# at least seven of the numbers are different primes
"icount(set([ABC, DEF, GHI, ADG, BEH, CFI, AEI, GEC]), is_prime) > 6"

# at least six of them are palindromic
"icount([ABC, DEF, GHI, ADG, BEH, CFI, AEI, GEC], is_npalindrome) > 5"

# at least five of the digits in the bottom two rows are odd
--code="is_odd = lambda x: x % 2 == 1"
"icount([D, E, F, G, H, I], is_odd) > 4"

# solution
--answer="(ABC, DEF, GHI)"

      So we can do some analysis to make things a bit easier:

      If a number is a palindrome, then its first and last digit are the same.

      Looking at the 6 numbers: ABC, GHI, ADG, CFI, AEI, GEC, we get the following graph equating the values of symbols if they are all palindromes:

      But at most 2 of them are not necessarily palindromes, and it is not possible to remove just 2 edges from the graph to form a disconnected segment.

      Hence A, C, G, I must all be the same (odd) digit (say, X).

      So we can consider the grid:

      and the 8 numbers are:

      XBX, DEF, XHX, XDX, BEH, XFX, XEX, XEX

      We see that the two diagonals take on the same value, so there are actually only 7 different numbers (all of which must all be prime), and 6 of the numbers are palindromes by definition, so we don’t need to worry about looking for additional palindromes.

      The following run file executes in 486ms.

      Run: [ @replit ]

      #! python -m enigma -rr

SubstitutedExpression

# there are 7 different primes
"icount(set([XBX, DEF, XHX, XDX, BEH, XFX, XEX]), is_prime) > 6"

# at least five of the digits in the bottom two rows are odd
--code="is_odd = lambda x: x % 2 == 1"
"icount([D, E, F, X, H, X], is_odd) > 4"

# solution
--answer="(XBX, DEF, XHX)"

      Solution: The completed grid is:

      So the eight numbers are:

      181 (prime, palindrome)
      503 (prime)
      191 (prime, palindrome)
      151 (prime, palindrome)
      809 (prime)
      131 (prime, palindrome)
      101 (prime, palindrome)
      101 (prime, palindrome)

      There are 7 different primes and 6 palindromes. The number 101 is repeated.

      Without the constraint that at least 5 of the 6 numbers in the bottom two rows are odd we can also have the following reflection:

      But in both cases the central square contains the digit 0.

      Like

    • GeoffR's avatar

      GeoffR 10:40 am on 3 January 2020 Permalink | Reply

      I used Jim’s alternative grid to find a permutation solution

      
# ABC   XBX
# DEF   DEF
# GHI   XHX

from time import perf_counter_ns
start = perf_counter_ns()

from enigma import is_prime
list_pal =[]

def is_pal3(abc):
    a = abc // 100
    b = abc //10 % 10
    c = abc % 10
    if a == c and b != a:
        return True
    return False

from itertools import permutations
for p in permutations('1234567890',6):
  x, b, d, e, f, h = p
  if any (z == '0' for z in (x, h, d, f, b)): continue
  # nos are xbx, DEF, xhx, xdx, beh, xfx, xex
  xbx, DEF = int(x+b+x), int(d+e+f)
  xhx, xdx = int(x+h+x), int(x+d+x)
  beh, xfx, xex = int(b+e+h), int(x+f+x), int(x+e+x)
  if all(is_prime(z) for z in (xbx, DEF, xhx, xdx, beh, xfx, xex)):
    # check for palindrome numbers 
    if is_pal3(xbx): list_pal.append(xbx)
    if is_pal3(DEF): list_pal.append(DEF)
    if is_pal3(xhx): list_pal.append(xhx)
    if is_pal3(xdx): list_pal.append(xdx)
    if is_pal3(beh): list_pal.append(beh)
    if is_pal3(xfx): list_pal.append(xfx)
    if is_pal3(xex): list_pal.append(xex)
    
    # we are looking for five palindromes in this grid
    if len(set(list_pal)) == 5:
      # check there are 4 odd digits in bottom two rows in this grid
      set_odd = set()
      if int(d) % 2 == 1: set_odd.add(d)
      if int(e) % 2 == 1: set_odd.add(e)
      if int(f) % 2 == 1: set_odd.add(f)
      if int(x) % 2 == 1: set_odd.add(x)
      if int(h) % 2 == 1: set_odd.add(h)
      if len(set_odd) == 4:
        # print the 3 by 3 grid
        print(xbx)
        print(DEF)
        print(xhx)
        print(f"{(perf_counter_ns() - start) / 1e6:.3f} ms")

# 181
# 503
# 191
# 144.905 ms

      Like

    • GeoffR's avatar

      GeoffR 3:56 pm on 6 January 2020 Permalink | Reply

      I used two list comprehensions in Python to shorten my code, which also meant I could omit the palindrome function.

      
# Grid rows are: XBX, DEF and XHX
from itertools import permutations
from enigma import is_prime

pal3, odd = [], []

for p in permutations('1234567890', 6):
  x, b, d, e, f, h = p
  if any (z == '0' for z in (x, h, d, f, b)): continue
  
  # Seven grid numbers are xbx, DEF, xhx, xdx, beh, xfx, xex
  xbx, DEF = int(x + b + x), int(d + e + f)
  xhx, xdx = int(x + h + x), int(x + d + x)
  beh, xfx, xex = int(b + e + h), int(x + f + x), int(x + e + x)
   
  # check all seven numbers are prime
  if all(is_prime(z) for z in (xbx, DEF, xhx, xdx, beh, xfx, xex)):
      
    # check for five palindrome numbers
    pal3 = [ x for x in (xbx, DEF, xhx, xdx, beh, xfx, xex) \
            if (x // 100 == x % 10 and x // 100 != x // 10 % 10)]    
    if len(pal3) == 5:
        
      # check for four odd digits in bottom two rows of grid
      odd = [int(z) for z in (d, e, f, x, h) if int(z) % 2 == 1]
      if len(odd) == 4:
        print(f"Grid rows are: {xbx}, {DEF}, {xhx} ")
        
# Grid rows are: 181, 503, 191

      Like

  • Unknown's avatar

    Jim Randell 4:25 pm on 27 December 2019 Permalink | Reply
    Tags:   

    Teaser 2988: Open the box 

    From The Sunday Times, 29th December 2019 [link] [link]

    Game show contestants are shown a row of boxes, each containing a different sum of money, increasing in regular amounts (eg, £1100, £1200, £1300, …), but they don’t know the smallest amount or the order. They open one box then take the money, or decline that and open another box (giving them the same choices, apart from opening the last box when they have to take the money).

    Alf always opens boxes until he finds, if possible, a sum of money larger than the first amount. Bert’s strategy is similar, except he opens boxes until he finds, if possible, a sum of money larger than both of the first two amounts. Remarkably, they can both expect to win exactly the same amount on average.

    How many boxes are there in the game?

    [teaser2988]

     
    • Jim Randell's avatar

      Jim Randell 4:37 pm on 27 December 2019 Permalink | Reply

      With k boxes, we always win a base amount, along with some multiple of the increment. So we can just consider the boxes to take on the values from 1 to k.

      This Python program considers increasing numbers of boxes, looking at the total winnings for A and B for all possible arrangements of boxes. Until it finds two totals with the same value. It runs in 75ms.

      Run: [ @repl.it ]

      from enigma import (subsets, irange, inf, printf)

# strategy, take the first amount larger than the first n boxes
def strategy(s, n):
  t = max(s[:n])
  for x in s[n:]:
    if x > t: break
  return x

# strategies for A and B
A = lambda s: strategy(s, 1)
B = lambda s: strategy(s, 2)

# play the game with k boxes
def play(k):
  # collect total winnings for A and B
  tA = tB = 0
  # consider possible orderings of the boxes
  for s in subsets(irange(1, k), size=k, select="P"):
    tA += A(s)
    tB += B(s)
  return (tA, tB)

for k in irange(3, inf):
  (tA, tB) = play(k)
  if tA != tB: continue
  printf("{k} boxes")
  break

      Solution: There are 6 boxes.

      For 3 to 5 boxes A’s strategy is better than B’s. When there are more than 6 boxes B’s strategy is better.

      Using prizes with values from 1..k I found that the average winnings for A and B are:

      k=3: A = 2.333; B = 2.000
      k=4: A = 3.125; B = 2.917
      k=5: A = 3.900; B = 3.800
      k=6: A = 4.667; B = 4.667
      k=7: A = 5.429; B = 5.524
      k=8: A = 6.188; B = 6.375
      k=9: A = 6.944; B = 7.222
      k=10: A = 7.700; B = 8.067
      k=11: A = 8.455; B = 8.909
      k=12: A = 9.208; B = 9.750

      In general we have:

      A(k) = (3k − 2) (k + 1) / 4k
      B(k) = (5k − 6) (k + 1) / 6k

      So, as k increases the ratio of A’s average approaches 3/4 (= 75.0%) of the maximum available prize. And the ratio of B’s average approaches 5/6 (= 83.3%) of the maximum prize.

      From the equations we see that the average winnings are the same when:

      (3k − 2)(k + 1) / 4k = (5k − 6)(k + 1) / 6k
      3(3k − 2) = 2(5k − 6)
      9k − 6 = 10k − 12
      k = 6 (for k > 2)

      In general a strategy of looking at n values and then taking the next highest value gives average winnings from k boxes according to the following formula:

      S(n, k) = ((2n + 1)k² − (n² − n − 1)k − (n² + n)) / (2n + 2)k
      S(n, k) = ((2n + 1)k − n(n + 1)) (k + 1) / 2(n + 1)k

      So: A(k) = S(1, k) and B(k) = S(2, k).

      Like

  • Unknown's avatar

    Jim Randell 8:49 am on 26 December 2019 Permalink | Reply
    Tags:   

    Teaser 2882: Snow White 

    From The Sunday Times, 17th December 2017 [link] [link]

    Snow White placed three balls in a hat (“Oh yes she did!”): written on each ball was a different non-zero digit. She asked one of her little helpers to draw out the three in some order and to use them in that order to make a three-figure number. She knew that this number would be divisible by three but not by seven. She asked the helpers to share out that number of sweets equally amongst the seven of them as far as possible and to give her the remainder. She knew that on seeing the remaining sweets she would be able to work out the order in which the three digits had been drawn out.

    What (in increasing order) were the three digits?

    [teaser2882]

     
    • Jim Randell's avatar

      Jim Randell 8:51 am on 26 December 2019 Permalink | Reply

      This Python program runs in 73ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, group, nconcat, mod, printf)

# available digits
digits = irange(1, 9)

# choose 3 digits
for ds in subsets(digits, size=3, select="C"):
  # any permutation must be divisible by 3
  if sum(ds) % 3 != 0: continue
  # compute the residues of the permutations mod 7
  g = group(subsets(ds, size=len, select="P", fn=nconcat), by=mod(7))
  # there can be no permutations exactly divisible by 7
  if g.get(0): continue
  # there can be no non-zero residue that is ambiguous
  if any(len(v) > 1 for (k, v) in g.items() if k != 0): continue
  # output solution
  printf("digits = {ds} [{g}]")

      Solution: The three digits were: 4, 8, 9.

      They can be assembled into the following 3-digit numbers (and residues modulo 7):

      489 (6)
      498 (1)
      849 (2)
      894 (5)
      948 (3)
      984 (4)

      Each permutation of the digits is uniquely identified by the residue.

      Like

    • GeoffR's avatar

      GeoffR 4:31 pm on 26 December 2019 Permalink | Reply 

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

% Three single digits
var 1..9:A; var 1..9:B; var 1..9:C;
constraint all_different([A, B, C]);

% Residues modulus 7 
var 1..6:a; var 1..6:b; var 1..6:c;
var 1..6:d; var 1..6:e; var 1..6:f;
constraint all_different([a, b, c, d, e, f]);

% Three digit numbers 
var 100..999:ABC = 100*A + 10*B + C;
var 100..999:ACB = 100*A + 10*C + B;
var 100..999:BAC = 100*B + 10*A + C;
var 100..999:BCA = 100*B + 10*C + A;
var 100..999:CAB = 100*C + 10*A + B;
var 100..999:CBA = 100*C + 10*B + A;

% All three digit numbers divisible by three
constraint ABC mod 3 == 0 /\ ACB mod 3 == 0 
/\ BAC mod 3 == 0 /\ BCA mod 3 == 0 
/\ CAB mod 3 == 0 /\ CBA mod 3 == 0;

% All three digit numbers were not divisible by seven
constraint ABC mod 7 == a /\ ACB mod 7 == b
/\ BAC mod 7 == c /\ BCA mod 7 == d
/\ CAB mod 7 == e /\ CBA mod 7 == f; 

constraint increasing([A, B, C]);

solve satisfy;

output[ "The three digits were " ++ show(A) ++ ", " 
++ show(B) ++ ", " ++ show(C)];

% The three digits were 4, 8, 9
% % time elapsed: 0.03 s
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 8:37 am on 22 December 2019 Permalink | Reply
    Tags: ,   

    Brainteaser 1782: Unwinding 

    From The Sunday Times, 10th November 1996 [link]

    Our Vienna clock will run for about eight days when fully wound, so I wind it up each Sunday morning. But last Sunday this caused a problem as, after I had wound it up, the hands started rotating at many times their normal speed. Thereafter they slowed down at a steady rate until they stopped sometime after 5pm.

    Interestingly, they told the correct time on the hour at each hour between winding up and stopping.

    What was the correct time when the clock stopped?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1782]

     
    • Jim Randell's avatar

      Jim Randell 8:38 am on 22 December 2019 Permalink | Reply

      The clock undergoes a period when the hands are rotating (rotating at a constant rate) much faster that normal. Then, at some point, they begin to slow (slowing at a constant rate) until the hands stop completely, some time after 5pm.

      Presumably this happens when the hands indicate a time of “about 8 days” (say 180 – 204 hours) from the winding time (which is sometime before 12pm).

      I made some assumptions to simplify the programming:

      Having not heard of a “Vienna clock” I assumed the clock was a normal 12 hour timepiece.

      I assumed the clock was wound up sometime between 11am and 12pm, and set off advancing at many times normal speed, but at some point at or before 12pm started slowing. After that the amount advanced by the clock at 12pm, 1pm, 2pm, 3pm, 4pm, 5pm, was sufficient that the clock showed the correct time. So each one was actually displaying a time exactly some multiple of 12 hours in advance of the actual time. The clock then stopped sometime between 5pm and 6pm (actual time).

      The following Python code examines this situation. It runs in 289ms.

      Run: [ @repl.it ]

      from fractions import Fraction as F
from enigma import (irange, Polynomial, nsplit, div, sprintf as f)

# format time t as hh:mm:ss.ss
def hms(t, fmt="{h:d}:{m:02d}:{s:05.2f}"):
  (t, r) = divmod(3600.0 * t, 1)
  (h, m, s) = nsplit(int(t), base=60)
  s += r
  return f(fmt)

# consider number of hours advanced at 12pm
for h0 in irange(12, 192, step=12):
  # at 1pm
  for h1 in irange(h0 + 1, 193, step=12):
    # at 2pm
    for h2 in irange(h1 + 1, 194, step=12):
      # use the three points to determine the quadratic equation
      # y = a.x^2 + b.x + c
      q = Polynomial.interpolate([(0, h0), (1, h1), (2, h2)])
      if q is None or len(q) < 3: continue
      (c, b, a) = q

      # does it achieve a maximum in [5, 6]
      if not(a < 0): continue
      m = F(-b, 2 * a)
      if not (5 < m < 6): continue

      # check the times at 3pm, 4pm, 5pm
      hs = [h0, h1, h2]
      for x in (3, 4, 5):
        y = div(q(x), 1)
        if y is not None and y % 12 == x:
          hs.append(y)
      if len(hs) < 6: continue

      # find the earliest start time
      s = F(h0, 1 - b)
      if not (-1 < s < 0): continue

      # check the total time advanced is in the required range (7.5 - 8.5 days)
      t = q(m) - s
      if not (180 < t < 204): continue

      print(f("stop={m} [hs={hs}, start={s}, total={t:.2f}h]", m=hms(m), s=hms(s % 12), t=float(t)))

      Solution: The correct time when the clock stopped was 5:35pm.

      We find a solution, with the number of hours advanced from 12pm at (12pm, 1pm, 2pm, 3pm, 4pm, 5pm) as follows:

      (+12, +73, +122, +159, +184, +197)

      The residues mod 12 of each of the values are:

      (0, 1, 2, 3, 4, 5)

      So we see that the clock would show the correct time on each hour.

      The differences between the successive terms of the sequences are:

      (61, 49, 37, 25, 13)

      Each term decreases by 12 from the previous one, so the clock is slowing at a constant rate, and comes to a stop at x = 67/12, which corresponds to 5:35pm.

      The corresponding quadratic equation is:

      y(x) = −6x² + 67x + 12

      At 12pm the clock is advancing at 67× normal speed (y'(0) = 67), so the maximum possible time after winding would be if immediately after winding, the clock set off at a constant 67× normal speed until 12pm, at which point it began to slow down.

      This places the earliest winding time at 11:49:05.5am.

      If the clock starts advancing at 67× normal speed at this time, then in the first 9.8 seconds it advances to show 12:00, and in the remaining 10m44.8s it advances another 12 hours, so that at 12pm (actual time) the clock shows 12:00.

      In the following hours the slowing clock advances an appropriate number of hours to show the correct time on each hour, until it stops at 5:35pm. In the time since winding it has advanced 199.22 hours, approximately 8.3 days, which is in the range we are expecting.

      If the clock started slowing before 12pm than it would be running at faster than 67× normal rate after winding, and the time of the winding would be closer to 12pm. But the total amount the clock has advanced is at least 197 hours (= 8.2 days), so we still get a viable answer.

      However, if it is possible that the clock was running at a constant speed until some time after 12pm, then we can get different answers to the published solution.

      For example, if the number of hours advanced at (12pm, 1pm, 2pm, 3pm, 4pm, 5pm) is:

      (+12, +49, +86, +123, +160, +197)

      The the correct time is displayed at the required times, and each value is 37 hours advanced from the previous value, so the clock is advancing at a constant rate of 37× normal speed. The time the clock was wound up was 11:40:00am.

      At (or after) 5pm the clock can be begin to slow and finally run down at whatever time we choose (between 5pm and 6pm).

      For example, if, at 5pm, the clock slows according to the following equation:

      y(x) = −74x² + 777x − 1838

      Then we have y(5) = 197, y'(5) = 37, y'(5.25) = 0, so y achieves a maximum at y(5.25) = 201.625.

      Which means the clock stops at 5:15pm, having advanced 201.96 hours (= 8.4 days). Which provides a viable alternative solution.

      So we do need to make some additional assumptions in order to arrive at a unique solution. The one I’ve highlighted in bold above is probably the key one.

      Like

      • John Crabtree's avatar

        John Crabtree 1:53 am on 23 December 2019 Permalink | Reply

        From 4.00pm to 5.00pm the clock traveled 13 hours
        From 3.00pm to 4.00pm the clock traveled 25 hours
        From 2.00pm to 3.00pm the clock traveled 37 hours
        From 1.00pm to 2.00pm the clock traveled 49 hours
        From 12.00pm to 1.00pm the clock traveled 61 hours
        That is a little over 7.5 days, and so the clock started some time before 12.00pm, and the rate of decrease is correct.

        Let the relative speed at 4.30pm, ie the average of the speeds at 4.00 and 5.00 pm, be 13.
        Then the relative speed at 3.30pm, ie the average of the speeds at 3.00 and 4.00 pm, is 25.
        The clock stopped an additional 13 / (25 – 12) = 13 / 12 hours after 4.30pm.
        And so the clock stopped at 5.35pm.

        Like

  • Unknown's avatar

    Jim Randell 5:21 pm on 20 December 2019 Permalink | Reply
    Tags:   

    Teaser 2987: Table mats 

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

    Beth and Sam were using computers to design two table mats shaped as regular polygons.

    The interior angles of Beth’s polygon were measured in degrees; Sam’s were measured in grads. [A complete turn is equivalent to 360 degrees or 400 grads.]

    On completion they discovered that all of the interior angles in the 2 polygons had the same numerical whole number value.

    If I told you the last digit of that number, you should be able to work out the number of edges in (a) Beth’s table mat and (b) Sam’s table mat.

    What were those numbers?

    [teaser2987]

     
    • Jim Randell's avatar

      Jim Randell 8:53 pm on 20 December 2019 Permalink | Reply

      This Python program determines the regular polygons with integer internal angles for 360 divisions (degrees) and 400 divisions (grads). It then finds the common values, and which of those are unique mod 10. It runs in 77ms.

      Run: [ @repl.it ]

      from enigma import (divisors_pairs, intersect, filter_unique, printf)

# record n-gons by internal angles
# t is the number of subdivisions in a circle
# return map of: <internal angle> -> <number of sides>
def ngons(t):
  r = dict()
  for (d, n) in divisors_pairs(t, every=1):
    if n > 2:
      r[t // 2 - d] = n
  return r

# find n-gons for 360 subdivisions and 400 subdivisions
A = ngons(360)
B = ngons(400)

# find interior angles that match
ss = intersect([A.keys(), B.keys()])

# filter them by the units digit
ss = filter_unique(ss, (lambda x: x % 10))

# output solution
for i in ss.unique:
  printf("angle = {i} -> (a) {a}-gon, (b) {b}-gon", a=A[i], b=B[i])

      Solution: (a) Beth’s polygon has 72 sides; (b) Sam’s polygon has 16 sides.

      A 72-gon has internal angles measuring 175°. A 16-gon has internal angles measuring 157.5° = 175 grads.

      There are 4 numbers which will give regular n-gons for angles expressed in degrees and grads. These are:

      120: degrees → 6-gon (hexagon); grads → 5-gon (pentagon)
      150: degrees → 12-gon (dodecagon); grads → 8-gon (octagon)
      160: degrees → 18-gon (octadecagon); grads → 10-gon (decagon)
      175: degrees → 72-gon (heptacontakaidigon?); grads → 16-gon (hexadecagon)

      Obviously only the last of these is uniquely identified by the final (units) digit.

      Like

    • GeoffR's avatar

      GeoffR 8:53 am on 24 December 2019 Permalink | Reply

      This programme gives four answers to the constraints in the puzzle.
      The first three answers have a common units digit of zero, and the fourth answer has a unique digit of five, which provides the answer to the puzzle. Merry Xmas!

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

var 1..400: S;  % Sam's angle (grads)
var 1..360: B;  % Beth's angle (degrees)

var 1..150: n1; % edges to Sam's table mat
var 1..120: n2; % edges to Beth's table mat
constraint n1 != n2;

% Internal angles equal gives 180 - 360/n1 = 200 - 400/n2 
constraint B == 180 - 360 div n1 /\ 360 mod n1 == 0;
constraint S == 200 - 400 div n2 /\ 400 mod n2 == 0;
constraint 180 * n1 * n2 - 360 * n2 == 200 * n1 * n2 - 400 * n1;
 
solve satisfy;

output [" Edges for Sam's table mat = " ++ show(n1) ++ 
", Edges for Beth's table mat = " ++ show(n2)
++ "\n Sam's angle = " ++ show(S) ++ ", Beth's angle = " ++ show(B)];

%  Edges for Sam's table mat = 6, Edges for Beth's table mat = 5
%  Sam's angle = 120, Beth's angle = 120
% ----------
%  Edges for Sam's table mat = 12, Edges for Beth's table mat = 8
%  Sam's angle = 150, Beth's angle = 150
% ----------
%  Edges for Sam's table mat = 18, Edges for Beth's table mat = 10
%  Sam's angle = 160, Beth's angle = 160
% ----------
%  Edges for Sam's table mat = 72, Edges for Beth's table mat = 16
%  Sam's angle = 175, Beth's angle = 175  << unique last digit
% ----------
% ==========

      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