Updates from June, 2022 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 3:55 pm on 24 June 2022 Permalink | Reply
    Tags:   

    Teaser 3118: Product dates 

    From The Sunday Times, 26th June 2022 [link] [link]

    If a date during the current millennium is day D in month M during year (2000+N), it is said to be a product date if the product of D and M equals N (for example 11 February 2022).

    My daughter and I have been investigating the numbers of days from one product date to the next product date. I was able to establish the longest such interval L, while my daughter worked out the shortest such interval S. We were surprised to find that L is a whole number multiple of S.

    What is that multiple?

    [teaser3118]

     
    • Jim Randell's avatar

      Jim Randell 4:07 pm on 24 June 2022 Permalink | Reply

      This Python program runs in 61ms. (Internal run time is 862µs).

      Run: [ @replit ]

      from datetime import date
from enigma import (Accumulator, irange, product, tuples, catch, div, printf)

# generate "product dates" in the 21st century
def generate():
  # consider each possible D, M pairing
  for (D, M) in product(irange(1, 31), irange(1, 12)):
    N = D * M
    d = catch(date, 2000 + N, M, D)
    if d is not None:
      yield d

# find the maximum and minimum separations between consecutive dates
rs = Accumulator.multi(fns=[max, min], collect=1)
for (a, b) in tuples(sorted(generate()), 2):
  d = (b - a).days
  rs.accumulate_data(d, (a, b))

# output solution
(L, S) = (x.value for x in rs)
d = div(L, S)
printf("L/S = {d} [L={L} S={S}]")

      Solution: The multiple is 274.

      The longest interval is 4384 days (2236-12-28 → 2348-12-29 → 2360-12-30 → 2372-12-31).

      The shortest interval is 16 days (2030-01-30 → 2030-02-15).

      Like

  • Unknown's avatar

    Jim Randell 8:56 am on 23 June 2022 Permalink | Reply
    Tags: ,   

    Teaser 2753: No question about it! 

    From The Sunday Times, 28th June 2015 [link] [link]

    “Sign Works” make rectangular signs of all sizes. Pat ordered a sign for the pub with the following instructions:

    “The length must be twice the width. Furthermore, the dimensions should be such that if you take its length (in centimetres), square the sum of its digits and take away the length itself, then you get the width. On the other hand, if you take its width (in centimetres), square the sum of its digits and take away the width itself, then you get the length”.

    This was enough information for the sign-maker to calculate the dimensions of the sign.

    What were they?

    [teaser2753]

     
    • Jim Randell's avatar

      Jim Randell 8:57 am on 23 June 2022 Permalink | Reply

      This is very straightforward.

      from enigma import (irange, inf, dsum, sq, printf)

for width in irange(1, inf):
  length  = 2 * width
  if width + length == sq(dsum(width)) == sq(dsum(length)):
    printf("width={width} length={length}")
    break

      Solution: The sign was 27 cm × 54 cm.

      Like

    • GeoffR's avatar

      GeoffR 9:30 am on 23 June 2022 Permalink | Reply 

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

var 1..9:a; var 1..9:b; % length digits
var 1..9:c; var 1..9:d; % width digits

% Length and width of sign ( assumed 2 digits)
var 10..99:L == 10*a + b; 
var 10..99:W == 10*c + d;

constraint L == 2 * W;

constraint W == (a + b) * (a + b) - L;

constraint L == (c + d) * (c + d) - W;

solve satisfy;

output [ "Length(cm) = " ++ show(L) ++ ", Width(cm) = " ++ show(W) ];

% Length(cm) = 54, Width(cm) = 27
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 11:16 am on 21 June 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 719: Wotta-Woppa! 

    From The Sunday Times, 27th April 1975 [link]

    On the Island of Imperfection there are three tribes; the Pukkas who always tell the truth, the Wotta-Woppas who never tell the truth, and the Shilli-Shallas who make statements which are alternately true and false, or false and true. This story is about three inhabitants; Ugly, Stupid and Toothless, whose names give some indication of the nature of their imperfections.

    The island currency is a Hope. The weekly wage of a Pukka is between 10 and 19 Hopes, of a Shilli-Shalla between 20 and 29, and of a Wotta-Woppa between 30 and 39 (in each case a whole number of Hopes). They make three statements each, anonymously:

    A says: (1) B is a Wotta-Woppa. (2) My wages are 25% less than 20% more than one of the others. (3) I get 10 hopes more than B.

    B says: (1) The wages of one of us is different from the sum of those of the other two. (2) We all belong to the same tribe. (3) More of C‘s statements are true than mine.

    C says: (1) Ugly earns more than Toothless. (2) The wages of one of us are 15% less than the wages of another. (3) Stupid is a Shilli-Shalla.

    Find C‘s name, tribe and wages.

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

    [teaser718]

     
    • Jim Randell's avatar

      Jim Randell 11:17 am on 21 June 2022 Permalink | Reply

      This is similar to Puzzle 15 (and Puzzle 66).

      Some obvious initial analysis:

      Statement B1 (“The wages of one of us is different from the sum of those of the other two”) must always be true, as it it not possible for each of the three to have wages that are equal to the sum of the other two. (Who would have the largest value?)

      So B cannot be a Wotta-Woppa. (And so A1 is false).

      Which means B3 must be also be true. So C must make more true statements than B, so B cannot be a Pukka. Hence B is a Shilli-Shalla, and C is a Pukka. (And B2 is false).

      And so C3 must be true, and “Stupid” is a Shilli-Shalla.

      And as A1 is false, then A cannot be a Pukka, and A3 must also be false.

      I incorporated these findings into a generic solution to get a program that runs in 71ms.

      Run: [ @replit ]

      from enigma import (subsets, tuples, irange, product, div, intersect, printf)

# Pukka - always tell the truth
def P(ss):
  return all(ss)

# Wotta-Woppa - never tells the truth
def W(ss):
  return not any(ss)

# Shilli-Shalla - alternates between true and false
def S(ss):
  return all(a != b for (a, b) in tuples(ss, 2))

# wages, by tribe
wage = { P: irange(10, 19), S: irange(20, 29), W: irange(30, 39) }

# assign tribes to the participants
for ts in ((W, S, P), (S, S, P)):
  (A, B, C) = ts

  # B's statements
  Bs = [True, False, True]
  assert B(Bs)

  # assign names to the participants
  for ns in subsets("STU", size=3, select="P"):
    (nA, nB, nC) = ns
    if nC == 'S': continue  # not possible
    (iS, iT, iU) = (ns.index(x) for x in "STU")

    # assign wages to the participants
    for ws in product(wage[A], wage[B], wage[C]):
      (wA, wB, wC) = ws

      # check A's statements
      As = [False, div(10 * wA, 9) in {wB, wC}, wA == wB + 10]
      if not A(As): continue

      # check C's statements
      Cs = [
        ws[iU] > ws[iT],
        ts[iS] is S,
        bool(intersect([{ div(85 * x, 100) for x in ws }, ws])),
      ]
      if not C(Cs): continue

      # check B's 3rd statement
      assert Cs.count(True) > Bs.count(True)

      # output solution
      f = lambda x: x.__name__
      printf("A={A} {nA} {wA}; B={B} {nB} {wB}; C={C} {nC} {wC} [{As}; {Bs}; {Cs}]", A=f(A), B=f(B), C=f(C))

      Solution: C is Toothless, he is a Pukka, his wage is 17 Hopes.

      A is Ugly, he is a Wotta-Woppa, his wage is 31 – 39 Hopes.

      B is Stupid, he is a Shilli-Shalla, his wage is 20 Hopes.

      C‘s wage (17) is 15% less than that of B (20).

      Like

      • Frits's avatar

        Frits 3:04 pm on 21 June 2022 Permalink | Reply

        @Jim, You swapped the ranges of Wotta-Woppa and Shilli-Shalla.

        Like

      • Jim Randell's avatar

        Jim Randell 12:25 pm on 27 June 2022 Permalink | Reply

        Inspired by Frits’ solution (below) I wrote a solution that uses the [[ SubstitutedExpression ]] solver from the enigma.py library, and is just a restatement of the puzzle text with no analysis.

        The values assigned for the tribes make it easy to express the wages alphametically.

        This Python program runs in 73ms.

        Run: [ @replit ]

        from enigma import (SubstitutedExpression, irange, tuples, div, printf)

#    statements  tribe  name  wage
# A: a d g       p      x     ps
# B: b e h       q      y     qt
# C: c f i       r      z     ru
#
# statements: 0 (false), 1 (true)
# tribe: 1 (P), 2 (SS), 3 (WW)
# name: 1 (S), 2 (T), 3 (U)
# wage (units): 0 - 9

# check statements for a tribe
def tribe(t, ss):
  if t == 1: return all(ss)
  if t == 2: return all(a != b for (a, b) in tuples(ss, 2))
  if t == 3: return not any(ss)

# B1: one of the wages is different from the sum of the other two
def B1(*ws):
  t = sum(ws)
  return any(w != t - w for w in ws)

# C1: Ugly (3) earns more than Toothless (2)
def C1(ns, ws):
  d = dict(zip(ns, ws))
  return d[3] > d[2]

# C2: the wages of one of us is 85% the wages of another
def C2(*ws):
  for w in ws:
    x = div(85 * w, 100)
    if x in ws: return True
  return False

# expressions to evaluate
exprs = [
  # tribes and statements
  "tribe({p}, [{a}, {d}, {g}])",
  "tribe({q}, [{b}, {e}, {h}])",
  "tribe({r}, [{c}, {f}, {i}])",

  # A1: "B is a Wotta-Woppa (3)" = {a}
  "int({q} == 3) = {a}",
  # A2: "My wages are [0.9] one of the others" = {d}
  "int(div({ps} * 10, 9) in { {qt}, {ru} }) = {d}",
  # A3: "I get 10 Hopes more than B" = {g}
  "int({ps} == {qt} + 10) = {g}",
  # B1: "The wages of one of us is different from the sum of the wages
  # of the other two" = {b}
  "int(B1({ps}, {qt}, {ru})) = {b}",
  # B2: "We all belong the same tribe" = {e}
  "int({p} == {q} == {r}) = {e}",
  # B3: "More of C's statements are true than mine" = {h}
  "int({c} + {f} + {i} > {b} + {e} + {h}) = {h}",
  # C1: "Ugly earns more than Toothless" = {c}
  "int(C1([{x}, {y}, {z}], [{ps}, {qt}, {ru}])) = {c}",
  # C2: "The wages of one of us are 0.85 the wages of another" = {f}
  "int(C2({ps}, {qt}, {ru})) == {f}",
  # C3: "Stupid (1) is a Shilli-Shalla (2)" = {i}
  "int({ {x}: {p}, {y}: {q}, {z}: {r} }[1] == 2) = {i}",
]

# invalid digit / symbol assignments
d2i = dict()
for d in irange(0, 9):
  vs = set()
  if d > 1: vs.update('abcdefghi')
  if d < 1 or d > 3: vs.update('pqrxyz')
  d2i[d] = vs

# create the puzzle
p = SubstitutedExpression(
  exprs,
  distinct="xyz",
  d2i=d2i,
  env=dict(tribe=tribe, B1=B1, C1=C1, C2=C2),
  verbose=0,
)

# solve the puzzle and output solutions
Ts = { 1: "Pukka", 2: "Shilli-Shalla", 3: "Wotta-Woppa" }
Ns = { 1: "Stupid", 2: "Toothless", 3: "Ugly" }
for s in p.solve():
  (a, b, c, d, e, f, g, h, i, p, q, r, s, t, u, x, y, z) = (s[k] for k in 'abcdefghipqrstuxyz')
  printf("A: {N:9s}  {T:13s}  {p}{s}  [{a} {d} {g}]", N=Ns[x], T=Ts[p])
  printf("B: {N:9s}  {T:13s}  {q}{t}  [{b} {e} {h}]", N=Ns[y], T=Ts[q])
  printf("C: {N:9s}  {T:13s}  {r}{u}  [{c} {f} {i}]", N=Ns[z], T=Ts[r])
  printf()

        Like

        • Frits's avatar

          Frits 1:31 pm on 29 June 2022 Permalink | Reply

          Nice idea to let tribes go from 1 to 3 so you can use the tribe value as a tens unit of the wage.

          Like

    • Frits's avatar

      Frits 3:30 pm on 21 June 2022 Permalink | Reply

      For all tribes the veracity of the first and third statement must be the same.

         
from enigma import SubstitutedExpression

# tribes 0 = Wotta-Woppa, 1 = Shilli-Shilla, 2 = Pukka 
# names: 0 = Stupid, 1 = Toothless, 2 = Ugly

#     stmnts  tribe  wages   name
#      0/1    0/1/2         0/1/2
# A:  D E D     P     UV      K
# B:  F G F     Q     WX      L
# C:  H I H     R     YZ      M
# the alphametic puzzle
p = SubstitutedExpression(
  [
    # if Wotta-Woppa all statements are false
    "P != 0 or D == E == 0",
    "Q != 0 or F == G == 0",
    "R != 0 or H == I == 0",
    
    # if Shilli-Shalla all statements are alternating true/false
    "P != 1 or D + E == 1",
    "Q != 1 or F + G == 1",
    "R != 1 or H + I == 1",
    
    # if Pukka all statements are true
    "P != 2 or D == E == 1",
    "Q != 2 or F == G == 1",
    "R != 2 or H == I == 1",
    
    # ranges: Pukka 10-19, Shilli-Shalla 20-29 and Wotta-Woppa 30-39
    "(P != 0 or U == 3) and (P != 1 or U == 2) and (P != 2 or U == 1)",
    "(Q != 0 or W == 3) and (Q != 1 or W == 2) and (Q != 2 or W == 1)",
    "(R != 0 or Y == 3) and (R != 1 or Y == 2) and (R != 2 or Y == 1)",
    
    # A1: B is a Wotta-Woppa
    "(F == G == 0) == D",
    # A2: My wages are 25% less than 20% more than one of the others
    "(UV in {0.9 * WX, 0.9 * YZ}) == E",
    # A3: I get 10 hopes more than B
    "(UV == WX + 10) == D",
    
    # B1: The wages of one of us is different from the sum of those 
    # of the other two
    "(UV != WX + YZ or UV + WX != YZ or UV + YZ != WX) == F",
    # B2: We all belong to the same tribe
    "(P == Q == R) == G",
    # B3: More of C's statements are true than mine
    "(2* H + I >  2 * F + G) == F",
    
    
    # C1: Ugly earns more than Toothless
    "((UV if K == 2 else WX if L == 2 else YZ) > \
      (UV if K == 1 else WX if L == 1 else YZ)) == H",
    # C2: The wages of one of us are 15% less than the wages of another
    "((20 * UV in {17 * YZ, 17 * WX}) or \
      (20 * WX in {17 * YZ, 17 * UV}) or \
      (20 * YZ in {17 * UV, 17 * WX})) == I",
    # C3: Stupid is a Shilli-Shalla.
    "((K == 0 and P == 1) or \
      (L == 0 and Q == 1) or \
      (M == 0 and R == 1)) == H",
  ],
  answer="(D, E, F, G, H, I), (P, Q, R), (UV, WX, YZ), (K, L, M)",
  d2i=dict([(0, "UWY")] +
           [(2, "DEFGHI")] +
           [(3, "DEFGHIKLMPQR")] +
           [(k, "DEFGHIKLMPQRUWY") for k in range(4, 10)]),
  distinct="KLM",
  verbose=0,
)

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

      Like

  • Unknown's avatar

    Jim Randell 3:11 pm on 19 June 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 77: Ali’s counter move 

    From The Sunday Times, 16th September 1962 [link]

    Ali and Baba are playing the Chay game, Ali has a bag containing 12 numbered tickets, 3 each of numbers 1, 2, 3, 4 (all numbers represented by strokes). Baba has 6 double-sided counters containing the same 12 numbers, and a board of 6 squares.

    Ali draws 6 tickets from his bag one at a time, calling out the number as he does so. At each call Baba selects a counter with that number on one of its sides and places it face up in a square. If in 6 calls he fills 6 squares he wins. Once a counter is laid it stays. The counter-couplings are so arranged that 5 squares could always be filled if the numbers were known beforehand.

    But, unnoticed by Baba, Ali has slyly added 1 stroke each to 2 of his opponent’s counters. As a result, Baba frequently places no more than 3 or 4 counters, and at last comes a deal when, after Ali has called “Two”, “One”, he calls a third number and Baba cannot fill it.

    It is the last straw.

    Baba, having lost many pice and much temper, angrily examines the four remaining counters. Three of them are identical couplings!

    “Ah! wicked one”, he cries, “you have forged my counters!”. And, throwing them down, he clears for action.

    What couplings are on these 4 counters?

    This puzzle is included in the book Sunday Times Brain  Teasers (1974).

    [teaser77]

     
    • Jim Randell's avatar

      Jim Randell 3:14 pm on 19 June 2022 Permalink | Reply

      This Python program considers possible sets of counters that meet the specified conditions, and looks at ways to fake two of the counters so that there are 3 counters the same. We then match two of the fake set to the calls “1” and “2” and look to see if there is a third call that cannot be matched from the remaining counters. (It is a good opportunity to do some work with multisets).

      This Python program runs in 295ms.

      Run: [ @replit ]

      from enigma import (multiset, irange, subsets, product, union, printf)

# update multiset <m>, by removing values in <rem>, and adding values in <add>
def update(m, rem=None, add=None):
  if rem:
    m = m.difference(multiset.from_seq(rem))
  else:
    m = m.copy()
  if add:
    m.update_from_seq(add)
  return m

# partition the multiset into <k>-tuples
# return a multiset of <k>-tuples
def mpartitions(m, k, ss=[]):
  # are we done?
  if not m:
    yield multiset.from_seq(ss)
  else:
    # choose the next <k>-tuple
    for s in subsets(m, size=k, select="mC"):
      t = tuple(sorted(s))
      if (not ss) or not (t < ss[-1]):
        yield from mpartitions(update(m, rem=s), k, ss + [t])

# the tickets
tickets = multiset.from_seq([1, 2, 3, 4], count=3)

# possible sequences of tickets
tss = list(tickets.subsets(size=6))

# possible counter displays
def display(cs, ss=multiset()):
  if not cs:
    yield ss
  else:
    # choose the next key
    (a, b) = k = cs.peek()
    n = cs[k]
    # and choose the split (how many showing a, the rest show b)
    for x in irange(0, n):
      # remaining counters
      cs_ = cs.copy().remove(k, n)
      ss_ = ss.copy().update_from_pairs([(a, x), (b, n - x)])
      yield from display(cs_, ss_)

# check this set of counters
def check(cs, ts):
  # consider each possible display
  for x in display(cs):
    # remove ticket sequences with at least 5 matches
    ts = list(t for t in ts if len(x.intersection(t)) < 5)
    if not ts: return True
  return False

# fake a counter by incrementing one side
def fake1(x, y):
  yield (x, y + 1)
  if x < y: yield (x + 1, y)

# fake a set of counters
def fake(cs):
  # choose 2 counters
  for (a, b) in subsets(cs, size=2, select="mC"):
    # fake them
    for (fa, fb) in product(fake1(*a), fake1(*b)):
      # replace the originals with the fakes
      yield update(cs, rem=(a, b), add=(fa, fb))

# consider possible counters
for cs in mpartitions(tickets, 2):
  # check these counters can match at least 5 of all tickets sequences
  if not check(cs, tss): continue
  printf("counters = {cs}", cs=sorted(cs))

  # make the fake set of counters
  for fcs in fake(cs):
    # there should be 3 counters the same
    if all(v < 3 for v in fcs.values()): continue
    printf("-> faked = {fcs}", fcs=sorted(fcs))

    # choose 2 counters to match the calls "1" and "2"
    for (x, y) in subsets(fcs, size=2, select="mP"):
      if not (1 in x and 2 in y): continue
      # remaining counters
      rs = update(fcs, rem=(x, y))
      # is there a call that cannot be matched?
      if len(union(rs.keys())) == 4: continue

      # output solution (rs)
      printf("-> remaining = {rs}; [1 -> {x}, 2 -> {y}]", rs=sorted(rs))
      printf()

      Solution: The four remaining counters are: 2|4, 2|4, 2|4, 3|4.

      There is only one set of counters that meets the specified conditions:

      1|2, 1|3, 1|4, 2|3, 2|4, 3|4

      These are then faked by incrementing the 3rd and 4th counters to give:

      1|2, 1|3, 2|4, 2|4, 2|4, 3|4

      Which has 3 copies of the 2|4 counter.

      For the call of “1” the 1|3 counter is chosen. For the call of “2” the 1|2 counter is chosen.

      This leaves: 2|4, 2|4, 2|4, 3|4, which cannot match a call of “1”.

      Like

    • Frits's avatar

      Frits 12:10 pm on 21 June 2022 Permalink | Reply

      A lot easier to solve without using Python.

         
# Suppose numbers in Ali's bag are a, b, c and d

# ------ Check Baba's original set of counters -----------------
# Can one counter have the same numbers on it?

# Then fi we have counters a/a and a/x where x is b, c or d.
# If Ali calls 3 a's and 3 x's then both his third a call and third x call 
# can't be filled.   ===> each counter has 2 different numbers on it

# Can 2 counters be the same?
# Then fi we have counters a/b and a/b.
# If Ali calls 3 a's followed by 3 b's then the last two b calls can't be
# filled.   ===> no counter combination occurs more than once.

# So Baba has to have 1/2, 1/3 and 1/4. He also needs to have 2/3 and 2/4
# and finally 3/4.

# so we have 1|2, 1|3, 1|4, 2|3, 2|4 and 3|4
# --------------------------------------------------------------


# In two counters a number is incremented by one, resulting in at least 
# 3 counters with the same numbers x and y. This means the x|y counter must 
# have been present in Baba's original set of counters.
# x|y cannot be a counter like 1|z as there is only one option 1|(z-1) to 
# produce an additional 1|z counter.   ===> 1|2, 1|3 and 1|4 are not x|y

# x|y cannot be a counter like z|(z + 1) as there is only one option 
# (z-1)|(z+1) to produce an additional z|(z + 1) counter.
# ==> 2|3 and 3|4 are not x|y

# so x|y is 2|4 and Baba's faked set being 1|2, 1|3, 2|4, 2|4, 2|4 and 3|4.
# As Ali has called “Two” and “One” resp. 1|2 and 1|3 must have been placed
# in a square.   ===> the four remaining counters are 2|4, 2|4, 2|4 and 3|4

      Like

  • Unknown's avatar

    Jim Randell 5:00 pm on 17 June 2022 Permalink | Reply
    Tags:   

    Teaser 3117: Stop me if you’ve heard this one 

    From The Sunday Times, 19th June 2022 [link] [link]

    A square, a triangle and a circle went into a bar.

    The barman said: “Are you numbers over 18?”

    They replied: “Yes, but we’re under a million”

    The square boasted: “I’m interesting, because I’m the square of a certain integer”

    The triangle said: “I’m more interesting — I’m a triangular number, the sum of all the integers up to that same integer”

    The circle said: “I’m most interesting — I’m the sum of you other two”

    “Well, are you actually a circular number?”

    “Certainly, in base 1501, because there my square ends in my number exactly. Now, shall we get the drinks in?”

    The square considered a while, and said: “All right, then. You(‘)r(e) round!”

    In base 10, what is the circular number?

    [teaser3117]

     
    • Jim Randell's avatar

      Jim Randell 5:27 pm on 17 June 2022 Permalink | Reply

      Circular numbers are also called automorphic numbers [@wikipedia], and we have encountered them before. See: Enigma 49, Enigma 1736.

      There is a unique value for the “certain integer” (and so S, T, C).

      This Python program runs in 59ms. (Internal runtime is 4.5ms).

      from enigma import (irange, inf, sq, tri, nsplit, zip_eq, join, printf)

# consider possible "certain" integers
for n in irange(6, inf):
  S = sq(n)
  T = tri(n)
  C = S + T
  if not (C < 1000000): break
  # consider the digits of C and C^2 in base 1501
  Cds = nsplit(C, base=1501)
  C2ds = nsplit(sq(C), base=1501)
  # does C^2 end with C?
  if zip_eq(Cds, C2ds, reverse=1):
    # output solution
    fmt = lambda ds: join(ds, sep=":", enc="{}")
    printf("n={n}: S={S} T={T} C={C} [C={Cds} C^2={C2ds}]", Cds=fmt(Cds), C2ds=fmt(C2ds))

      Solution: The circular number is 1027.

      Numbers up to 999,999 can be represented in base 1501 using 1- or 2- digits.

      And there are six 1- or 2- digit automorphic numbers in base 1501, which give potential values for C:

      0
      1
      475
      1027
      368220
      1884782

      The first two are too small. The last one is too big.

      Of the remaining three only 1027 gives a viable value for n, which is n = 26.

      i.e.

      S = sq(26) = 676
      T = tri(26) = 351
      C = 676 + 351 = 1027

      And in base 1501 we have:

      1027 = {1027}
      1027² = {702:1027}

      So (in base 1501) the final digit of C² is C.

      In fact, even if S and T are square and triangular numbers of (possibly) different integers, we can still work out a unique value for C.

      Like

      • Jim Randell's avatar

        Jim Randell 8:26 pm on 17 June 2022 Permalink | Reply

        Here is a faster version that doesn’t construct the base 1501 representations.

        It has an internal run time of 852µs.

        from enigma import (irange, inf, sq, tri, printf)

# consider possible "certain" integers
M = B = 1501
for n in irange(6, inf):
  S = sq(n)
  T = tri(n)
  C = S + T
  if not (C < 1000000): break
  # consider the digits of C and C^2 in base 1501
  while not (C < M): M *= B
  if pow(C, 2, M) == C:
    # output solution
    printf("n={n}: S={S} T={T} C={C}")

        Liked by 1 person

        • Jim Randell's avatar

          Jim Randell 4:11 pm on 30 June 2022 Permalink | Reply

          I read up on how to find modular roots of integer-valued polynomials using Hensel lifting and the Chinese Remainder Theorem, and then wrote some code to implement it.

          Given the “certain integer” n, the following Python code constructs a polynomial function for f(n) = sq(C(n)) − C(n), and then finds the roots of this function modulo 1501^k (for k = 1, 2). We then check these roots give viable values of S, T, C.

          The internal runtime is 564µs, so it is faster than my simple approach above, but quite a lot more complicated.

          from enigma import (irange, prime_factor, gcd, lcm, egcd, cproduct, sq, tri, ndigits, arg, printf)

# simplified CRT
# solve: x = a (mod m); x = b (mod n)
def crt1(a, b, m, n):
  g = gcd(m, n)
  if (a - b) % g != 0: return None
  (x, y, z) = (m // g, n // g, (m * n) // g)
  (u, v, _) = egcd(x, y)
  return (b * u * x + a * v * y) % z

# general Chinese Remainder Theorem
# solve: x = rs[i] (mod ms[i])
def crt(rs, ms):
  assert len(rs) == len(ms) # or use zip(..., strict=1)
  x = mm = None
  for (r, m) in zip(rs, ms):
    if x is None:
      (x, mm) = (r, m)
    else:
      x = crt1(r, x, m, mm)
      if x is None: return None
      mm = lcm(m, mm)
  return x

# find modular roots of a polynomial
class PolyRootsMod(object):

  def __init__(self, f, cache=1):
    self.f = f
    self.cache = (dict() if cache else None)

  # find roots of <f> mod (<b>^<k>) using Hensel's lemma
  def hensel(self, b, k):
    if k == 0: return [0]
    assert k > 0
    bk = b**k
    # check the cache
    cache = self.cache
    if cache:
      rs = cache.get(bk)
      if rs is not None:
        return rs
    # find the roots
    f = self.f
    k_ = k - 1
    bk_ = b**k_
    rs = list()
    for r in self.hensel(b, k_):
      for i in irange(b):
        x = i * bk_ + r
        if f(x) % bk == 0:
          rs.append(x)
    # cache if necessary
    if cache is not None: cache[bk] = rs
    return rs

  # find roots of polynomial <p> mod <n>^<k>
  def roots_mod(self, n, k=1):

    # find roots for each prime factor of <n>^<k>
    (rs, bs) = (list(), list())
    for (f, e) in prime_factor(n):
      rs.append(self.hensel(f, e * k))
      bs.append(pow(f, e * k))

    # combine roots using CRT
    for xs in cproduct(rs):
      yield crt(xs, bs)


B = arg(1501, 0, int)
printf("[B={B}]")

# start with polynomial functions: sq, tri, circ
circ = lambda n: sq(n) + tri(n)

# find k-digit automorphic values for C in base B
f = lambda x: x * (x - 1)
poly = PolyRootsMod(lambda n: f(circ(n)))
for k in irange(1, ndigits(999999, base=B)):
  for n in poly.roots_mod(B, k):
    S = sq(n)
    T = tri(n)
    C = circ(n)
    if S < 18 or T < 18 or not (C < 1000000): continue
    if ndigits(C, base=B) != k: continue
    printf("S={S} T={T} C={C} [n={n}]")

          Like

      • Jim Randell's avatar

        Jim Randell 9:50 am on 18 June 2022 Permalink | Reply

        Here is a version adapted from my code for Enigma 49. It proceeds by constructing possible automorphic values for C and then calculating the corresponding “certain integer” n, and from that S and T. Although this is not as fast as my previous program.

        from enigma import (irange, ndigits, uniq, quadratic, sq, tri, printf)

# generate <k> digit automorphic numbers (in base <b>)
# i.e. x where the rightmost k digits of x^n are the digits of x
# yield (<k>, <x>) where <k> in <ks>
def automorphic(ks, b=10, n=2):
  K = max(ks)
  (k, xs, p, q) = (1, [0], 1, b)
  while not (k > K):
    f = (k in ks)
    xs_ = list()
    for d in irange(b):
      for x in xs:
        x_ = d * p + x
        if pow(x_, n, q) == x_:
          if f: yield (k, x_)
          xs_.append(x_)
    (k, xs, p, q) = (k + 1, xs_, q, q * b)

# consider 1-, 2- digit automorphic numbers in base 1501
d = ndigits(999999, base=1501)
for C in uniq(x for (k, x) in automorphic(irange(1, d), 1501)):
  if C < 18 or not (C < 1000000): continue
  # calculate n: C = n(3n + 1)/2
  for n in quadratic(3, 1, -2 * C, domain="Z"):
    if n < 6: continue
    S = sq(n)
    T = tri(n)
    printf("C={C} S={S} T={T} [n={n}]")

        And here is a version which proceeds by constructing possible values for C using the technique given on the Wikipedia page for automorphic numbers [@wikipedia].

        from enigma import (irange, quadratic, sq, tri, printf)

# Hensel's lemma - see [ https://en.wikipedia.org/wiki/Automorphic_number ]
def hensel(poly, base, power):
  if power == 0: return [0]
  roots = hensel(poly, base, power - 1)
  rs = list()
  for r in roots:
    for i in irange(base):
      j = i * base ** (power - 1) + r
      x = poly(j) % (base ** power)
      if x == 0:
        rs.append(j)
  return rs

# generate <k> digit automorphic numbers in base <b>
# i.e. values of x where the rightmost k digits of x^2 are the digits of x
def automorphic(k, b=10):
  poly = lambda x: x * x - x
  return hensel(poly, b, k)

# consider 1-, 2- digit automorphic numbers in base 1501
for k in (1, 2):
  for C in automorphic(k, 1501):
    if C < 18 or not (C < 1000000): continue
    # calculate n: C = n(3n + 1)/2
    for n in quadratic(3, 1, -2 * C, domain="Z"):
      if n < 6: continue
      S = sq(n)
      T = tri(n)
      printf("C={C} S={S} T={T} [n={n}]")

        Like

    • Robert Brown's avatar

      Robert Brown 6:19 pm on 17 June 2022 Permalink | Reply

      Hi Jim
      Your version of the text differs from the Sunday Times site. This asks “In base 10, what is the circular number?” You seem to have “what is the certain integer”.

      Like

      • Jim Randell's avatar

        Jim Randell 6:27 pm on 17 June 2022 Permalink | Reply

        Thanks. Of course if you know the “certain integer”, you can easily calculate the square, triangular and circular numbers.

        Interestingly, there is only one possible value for C, even if S and T are square and triangular numbers of different integers.

        Like

    • GeoffR's avatar

      GeoffR 8:32 pm on 17 June 2022 Permalink | Reply

      if S and T are both less than 1,000,000, then C is less than 2,000,000.

      The last two digits in base 1501 give a max value of 2,253,000.

      i.e. 1500 *1501 + 1500, which is adequate to define C.

      
# Square and triangular numbers are less than 1,000,000
sqs = [x * x for x in range(5, 1000)]
tris = [ x * (x+1)// 2 for x in range(6, 1410)]

CNum = []  # list to store circular numbers

# consider possible (S, T) combinations
for S in sqs:
  for T in tris:
    C = S + T
    C2 = C * C
    # only 2 digits in base 1501 are needed
    # for the maximum value of C
    num, rem = divmod(C2, 1501)
    if rem == C:
      if C not in CNum: CNum.append(C)

for n in CNum:
    print(f"Circular number = {n}")

      Like

      • Jim Randell's avatar

        Jim Randell 9:42 pm on 17 June 2022 Permalink | Reply

        @GeoffR: This is very similar to the first program I wrote. And then I realised that S = n² and T = tri(n) for the same value of n, which makes things much faster.

        It does however lead to the same answer for C, so there is a harder problem lurking inside this puzzle.

        Also I think the text implies that all of S, T, C are less than a million (and more than 17).

        But C is 1- or 2-digits in base 1501, so C² could be up to 4 digits, and we need to check the final 2 digits if C is length 2.

        Like

    • Frits's avatar

      Frits 11:11 pm on 17 June 2022 Permalink | Reply

      Approaching it from the possible C values.

      I have assumed that when the number of digits in the remainder of (C^2 base 1501) is smaller than the number of digits in C we need to also check the last digits of the divisor of (C^2 base 1501).

         
B = 1501

# C = f(n) = n(3n + 1) // 2
# f(n+1) - f(n) = (n + 1)(3(n + 1) + 1) // 2 - n(3n + 1) // 2
#               = 2 + 3n

C = 40        # as C >= 2 * 18
for n in range(5, 817):  
  sC = str(C)
  lC = len(sC)
    
  C2 = C**2
  sC2 = str(C2)
  
  # next C
  C += (2 + 3 * n)
  
  # calculate remainder
  R1 = C2 % B
  lR1 = len(str(R1))
  
  # can we directly check all digits of C
  if lR1 >= lC:
    if str(R1)[-lC:] != sC: continue
  else: # len(R1) < lC
    # check last digits of C
    if sC[-lR1:] != str(R1): continue
    
    # check the digits of the divisor
    R2 = ((C2 - R1) // B) % B
    lR2 = len(str(R2))
    
    # check if digits in C correspond with the remainder of the divisor
    if sC[-lR1 + lR2:-lR1] != str(R2): continue
    
    # too lazy to code what happens if lR1 + lR2 < lC
    if lR1 + lR2 < lC: continue
    
  print("answer:", sC)

      Like

    • Frits's avatar

      Frits 2:39 pm on 18 June 2022 Permalink | Reply

      @Jim,

      If the base is 272 is C = 57 an answer as C2ds=(11, 257) ?

      Like

      • Jim Randell's avatar

        Jim Randell 2:55 pm on 18 June 2022 Permalink | Reply

        @Frits: 57 is not automorphic in base 272.

        57 = {57}
        57² = {11:257}

        You compare the “digits” as atomic values not strings, so the final digit of 57² is 257 and this is not the same as 57.

        But 17 and 256 are both 1-digit automorphic numbers in base 272:

        17 = {17}
        17² = {1:17}

        256 = {256}
        256² = {240:256}

        Like

    • Frits's avatar

      Frits 4:48 pm on 18 June 2022 Permalink | Reply

      There is no solution if the circular number has to be a round number as well (at least not in base 10).

      Like

    • Jim Randell's avatar

      Jim Randell 9:06 am on 21 June 2022 Permalink | Reply

      For an answer with larger values for S, T, C, but a smaller base, try solving the same puzzle with a base of 105.

      Like

    • GeoffR's avatar

      GeoffR 12:08 pm on 21 June 2022 Permalink | Reply

      Easy to adapt Jim’s first program, substituting 105 for 1501 as the number base.

      This gives:

      n=458: S=209764 T=105111 C=314875 [C={28:58:85} C^2={7:80:71:28:58:85}]
      C is 3 digits long, so:
      28 * 105**2 + 58 * 105 + 85 = 314875

      Like

  • Unknown's avatar

    Jim Randell 9:22 am on 16 June 2022 Permalink | Reply
    Tags:   

    Teaser 2499: [Supermarket milk] 

    From The Sunday Times, 15th August 2010 [link] [link]

    Joe was talking to the supermarket manager about shelf stocking, and she mentioned a recent exercise with milk. Each morning, they added sufficient new stock to ensure there were 1,200 litres on the shelves. They found that 56% of the new stock was sold on the first day, half that amount the next day and half that new amount the day after. Any remaining stock was regarded as out of date and removed next morning before restocking. Hence, they calculated the number of litres to be added each morning.

    What is that number?

    This puzzle was originally published with no title.

    [teaser2499]

     
    • Jim Randell's avatar

      Jim Randell 9:23 am on 16 June 2022 Permalink | Reply

      I assumed that the numbers are fixed. So the same quantity of fresh milk is added each day, and the same quantities sold each day.

      If x litres of fresh milk are stocked at the beginning of the day (to bring the total stocks to 1200 litres).

      We can track what happens to this batch milk on the following days.

      At the start of the next day 0.56x has been sold, so there is only 0.44x of this batch of milk remaining (and a new batch of x litres of fresh milk are added).

      At the start of the next day an additional 0.28x has been sold, so there is only 0.16x of the original batch remaining (along with 0.44x litres of the previous days new batch, and x litres of fresh milk).

      At the start of the next day an additional 0.14x has been sold, so there is only 0.02x of the original batch remaining, but this is removed as it is too old.

      So the 1200 litres of milk on the shelves consists of:

      x litres of fresh milk
      0.44x litres of 1-day old milk
      0.16x litres of 2-day old milk

      Hence:

      x + 0.44x + 0.16x = 1200
      1.6x = 1200
      x = 750

      Solution: Each morning 750 litres of fresh milk are added to the shelves.

      So the milk available at the start of the day consists of:

      750 litres of fresh milk (420 litres are sold during the day, leaving …)
      330 litres of 1-day old milk (210 litres are sold during the day, leaving …)
      120 litres of 2-day old milk (105 litres are sold during the day, leaving 15 litres to dispose of)
      1200 litres in total (735 litres sold)

      Like

    • Hugh+Casement's avatar

      Hugh+Casement 8:55 am on 17 June 2022 Permalink | Reply

      That’s some supermarket! How ever many metres of shelf space do 1200 litres take up?
      I suggest that a more realistic puzzle would have all the numbers a fifteenth as much.

      Like

  • Unknown's avatar

    Jim Randell 12:30 pm on 14 June 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 718: An eccentric race 

    From The Sunday Times, 20th April 1975 [link]

    After the tea-party Alice persuaded the Mad Hatter, the March Hare and the Dormouse to run with her round a nearby circular track, promising that they should all four win the race by reaching the winning-post at the same moment — so long as they did not vary their speeds!

    Round the track were twelve posts equally-spaced a whole number of feet apart, No. 12 being at the start, which was also the finishing-post. At each post one of the Flamingoes was stationed as umpire. We will call them F1, F2, …, F12. F12 acted as starter. The umpires reported as follows:

    (1) All four runners maintained their own constant speeds.

    (2) F2 noted that Hatter passed Dormouse at his post exactly 30 seconds after the start.

    (3) F3 reported that Hare passed Hatter at his post exactly 45 seconds after the start.

    (4) F8 said that Hare passed Alice at his post, at which time Alice was passing his post for the third time and Hare for the sixth time.

    (5) The umpires reported no more overtakings, although obviously there were others.

    The speeds of the four runners, in feet per second, were whole numbers between 5 and 20.

    How many laps had they all completed when they all won. And how many seconds did the race last?

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

    [teaser718]

     
    • Jim Randell's avatar

      Jim Randell 12:33 pm on 14 June 2022 Permalink | Reply

      I am assuming they all set off from the start at the same time (although this is not explicitly mentioned).

      This Python program runs in 55ms. (Internal run time is 326µs).

      Run: [ @replit ]

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

# distance units for passing post <n> for the <k>th time
dist = lambda n, k: n + 12 * (k - 1)

# check velocity <v> passed post <n> at time <t>
def check(v, n, t, d):
  x = div(v * t, d)
  return (x is not None) and (x % 12 == n)

# calculate the laps and time for a race with velocities <vs>
def race(vs, lap):
  # find the slowest speed
  s = min(vs)
  # consider total number of laps for the slowest
  for n in irange(1, inf):
    # calculate number of laps for the others
    laps = list(div(v * n, s) for v in vs)
    if None not in laps:
      return (laps, fdiv(n * lap, s))

# choose a speed for the Hare (M)
for M in irange(7, 20):

  # Alice (A) passed post 8 for the 3rd time, when the Hare passed it
  # for the 6th time
  A = div(M * dist(8, 3), dist(8, 6))
  if A is None: continue

  # choose speed for D
  for D in irange(5, M - 2):
    # Dormouse passes post 2 at exactly 30s
    # consider possible values for d
    for d in divisors(30 * D):
      if not check(D, 2, 30, d): continue

      # choose speed for Hatter (H)
      for H in irange(D + 1, M - 1):

        # Hatter passes post 2 at exactly 30s
        if not check(H, 2, 30, d): continue

        # Hare and Hatter pass post 3 at exactly 45s
        if not (check(H, 3, 45, d) and check(M, 3, 45, d)): continue

        # output solution
        ((lM, lA, lH, lD), t) = race([M, A, H, D], 12 * d)
        printf("M={lM} A={lA} H={lH} D={lD}; d={d} lap={lap} -> t={t:g}", lap=12 * d)

      Solution: At the end of the race the number of laps was: Alice = 8, Mad Hatter = 13, March Hare = 17, Dormouse = 7. The race lasted 180 seconds.

      The distance between posts was 15ft, so one lap was 180ft.

      The velocity of each participant, expressed in feet per second, is the same as the number of laps run during the race.

      Like

      • Frits's avatar

        Frits 10:57 pm on 15 June 2022 Permalink | Reply

        check(M, 3, 45, d) can already be done before the loop over H.

        Another idea is to choose H before D and then d must be in the intersection of the divisors of (30 * H) and (45 * H).

        Like

  • Unknown's avatar

    Jim Randell 10:01 am on 12 June 2022 Permalink | Reply
    Tags: by: R. Fisher   

    Brain-Teaser 51: In defiance of insomnia 

    From The Sunday Times, 11th March 1962 [link]

    Mr Robinson is an elderly gentleman who seeks to combat insomnia by juggling with the number of days he has lived. On April 25 last he noted that this was the product of three numbers each consisting of ten times a single figure less one. The following night he found to his surprise that the total of his days was the perfect cube of the product of the three figures of the previous day.

    How many days had he lived on April 26?

    [teaser51]

     
    • Jim Randell's avatar

      Jim Randell 10:02 am on 12 June 2022 Permalink | Reply

      This one is easy enough to tackle by brute force in Python.

      The following Python program runs in 62ms. (Internal runtime is 198µs).

      Run: [ @replit ]

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

# consider the three digits
for ds in subsets(irange(1, 9), size=3):
  # calculate the numbers of days
  n1 = multiply(10 * d - 1 for d in ds)
  n2 = pow(multiply(ds), 3)
  # are they consecutive?
  if n1 + 1 == n2:
    printf("{ds} -> {n1} {n2}")

      Solution: Mr Robinson had lived 27,000 days on 26th April.

      Which is almost 74 years. 27,000 days before 26th April 1961 is 24th May 1887. (So Mr Robinson and I have the same birthday).

      We have:

      26999 = 19 × 29 × 49
      27000 = (2 × 3 × 5)³

      We can reduce the number of candidate digit sets considered by noting:

      (10x − 1)(10y − 1)(10z − 1) + 1 = (xyz)³

      The LHS is divisible by 10, so one of the digits must be 5 and another must be even.

      Like

      • John Crabtree's avatar

        John Crabtree 3:40 pm on 14 June 2022 Permalink | Reply

        And (xyz)³ – 1 = ((xyz) – 1)((xyz)^2 + (xyz) + 1)
        With (xyz) being a multiple of 10, and the possible ages, the few possibilities are easily checked.

        Like

        • John Crabtree's avatar

          John Crabtree 5:21 am on 15 June 2022 Permalink | Reply

          In fact then two of the numbers must be 2 and 5, and then ((xyz)^2 + (xyz) + 1) = 19 * 49 = 931. And then (xyz) = 30, etc.

          Like

          • Frits's avatar

            Frits 10:29 am on 17 June 2022 Permalink | Reply

            @John, How do you proof one of the numbers is 2?

            If we assume the highest human age is 125 then more or less (xyz)^3 < 125*365.

            Using z=5 we get (xy)^3 < 365 so xy < 365^(1/3) so xy < 7.15.
            That leaves numbers 2 and 3 for x and y (if one of them must be even).

            Like

          • Frits's avatar

            Frits 10:43 am on 17 June 2022 Permalink | Reply

            Using the same logic for minimum age of 60 we get xy > 5.60.
            This leaves 2,3 and 1,6 for x,y.

            But 9 * 59 * 49 = 26019 so only options 2,3 remain for x,y.

            Like

    • Frits's avatar

      Frits 2:27 pm on 17 June 2022 Permalink | Reply 

         
# (10x - 1)(10y - 1)(10z - 1) + 1 = (x * y * z)^3 
# The LHS is divisible by 10, so one of the digits must be 5 (say z)
# and another must be even

# (10 * x - 1) * (10 * y - 1) * 49 = cd999   (z = 5)
# 4900 * x * y - 490 * (x + y) + 49 = cd999 
# ==> 490 * (x + y) must end on 50 in order for RHS to end on 99
# ==> x + y is either 5 or 15

# if RHS ends on 9.. then ((9 * x * y) - (49 * (x + y))) must end on 9
# x + y is either 5 or 15 ==> the product 9 * x * y must end on a 4

# ==> - 490 * (x + y) + 49 must end on 401
# ==> 490 * (x + y) must end on 450

# x + y is 5 or 15 ==> x + y is 10 * a + 5 where a = 0 or 1
# 490 * (x + y) = 4900 * a + 2450
# a = 1 can be discarded as then 4900 * a + 2450 ends on 350
# ==> x + y = 5. so either x, y (or y, x) is (1, 4) or (2, 3)
# x, y (or y, x) equal to (1, 4) can be discarded as then 9 * x * y ends on 6
# ==> x * y = 6 ==> x * y * 5 is 30
# Mr Robinson had lived 30^3 = 27000 days on 26th April

      Like

  • Unknown's avatar

    Jim Randell 4:25 pm on 10 June 2022 Permalink | Reply
    Tags:   

    Teaser 3116: Poll positions 

    From The Sunday Times, 12th June 2022 [link] [link]

    In an election for golf-club president, voters ranked all four candidates, with no voters agreeing on the rankings. Three election methods were considered.

    Under first-past-the-post, since the first-preferences order was A, B, C, D, the president would have been A.

    Under Alternative Vote, since A had no majority of first preferences, D was eliminated, with his 2nd and 3rd preferences becoming 1st or 2nd preferences for others. There was still no majority of 1st preferences, and B was eliminated, with his 2nd preferences becoming 1st preferences for others. C now had a majority of 1st preferences, and would have been president.

    Under a Borda points system, candidates were given 4, 3, 2, or 1 points for each 1st, 2nd, 3rd or 4th preference respectively. D and C were equal on points, followed by B then A.

    How many Borda points did each candidate receive?

    [teaser3116]

     
    • Jim Randell's avatar

      Jim Randell 5:17 pm on 10 June 2022 Permalink | Reply

      There are only factorial(4) = 24 different ways to order the candidates, so that gives us an upper bound on the number of voters.

      This Python program finds the required points values, and the unique set of votes that leads to it.

      It isn’t particularly fast (although it is faster than my first program, which just tried all possible sets of votes). It runs in 251ms.

      Run: [ @replit ]

      from enigma import (group, subsets, join, unpack, irange, decompose, cproduct, map2str, printf)

candidates = "ABCD"

# consider possible voting patterns (first, second, third, fourth)
# grouped by first choice
patterns = group(subsets(candidates, size=len, select="P", fn=join), by=(lambda x: x[0]))

# count the number of first choice votes
def first(vs, ks):
  d = dict((k, 0) for k in ks)
  for v in vs:
    d[v[0]] += 1
  return sorted(d.items(), key=unpack(lambda p, n: n), reverse=1)

# eliminate a candidate
def eliminate(vs, x):
  return list(v.replace(x, '', 1) for v in vs)

# calculate Borda points
def borda(vs, ks):
  n = len(ks)
  d = dict((k, 0) for k in ks)
  for v in votes:
    for (i, x) in enumerate(v):
      d[x] += n - i
  return d

# check the remaining puzzle constraints
# return Borda points
def check(N, votes):

  # first D is eliminated
  vs = eliminate(votes, 'D')
  # count the number of first choices
  ((p1, n1), (p2, n2), (p3, n3)) = first(vs, "ABC")
  #  there is no majority of first choices, and B is eliminated
  if 2 * n1 > N or not (n2 > n3 and p3 == 'B'): return

  # then B is eliminated
  vs = eliminate(vs, 'B')
  # count the number of first choices again
  ((p1, n1), (p2, n2)) = first(vs, "AC")
  if not (p1 == 'C' and 2 * n1 > N): return

  # count Borda points
  pts = borda(votes, candidates)
  # D and C are equal first, then B, then A
  if not (pts['D'] == pts['C'] > pts['B'] > pts['A']): return

  # return Borda points
  return pts

# consider the number of voters [6, 24]
for N in irange(6, 24):
  # consider the number of first choice votes (A does not have a majority)
  for (A, B, C, D) in decompose(N, 4, increasing=-1, sep=1, min_v=0, max_v=min(6, N // 2)):
    # choose the votes
    vs = (subsets(patterns[k], size=n) for (k, n) in zip("ABCD", (A, B, C, D)))
    for (As, Bs, Cs, Ds) in cproduct(vs):
      votes = As + Bs + Cs + Ds
      pts = check(N, votes)
      if pts:
        printf("points: {pts}", pts=map2str(pts, arr="=", sep=" ", enc=""))
        printf("-> {n} votes {votes}", n=len(votes), votes=join(votes, sep=" ", enc="[]"))
        printf()

      Solution: The Borda points are: A=33, B=35, C=36, D=36.

      There are 14 voters and the votes cast are:

      ABCD, ABDC, ACDB, ADBC, ADCB
      BCAD, BCDA, BDAC, BDCA
      CBDA, CDAB, CDBA
      DCAB, DCBA

      Using “first-past-the=post”, A wins with 5 votes, B has 4, C has 3, D has 2.

      Under “alternative vote” the first round is as given above. D is eliminated and his 2 votes are redistributed to give: A=5, B=4, C=5. Again there is no outright winner, so C’s 4 votes are redistributed to give: A=6, C=8, and C wins.

      Like

      • Frits's avatar

        Frits 10:58 am on 11 June 2022 Permalink | Reply

        @Jim,

        With a little analysis you can halve the run time by choosing a better range of number of voters than [6, 24].

        Like

        • Jim Randell's avatar

          Jim Randell 1:32 pm on 11 June 2022 Permalink | Reply

          I went with the smallest possible number of voters: D=0, C=1, B=2, A=3, gives a total of 6 voters.

          But in this scenario when D is eliminated there would be no votes to redistribute, so we can move to: D=1, C=2, B=3, A=4, to give a total of 10 voters.

          But when D’s votes are redistributed it is enough to knock B into last place, so C needs to gain at least 2 votes to leapfrog B.

          So we can increase minimum possible to: D=2, C=3, B=4, A=5, for a total of 14 voters.

          Incorporating this into my program brings the run time down to 384ms.

          And with a bit more analysis of the alternative vote system we can see that the number of voters is in {14, 15, 17, 18}.

          Like

          • Frits's avatar

            Frits 1:59 pm on 11 June 2022 Permalink | Reply

            @Jim,

            Yes, [14, 15, 17, 18] is what I had in mind.

            Like

          • Frits's avatar

            Frits 2:05 pm on 11 June 2022 Permalink | Reply

            My PuzzlingInPython program also early rejects N=18.

            Like

    • Hugh+Casement's avatar

      Hugh+Casement 9:48 am on 19 June 2022 Permalink | Reply

      I really don’t see the point of optimizing the run time for a program that is run only once.
      It takes far longer to write it!

      Like

      • Jim Randell's avatar

        Jim Randell 10:59 pm on 19 June 2022 Permalink | Reply

        If possible, I aim for a generic program that runs in under 1s, and if I can get the run time down to 100ms that’s even better (although I still like to keep it generic if possible).

        In this case my initial attempt ran in 44s, so I accepted I might have to tune it a little to improve on the run time. It wasn’t very much work, and the program posted above ran in less than 1s. I did do some more tweaking which got the run time down to 74ms, but I didn’t think the extra complication was worth posting.

        Like

        • Hugh+Casement's avatar

          Hugh+Casement 9:51 am on 20 June 2022 Permalink | Reply

          This is not process control, where milliseconds may well matter!

          If a program takes many minutes to run (while I go and do something else), I probably find it worth spending a bit of time to try and improve the method or find a different line of attack.
          But one has to keep a sense of proportion.

          Like

  • Unknown's avatar

    Jim Randell 10:12 am on 9 June 2022 Permalink | Reply
    Tags:   

    Teaser 2754: Family history 

    From The Sunday Times, 5th July 2015 [link] [link]

    Three of George’s relatives who were born in different years of the 20th century shared the same birthday. Writing these in the form D/M/Y with just two digits for the year, he tells Martha that: in one case D divided by M, when expressed as a percentage, is Y; in another M is the average of D and Y; in the remaining one D raised to the power M equals Y. George then told Martha that knowing the day, D, would not enable her to work out the three dates, but knowing any one of the three years would enable her to work out all three dates.

    What is the most recent of the three birth dates?

    [teaser2754]

     
    • Jim Randell's avatar

      Jim Randell 10:13 am on 9 June 2022 Permalink | Reply

      The years are all in the 20th Century (i.e. 1901 – 2000).

      This Python program runs in 57ms. (Internal runtime is 536µs).

      Run: [ @replit ]

      from enigma import (
  irange, product, div, seq_all_different as all_different,
  filter_unique, unpack, intersect, printf
)

# generate possible dates
def generate():
  # choose values for D and M
  for (D, M) in product(irange(1, 31), irange(1, 12)):
    if D > 28 and M == 2: continue
    if D > 30 and M in {4, 6, 9, 11}: continue

    # calculate the 3 (truncated) years
    Ys = (div(100 * D, M), 2 * M - D, D ** M)
    if any(y is None or y < 0 or y > 99 for y in Ys): continue
    if not all_different(Ys): continue
    yield (D, M, Ys)

# candidate solutions
ss = generate()

# knowing D does not let you work out the solution
ss = filter_unique(ss, unpack(lambda D, M, Ys: D)).non_unique

# but knowing _any_ of the years would let you work it out
fn = lambda k: unpack(lambda D, M, Ys: Ys[k])
ss = intersect(filter_unique(ss, fn(k)).unique for k in (0, 1, 2))

# output solution
for (D, M, Ys) in ss:
  (Y1, Y2, Y3) = Ys
  printf("D={D} M={M} -> Y1={Y1:02d} Y2={Y2:02d} Y3={Y3:02d}")
  Y = max((2000 if y == 0 else y + 1900) for y in Ys)
  printf("-> most recent (D/M/Y) = {D}/{M}/{Y}")

      Solution: The most recent of the birth dates is: 2/5/40 (i.e. 2nd May 1940).

      All birthdays are 2nd May, and the years are: 1908, 1932, 1940.

      So we have:

      2/5 = 40% → 1940
      5 is the mean of 2 and 8 → 1908
      2^5 = 32 → 1932

      At the time of publication the most recent birthdays would be: 107th, 83rd, 75th.

      There are 7 possible D/M pairs:

      D=1 M=2 → Ys=(50, 3, 1)
      D=1 M=4 → Ys=(25, 7, 1)
      D=1 M=5 → Ys=(20, 9, 1)
      D=1 M=10 → Ys=(10, 19, 1)
      D=2 M=4 → Ys=(50, 6, 16)
      D=2 M=5 → Ys=(40, 8, 32)
      D=3 M=4 → Ys=(75, 5, 81)

      The last of these is excluded as D is unique.

      The D=2 M=5 case is the only one which can be uniquely determined given any of the Y values.

      Like

  • Unknown's avatar

    Jim Randell 7:52 am on 7 June 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 713: Better and better 

    From The Sunday Times, 16th March 1975 [link]

    When the four modest gamblers — Al, Bill, Carl and Don — sat down for their usual game of poker, each of the four placed on the table, as their stake money for the evening, a different whole number of pence.

    After a number of hands, Al found that he had exactly doubled the number of pence with which he had started. it was his turn to provide the evening’s refreshments, and he bought the first round of drinks. After a few more hands, Al exactly doubled the number of pence he had had left after buying the first round and he then bought a second round. Thereafter he repeated the process, i.e. he exactly doubled his remaining pence and bought a third round.

    During the fourth session, Al took every penny his three opponents still had on the table and found that he had exactly doubled the number of pence he had had left after buying the third round. He then bought a fourth round — which took every penny he himself had!

    Each of the four rounds of drinks cost precisely the same whole number of pence.

    Carl began the game with a number of pence (between 50 and 100) which was exactly half the total number of pence which Bill and Don had between them at the start.

    How many pence did Al have when the game began?

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

    [teaser713]

     
    • Jim Randell's avatar

      Jim Randell 7:55 am on 7 June 2022 Permalink | Reply

      If the starting amounts are (A, B, C, D). Then at the end of the first session A now has 2A and buys a round (costing R), so starts the second session with (2A − R).

      He ends the second session with twice his starting amount, i.e. (4A − 2R), and buys another round. So starts the third session with (4A − 3R).

      He ends the third session with twice his starting amount, i.e. (8A − 6R), and buys another round. So starts the fourth session with (8A − 7R).

      He ends the fourth session with twice his starting amount, i.e. (16A − 14R), and buys another round, leaving him with no money.

      Hence:

      16A − 15R = 0
      R = (16/15)A

      Also the purchasing of the 4 rounds used up all of the money:

      4R = A + B + C + D
      (4(16/15) − 1)A = B + C + D
      A = (15/49)(B + C + D)

      Now: C = (B + D) / 2, so:

      B + D = 2C
      A = (15/49)(3C)
      A = (45/49)C

      And:

      R = (16/15)A
      R = (48/49)C

      48 has no factors of 7, so C must have (at least) 2 factors of 7. And as C is in [50, 100] we must have:

      C = 98
      B + D = 196
      A = 90
      R = 96

      All that remains is to ensure B and D can be assigned values such that each of the four starts with a different stake.

      If we keep keep the stakes below 100p we can assign B and D to 97p and 99p (in some order). The four starting amounts are then (90p, 97p, 98p, 99p).

      Solution: Al started the game with 90p.

      So Al’s progress is:

      1: 90p → 180p; spends 96p
      2: 84p → 168p; spends 96p
      3: 72p → 144p; spends 96p
      4: 48p → 96p; spends 96p

      Like

  • Unknown's avatar

    Jim Randell 9:14 am on 5 June 2022 Permalink | Reply
    Tags:   

    Teaser 2868: Prime logic 

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

    Three expert logicians played a game with a set of twenty-one cards each containing a different two-figure prime number. Each drew a card and held it up so that they could not see their own card but could see the others. Alf, Bert and Charlie in turn were then asked two questions, namely “Is your number the smallest of the three?” and “Is your number the largest of the three?”. In the first round all three answered “Don’t know” to both questions. The same happened in rounds two and three. In round four Alf answered “Don’t know” to the first question.

    What did Alf answer to the second question and what numbers did Bert and Charlie have?

    News

    When I started the S2T2 site (in February 2019), I already had notes for a number of Teaser puzzles that I had solved at the time of publication. And since then I have been steadily posting my notes for these puzzles to the site. This puzzle completes the accumulation of these notes, so there is now a complete archive of puzzles I solved at the time of publication from July 2015 to present.

    I shall continue to post puzzles from 2011 – 2015 corresponding to the collections of Teasers published as books in 2019 and 2020 (see: [Books]), but these puzzles will be new to me.

    Also, the posting of this puzzle also means that all puzzles from Teaser 2831 onwards are available on S2T2. Earlier Teaser puzzles are available via The Sunday Times Digital Archive (which is my source for older puzzles on the site).

    [teaser2868]

     
    • Jim Randell's avatar

      Jim Randell 9:15 am on 5 June 2022 Permalink | Reply

      Although it is not explicitly made clear I have assumed that at the beginning for the game each player draws a card, and then the three cards remain the same while the rounds of questions proceed.

      The puzzle would work just as well with cards numbered 1 – 21 (although the numbers on the final cards would be different).

      This program starts out with all possible ways for the 3 cards to be chosen. There are P(20, 3) = 7980 possibilities.

      We then consider the first three rounds where A, B, C answer “Don’t know” to both questions, eliminating possibilities where they would be able to give a different answer. And in the fourth round A answers “Don’t know” to the first question. The remaining possibilities then give the answer to the puzzle.

      It runs in 123ms. (Internal runtime is 62.9ms).

      Run: [ @replit ]

      from enigma import (primes, seq_all_same_r, group, ordered, delete, subsets, printf)

# indices for A, B, C
(A, B, C) = (0, 1, 2)

# consider the 21 cards
cards = list(primes.between(10, 99))  # 2-digit primes
#cards = list(irange(1, 21))  # 1 - 21 work just as well
assert len(cards) == 21

smallest = lambda x, y: x < y
largest = lambda x, y: x > y

# answer question <fn> with knowledge <ks> and other cards <others>
# return "Yes", "No", "???" (= "Don't know")
def check(ks, others, fn):
  r = seq_all_same_r(all(fn(x, y) for y in others) for x in ks)
  # there should be at least one choice
  assert not r.empty
  if r.same:
    # if all choices had the same value the answer is "Yes" or "No"
    return ('Yes' if r.value else 'No')
  else:
    # mismatch, answer is "Don't know"
    return '???'

# return new set of possibilities where the answer to questions <qs> is as specified
def question(label, ps, i, *qs):
  # map: <others> -> <possibilities>
  d = group(ps, by=(lambda p: ordered(*delete(p, [i]))), fn=set)
  # consider possibilities based on the other cards I can see
  ps1 = set()
  for (others, ps) in d.items():
    # person <i> must be holding one of these cards
    ks = set(p[i] for p in ps)
    # must give correct answer to all questions
    if any(check(ks, others, fn) != r for (fn, r) in qs): continue
    # collect the viable possibilities
    ps1.update(ps)
  if label: printf("[{label}] {n} possibilities", n=len(ps1))
  return ps1

# initial possible assignments of cards
ps = set(subsets(cards, size=3, select="P"))
printf("[---] {n} possibilities", n=len(ps))

# the first three rounds, answers are all "Don't know"
for rnd in "123":
  ps = question(rnd + ".A", ps, A, (smallest, '???'), (largest, '???'))
  ps = question(rnd + ".B", ps, B, (smallest, '???'), (largest, '???'))
  ps = question(rnd + ".C", ps, C, (smallest, '???'), (largest, '???'))

# [4.A.1] answer is "Don't know"
ps = question("4.A.1", ps, A, (smallest, '???'))

# output remaining possibilities
for r in ("Yes", "No", "???"):
  for (a, b, c) in question(None, ps, A, (largest, r)):
    printf("-> A={a} B={b} C={c}, answer to 4.A.2 is \"{r}\"")

      Solution: Alf’s answer to the second question in round four is “No”. Bert and Charlie had cards with numbers 47 and 59 (respectively).

      After the first 3 rounds and A’s answer to the first question of the fourth round there are only 2 possibilities remaining:

      A=43 B=47 C=59
      A=53 B=47 C=59

      Like

    • Frits's avatar

      Frits 11:11 am on 6 June 2022 Permalink | Reply

      Easier to read and with better performance:

      [https://brg.me.uk/?page_id=4512]

      Like

      • Jim Randell's avatar

        Jim Randell 11:32 pm on 6 June 2022 Permalink | Reply

        @Frits: I took a generic approach to the puzzle. The program runs pretty much instantaneously, so I didn’t feel the need for additional analysis to simplify the programming or make it run faster.

        Like

    • Frits's avatar

      Frits 11:29 am on 7 June 2022 Permalink | Reply

      Based on Brian’s program and avoiding the use of defaultdict.

         
from itertools import product

# all two digit primes
P = [x for x in range(11, 100, 2) if all(x % p for p in (3, 5, 7))]
 
# In answering the question 'is your number the smallest of the three?',
# if they see numbers held by the other two that are less than or equal
# to their current inferred minimum, they would be able to answer 'no';
# so when they answer "don't know" we can remove such numbers as possible
# for the other two; being unable to answer the question 'is your number
# the largest of the three?' similarly allows us to remove numbers for
# the others that are greater than or equal to their inferred maximum. 
# The same numbers will also be removed from the questioner his/her self
# during the next question.

# After 3 rounds of questions 9*2 numbers have been removed for A and B
# and 9*2 - 1 numbers for C (as C asked the last question)

A = P[9:-9]
B = P[9:-9]
C = P[8:-8]

# In round four Alf answered "Don't know" to the first question.
# Alf's inferred minimum was A[0] so Bert and Charlie drew cards > A[0]
B = [p for p in B if p > A[0]]
C = [p for p in C if p > A[0]]

# map possible values for B and C to lists of possible A values
d = {tuple(sorted(prd)): [a for a in A if a not in prd]
     for prd in product(B, C) if prd[0] != prd[1] 
         and any(p < A[-1] for p in prd)}

# Alf can give an answer if he has only one possible number 
d = {k: vs for k, vs in d.items() if len(vs) > 1}

# report possibilities that are left
for bc, a in d.items():
  # Alf is asked "Is your number the largest of the three?"
  ans = "Yes" if a[0] > bc[-1] else "No" if a[-1] < bc[-1] else "Don't know"
  
  # all values in B are also in C, check if high number only occurs in C
  (bc, relation) = (set(bc), "in") if bc[-1] in B else (bc, "=")     
      
  print(f"answer = {ans}, (B, C) {relation} {bc} and A in {set(a)}")

      Like

  • Unknown's avatar

    Jim Randell 6:14 pm on 1 June 2022 Permalink | Reply
    Tags:   

    Teaser 3115: Germometric mean 

    From The Sunday Times, 5th June 2022 [link] [link]

    On Whit Monday, Zak began self-isolating upstairs. At lunchtime Kaz shouted up: “What’s a Geometric Mean?”

    “It’s the Nth root of the product of N values”, Zak replied.

    On TV, Teaseside hospital’s “geovid” admissions for the seven days prior were listed alongside their Geometric Mean. Kaz stated that chronologically the numbers comprised a decreasing set of two-figure values, Friday’s value equalling the Geometric Mean. She added that, curiously, there was a value double the Geometric Mean, but not triple, whereas the Geometric Mean was triple a data value, but not double a data value. She then told Zak just the Geometric Mean.

    Zak worked out the unique data set.

    Give the seven numbers in chronological order.

    [teaser3115]

     
    • Jim Randell's avatar

      Jim Randell 6:41 pm on 1 June 2022 Permalink | Reply

      The following Python program runs in 70ms. (Internal run time is 9.7ms).

      Run: [ @replit ]

      from enigma import (irange, divisors, filter2, div, reverse, singleton, printf)

# generate <k> increasing values from <vs> with product <v>
def decompose(v, k, ds, ss=[]):
  if k == 1:
    if v in ds:
      yield ss + [v]
  elif not (len(ds) < k):
    for (i, d) in enumerate(ds):
      v_ = div(v, d)
      if v_ is not None:
        yield from decompose(v_, k - 1, ds[i + 1:], ss + [d])

# generate candidate values for geometric mean <gm>
def generate(gm):
  # find the remaining values
  ds = list(d for d in divisors(gm, 6) if 9 < d < 100 and d != gm)
  for vs in decompose(gm**6, 6, ds):
    # there are 2 values less than gm (and 4 values greater)
    (lt, gt) = filter2((lambda x: x < gm), vs)
    if len(lt) != 2: continue
    # there is a gm/3 value, but not a gm/2 value
    if (gm // 3 not in lt) or (div(gm, 2) in lt): continue
    # there is a gm*2 value, but not a gm*3 value
    if (gm * 2 not in gt) or (gm * 3 in gt): continue
    # return the sequence, Mo - Su
    yield reverse(gt) + [gm] + reverse(lt)

# consider values for the geometric mean: gm/3 and gm*2 are 2-digit values
for gm in irange(30, 49, step=3):
  # is there only a single candidate solution?
  ns = singleton(generate(gm))
  if ns:
    # output solutions
    printf("{ns}")

      Solution: The numbers are (Mon – Sun): 96, 72, 64, 54, 48, 32, 16.

      The geometric mean is 48, and there is a value twice the geometric mean (98), but not three times (144). There is also a value one third of the geometric mean (16), but not one half (24).

      This is the only possible sequence with a geometric mean of 48.

      However there are other possible sequences with a geometric mean of 42:

      (98, 84, 81, 49, 42, 14, 12)
      (98, 84, 54, 49, 42, 18, 14)
      (84, 63, 56, 49, 42, 27, 14)
      (84, 63, 54, 49, 42, 28, 14)

      Like

      • Jim Randell's avatar

        Jim Randell 6:49 am on 2 June 2022 Permalink | Reply

        And here is an even faster version:

        If g is the geometric mean we have a decreasing sequence of values (Mon – Sun):

        (a, b, c, d, g, e, f)

        Such that:

        g^7 = a × b × c × d × g × e × f

        And we know one of the values greater than g (i.e. one of (a, b, c, d)) has a value of 2g, and one of the values less than g (i.e. one of (e, f)) has a value of (g / 3) (which tells us g is a multiple of 3).

        Hence:

        (3/2)(g^4) = [3 of (a, b, c, d)] × [1 of (e, f)]

        Which tells us g is also a multiple of 2.

        Furthermore (g / 3) is a 2-digit value, so g ≥ 30, and 2g is also a 2-digit value, so g < 50.

        This Python program considers possible values for the geometric mean, and finds the three remaining values higher than the mean, and the value lower than the mean. If a mean leads to a single possible set of values, then we have found the solution.

        It runs in 54ms. (Internal runtime is 167µs).

        Run: [ @replit ]

        from enigma import (irange, div, diff, singleton, printf)

# reversed sort
rsort = lambda x: sorted(x, reverse=1)

# find <k> increasing values from <ds> whose product divide into <v>
# return: (<ns>, <r>) where <r> is the remainder
def decompose(v, k, ds, ns=[]):
  if k == 0:
    yield (ns, v)
  elif not (len(ds) < k):
    for (i, d) in enumerate(ds):
      v_ = div(v, d)
      if v_ is not None:
        yield from decompose(v_, k - 1, ds[i + 1:], ns + [d])

# generate candidate sequences for geometric mean <gm>
def generate(gm):
  # find 2-digit divisors of (3/2)gm^4 greater than gm
  v = 3 * div(gm**4, 2)
  ds = diff((d for d in irange(gm + 1, 99) if v % d == 0), {2 * gm, 3 * gm})
  for (gt, r) in decompose(v, 3, ds):
    # there is no gm/2 value
    if (not 9 < r < gm) or 2 * r == gm or 3 * r == gm: continue
    # return the sequence (in decreasing order)
    yield rsort(gt + [2 * gm]) + [gm] + rsort([r, gm // 3])

# consider values for the geometric mean, gm is a multiple of 6
for gm in irange(30, 49, step=6):
  # is there only a single candidate solution?
  ns = singleton(generate(gm))
  if ns:
    # output solutions
    printf("[Mon - Sun] = {ns}")

        Like

        • Frits's avatar

          Frits 1:30 pm on 2 June 2022 Permalink | Reply

          Using divisors_tuples() is slower than the decompose() method.

             
from enigma import divisors_tuples

# return entry where column <col> is unique
def unique_col(seq, col=0):
  d = dict()
  for s in seq:
       d[s[col]] = s[col] in d
   
  return [s for s in seq if not d[s[col]]]

# there is a gm/3 value and there is a 2*gm value
# gm must also be even as gm^7 is even 

sol = []
# consider values for the geometric mean: gm/3 and gm*2 are 2-digit values
for gm in range(30, 50, 6):
  # generate seven 2-digit numbers that multiply to gm^7
  nums = [sorted(x + (gm // 3, gm, 2 * gm), reverse = True) 
         for x in divisors_tuples(3 * (gm**4 // 2), 4) 
         if all(9 < y < 100 for y in x) 
            and gm // 2 not in x 
            and 3 * gm not in x]
 
  # store valid solutions
  sol += [x for x in nums if len(set(x)) == 7 and x[4] == gm]

print("answer =", *unique_col(sol, 4))

          A basic SubstitutedExpression program takes about 5 seconds (with PyPy).

          Like

    • Frits's avatar

      Frits 2:58 pm on 2 June 2022 Permalink | Reply

      Program runs in 75ms (with PyPy).

         
from enigma import SubstitutedExpression

# the alphametic puzzle
p = SubstitutedExpression(
  [
   # there is a gm/3 value and there is a gm*2 value
   # gm must also be even as gm^7 is even so E is even
   "(G + M) % 3 == 0",
   
   # 1.5 * GM**4 is the product 4 unknown sorted numbers AB, CD, EF and PQ
  
   "AB < GM",
   "CD > GM",
   "EF > GM",
   "CD < EF",
   
   "div(3 * GM**4 // 2, AB * CD * EF) = PQ",
   "PQ > EF",
   
   # seven different numbers
   "len(set([AB, CD, EF, PQ, GM, 2 * GM, GM // 3])) == 7",
   # friday's value equalling the geometric mean
   "sorted([AB, CD, EF, PQ, GM, 2 * GM, GM // 3])[2] == GM",
   
   # there is no 3*gm or gm/2 value
   "3 * GM not in {AB, CD, EF, PQ, GM, 2 * GM, GM // 3}",
   "GM // 2 not in {AB, CD, EF, PQ, GM, 2 * GM, GM // 3}",
   
  ],
  answer="sorted([AB, CD, EF, PQ, GM, 2 * GM, GM // 3], reverse=1)",
  d2i=dict([(0, "GACEP")] + 
           [(1, "GCEM")] +                       
           [(2, "GCE")] +
           [(3, "M")] +
           [(5, "AGM")] +
           [(6, "AG")] +
           [(7, "AGM")] +
           [(8, "AG")] +
           [(9, "AGM")]),
  distinct="",
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# store answers
d = dict()
for (_, ans) in p.solve():
  d[ans[4]] = d.get(ans[4], []) + [ans]
  
for v in d.values():
  if len(v) == 1:
    print(*v)

      Like

  • Unknown's avatar

    Jim Randell 12:59 pm on 31 May 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 707: The reigning king 

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

    In the World Chess Championships, under the old rules, the reigning champion wins when he has scored at least 12 points (1 for a win and ½ for a draw) or the challenger wins when he has scored 12½ points.

    When the system was last used the contest required its full 24 games, the challenger’s won games with the White pieces was equal to the total number of draws, and the reigning champion’s lost games with the White pieces was either one more or one less than this number.

    What was the result of the final game?

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

    [teaser707]

     
    • Jim Randell's avatar

      Jim Randell 1:00 pm on 31 May 2022 Permalink | Reply

      After 23 games (and 23 points distributed), the reigning champion (R) must have less than 12 points, and the challenger (C) must have less than 12.5 points.

      Possibilities [and outcomes for the final match] are:

      R=11.5, C=11.5 [draw → R=12.0, C=12.0; R wins → R=12.5, C=11.5; C wins → R=11.5, C=12.5]
      R=11.0, C=12.0 [draw → R=11.5, C=12.5; R wins → R=12.0, C=12.0; C wins → R=11.0, C=13.0]

      If, after 24 games, there were x draws. And C won x games playing white. And R lost (x ± 1) games playing white.

      The games lost by R playing white were won by C playing black, so C’s total number of points is:

      C = 0.5x + x + (x ± 1)
      C = 2.5x ± 1

      And C’s total points must be in (11.5, 12.0, 12.5, 13.0):

      11.5 = 2.5x + 1 ⇒ x = 4.2 [impossible]
      11.5 = 2.5x − 1 ⇒ x = 5
      12.0 = 2.5x + 1 ⇒ x = 4.4 [impossible]
      12.0 = 2.5x − 1 ⇒ x = 5.2 [impossible]
      12.5 = 2.5x + 1 ⇒ x = 4.6 [impossible]
      12.5 = 2.5x − 1 ⇒ x = 5.4 [impossible]
      13.0 = 2.5x + 1 ⇒ x = 4.8 [impossible]
      13.0 = 2.5x − 1 ⇒ x = 5.6 [impossible]

      The only possibility is x = 5, and so C drew 5 games, won 5 games playing white, and won 4 games playing black, giving a total of 5 draws, 9 wins and 11.5 points.

      So R had 12.5 points, and has drawn 5 and won 10 games, and the championship.

      Solution: The final game (and championship) was won by the reigning champion.

      And before the final game each player was on 11.5 points (9 wins + 5 draws).

      Like

  • Unknown's avatar

    Jim Randell 9:53 am on 29 May 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 110: Rectangular blocks 

    From The Sunday Times, 5th May 1963 [link]

    Two rectangular blocks have all their dimensions an exact number of inches, all different.

    The sum of the edges of one block is equal to the sum of the edges of the other.

    The sum of the areas of the faces of one block is equal to the sum of the areas of the faces of the other.

    The volumes of the two blocks, however, differ by 140 cubic inches.

    If the smallest of the 6 dimensions of the two blocks is 5 inches, what are the dimensions of the blocks?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser110]

     
    • Jim Randell's avatar

      Jim Randell 9:54 am on 29 May 2022 Permalink | Reply

      For blocks with dimensions (x, y, z) this Python program consider blocks that be made with the same (x + y + z) value, and then looks for two with the same surface area, but with areas that differ by 140.

      It runs in 62ms. (Internal runtime is 4.7ms).

      Run: [ @replit ]

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

# for comparing surface areas
area = lambda ds: 2 * sum(x * y for (x, y) in subsets(ds, size=2))

# for calculating volumes
vol = multiply

# find the first solution
def main():
  # consider increasing x + y + z values
  for t in irange(18, inf):
    # consider possible dimensions for the blocks
    for (b1, b2) in subsets(decompose(t, 3, increasing=1, sep=1, min_v=5), size=2):
      ds = set(b1 + b2)
      if not (len(ds) == 6 and 5 in ds): continue
      if not (area(b1) == area(b2)): continue
      if not (abs(vol(b1) - vol(b2)) == 140): continue
      printf("t={t}: {b1} {b2}")
      return  # we only need the first value

main()

      Solution: The dimensions of the blocks are: (5 × 14 × 17) inches, (7 × 10 × 19) inches.

      Like

    • Jim Randell's avatar

      Jim Randell 11:38 am on 29 May 2022 Permalink | Reply

      Or, using some analysis:

      If the blocks have dimensions (a, b, c) and (x, y, z), then we have (assuming (a, b, c) has the larger volume):

      a + b + c = x + y + z
      ab + ac + bc = xy + xz + yz
      abc − xyz = 140

      Now, if we consider the expression:

      (a − 5)(b − 5)(c − 5) − (x − 5)(y − 5)(z − 5)
      = (abc − 5(ab + ac + bc) + 25(a + b + c) − 125) − (xyz − 5(xy + xz + yz) + 25(x + y + z) − 125)
      = 140

      We note that one side of the subtraction must equal zero, so the other is ±140.

      And as all the numbers multiplied together in each side of the subtraction are non-negative, it must be the right-hand term that is zero. Hence x = 5.

      So we can look at divisors of 140 to determine the dimensions (a, b, c), and then choose (x, y, z) to give the same sum, and check the surface area constraint.

      Here is a Python program that fully explores the solution space. It runs in 57ms. (Internal run time is 236µs).

      Run: [ @replit ]

      from enigma import (subsets, divisors_tuples, is_pairwise_distinct, div, printf)

# surface area
area = lambda *ds: 2 * sum(x * y for (x, y) in subsets(ds, size=2))

# start with x = 5
x = 5
# calculate dimensions for (a, b, c)
for (a, b, c) in divisors_tuples(140, 3):
  (a, b, c) = (a + x, b + x, c + x)
  if not is_pairwise_distinct(a, b, c, x): continue
  # find possible y, z values, given xyz = abc - 140
  n = div(a * b * c - 140, x)
  if n is None: continue
  for (y, z) in divisors_tuples(n, 2):
    if not (x < y < z and x + y + z == a + b + c): continue
    # all dimensions are distinct
    if not is_pairwise_distinct(x, y, z, a, b, c): continue
    # check the areas
    if area(a, b, c) != area(x, y, z): continue
    # output solution
    printf("{b1} {b2}", b1=(x, y, z), b2=(a, b, c))

      Like

      • Mark Valentine's avatar

        Mark Valentine 12:42 pm on 30 May 2022 Permalink | Reply

        Nice trick to factorise with x-5 to obtain the zero. I was factorising with x+1 not getting anywhere.

        Like

      • Frits's avatar

        Frits 1:44 pm on 31 May 2022 Permalink | Reply

        @Jim,

        I you disable the area check in the first program you get answer (5, 6, 14) (7, 8, 10) and if you disable in the second program you get anwer (5, 14, 17) (7, 10, 19).

        Like

      • Frits's avatar

        Frits 2:16 pm on 31 May 2022 Permalink | Reply

        @GeoffR, the problem with MiniZinc most of the times that you have to set boundaries.
        You have chosen 25 as upper limit.

        Like

        • GeoffR's avatar

          GeoffR 6:59 pm on 31 May 2022 Permalink | Reply

          @Frits:
          The teaser description gives us a means to fix the LB.

          With no prior knowledge of the solution and no logical means to set the UB, I guess the UB could be set fairly high to try and find a solution in MiniZinc. It could then reduced by trial and error if an improvement in total run-time was needed.

          I did an experiment for this teaser, varying the upper bound, to see the variation in run-time to find a solution and the total run-time:

          Upper bound = 25 (Soln = 170ms, Total time = 170ms)
          Upper bound = 50 (Soln = 170ms, Total time = 180ms)
          Upper bound = 100 (Soln = 170ms, Total time = 230ms)
          Upper bound = 200 (Soln = 170ms, Total time = 530ms)

          Absolute boundaries do not seem that important practically in this case.

          Like

      • Frits's avatar

        Frits 8:41 pm on 31 May 2022 Permalink | Reply 

           
from enigma import is_square_p

# dimensions are (a + 5), (b + 5), (c + 5) and 5, y, z

# as (4, 5, 7) is the 140-factorization with the highest lowest factor
# a is less equal to 4 (and not divisble by 3)
for a in [1, 2, 4]:
  # as (1, 10, 14) is the 140-factorization with the highest middle factor
  # b is less equal to 10 (and not divisble by 3 or 8)
  for b in [2, 4, 5, 7, 10]:
    if b <= a: continue
    
    # a * b * c = 140
    (c, r) = divmod(140, a * b)
    if r or c <= b: continue
    
    # sum of edges is the same
    # a + b + c + 15 - 5 - y = z
    # volume difference is equal to 140
    # ((a + 5) * (b + 5) * (c + 5) - 140) / 5y = z
    
    # (5 * y) * (a + b + c + 10 - y) = ((a + 5) * (b + 5) * (c + 5) - 140) 
    # 5y^2 - 5 * (a + b + c + 10) * y + (a + 5) * (b + 5) * (c + 5) - 140 = 0
    
    # calculate discriminant
    D = (5 * (a + b + c + 10))**2 - 20 * ((a + 5) * (b + 5) * (c + 5) - 140)
    if D < 0 or not is_square_p(D): continue
    
    # choose lowest solution as y < z
    y = (5 * (a + b + c + 10) - D**.5) // 10 
    z = a + b + c + 15 - 5 - y
    print((a + 5, b + 5, c + 5), (5, y, z))

        Like

    • GeoffR's avatar

      GeoffR 12:45 pm on 29 May 2022 Permalink | Reply 

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

var 5..25:a; var 5..25:b; var 5..25:c; % 1st block

var 6..25:x; var 6..25:y; var 6..25:z; % 2nd block (bigger)

constraint all_different([a, b, c, x, y, z]);

constraint a == 5;
constraint a < b /\ b < c;
constraint x < y /\ y < z;

% The sum of the edges of one block is equal
% to the sum of the edges of the other.
constraint 4 * (a + b + c) == 4 * (x + y + z);

% The sum of the areas of the faces of one block is equal 
% to the sum of the areas of the faces of the other.
constraint 2 * (a * b + a * c + b * c) == 2 *(x * y + y * z + x * z);

% The volumes of the two blocks differ by 140 cubic inches.
constraint x * y * z == a * b * c + 140;

solve satisfy;

output[ "First block dimensions(inches) : " ++ show(a) ++ 
" by " ++ show(b) ++ " by " ++ show(c) 
++ "\n" ++ "Second block dimensions(inches) : " ++ show(x) 
++ " by " ++ show(y) ++ " by " ++ show(z)];

% First block dimensions(inches) : 5 by 14 by 17
% Second block dimensions(inches) : 7 by 10 by 19
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 4:50 pm on 27 May 2022 Permalink | Reply
    Tags:   

    Teaser 3114: Colourful characters 

    From The Sunday Times, 29th May 2022 [link] [link]

    George and Martha have recently taken a great-grandchild to a toddler’s birthday party. The youngsters like to traipse around over a pen with a large number of brightly coloured plastic balls. Actually there were 200 in total, some of red, yellow, blue and green. There were at least 30 but fewer than 70 of each colour, with the following properties:

    Red = perfect square
    Yellow = prime number
    Blue = palindromic number
    Green = divisible by three [different] single-digit prime numbers

    George told Martha the above information and the number of red balls. Martha was then able to work out the numbers of each of the others.

    How many of each colour were there?

    [teaser3114]

     
    • Jim Randell's avatar

      Jim Randell 5:18 pm on 27 May 2022 Permalink | Reply

      i.e. the number of red balls is a perfect square; the number of yellow balls is prime; etc.

      I required the number of green balls to be “divisible by exactly three different single-digit prime numbers”.

      The following Python program runs in 54ms. (Internal run time is 310µs).

      Run: [ @replit ]

      from enigma import (
  irange, is_prime, is_square, is_npalindrome, product,
  filter_unique, unpack, printf
)

# select candidate quantities [30, 69]
select = lambda fn: list(x for x in irange(30, 69) if fn(x))

# single digit primes
sdps = list(x for x in irange(0, 9) if is_prime(x))

# find the candidate quantities for each colour
Rs = select(is_square)
Ys = select(is_prime)
Bs = select(is_npalindrome)
Gs = select(lambda x: sum(x % d == 0 for d in sdps) == 3)

# generate possible (R, Y, B, G) combinations
def generate():
  for qs in product(Rs, Ys, Bs, Gs):
    if sum(qs) == 200:
      yield qs

# find combinations unique by the number of reds
reds = unpack(lambda R, Y, B, G: R)
for (R, Y, B, G) in filter_unique(generate(), reds).unique:
  printf("R={R} Y={Y} B={B} G={G}")

      Solution: The numbers of balls are: Red = 36, Yellow = 67, Blue = 55, Green = 42.

      Manually:

      There are only a few options for each colour:

      Red = (36, 49, 64)
      Yellow = (31, 37, 41, 43, 47, 53, 59, 61, 67)
      Blue = (33, 44, 55, 66)
      Green = (30, 42, 60)

      And we want combinations of these that sum to 200. Note that Yellow (prime) is always odd, so the sum of the other three must also be odd – Green is always even, so Red and Blue must be one odd and one even.

      We quickly find there are 5 candidate solutions:

      R=36 B=55 G=42 Y=67
      R=49 B=44 G=60 Y=47
      R=49 B=66 G=42 Y=43
      R=64 B=33 G=42 Y=61
      R=64 B=33 G=60 Y=43

      And only R=36 give a unique set of values.

      Like

      • Frits's avatar

        Frits 10:37 am on 28 May 2022 Permalink | Reply

        @Jim, I would have probably chosen a different alias name for the itertools cartesian product as using the name product in combination with numbers is ambiguous (to me).

        Like

        • Jim Randell's avatar

          Jim Randell 11:06 am on 28 May 2022 Permalink | Reply

          @Frits: A long time ago there used to have a product() function in enigma.py to calculate the product of a sequence of numbers.

          But I renamed it multiply() to avoid confusion with itertools.product() (which is a useful function in solving puzzles).

          Python 3.8 added a similar function to multiply() as math.prod().

          Like

        • Jim Randell's avatar

          Jim Randell 11:50 am on 10 July 2022 Permalink | Reply

          @Frits: I’ve added the [[ cproduct() ]] function to the enigma.py library. Which is an unpacked version of the [[ itertools.product() ]] function.

          It makes it neater to make a Cartesian product from a generator (which is quite a common occurrence in puzzles):

          # using itertools.product
product(*(<generator>))
# using cproduct
cproduct(<generator>)

          You can also use it for a fixed list of sets like this:

          # using itertools.product
product(As, Bs, Cs)
# using cproduct
cproduct([As, Bs, Cs])

          Like

    • GeoffR's avatar

      GeoffR 6:29 pm on 27 May 2022 Permalink | Reply

      Multiple output configuration produces five potential solutions, but only one of these solutions has a unique number of red balls, which gives the answer.

      
% A Solution in MiniZinc
include "globals.mzn";
 
% Red, Yellow, Blue and Green coloured ball numbers
var 30..69:R; var 30..69:Y; var 30..69:B; var 30..69:G;

constraint R + Y + B + G == 200;

predicate is_sq(var int: y) =
exists(z in 1..ceil(sqrt(int2float(ub(y))))) (z*z = y);

% R is a square number
constraint is_sq(R);

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

% Y is a prime number
constraint is_prime(Y);

% B is a 2-digit palindromic number
constraint B div 10 == B mod 10;

% G has 3 single digit prime divisors i.e three from 2, 3, 5, 7
constraint sum( [bool2int(G mod 2 == 0), bool2int(G mod 3 == 0), 
bool2int(G mod 5 == 0), bool2int(G mod 7 == 0)] ) == 3;

solve satisfy;

output [ "[R,Y,B,G ]= " ++ show( [R,Y,B,G ]) ];

      Like

    • Frits's avatar

      Frits 6:52 pm on 27 May 2022 Permalink | Reply 

         
from enigma import SubstitutedExpression

# return entry where column <col> is unique
def unique_col(seq, col=0):
  d = dict()
  for s in seq:
       d[s[col]] = s[col] in d
  
  return [s for s in seq if not d[s[col]]]

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # Red = perfect square
    "is_square(RD)",
    # Yellow = prime number
    "is_prime(YW)",
    # Blue = palindromic number
    "BE in {33, 44, 55, 66}",
    
    # there were 200 in total
    "200 - RD - YW - BE = GN",
    # Green = divisible by three single-digit prime numbers
    "sum(GN % p == 0 for p in [2, 3, 5, 7]) == 3",
   
  ],
  answer="RD, YW, BE, GN",
  d2i=dict([(k, "RYBG") for k in range(3)] + 
           [(k, "RYBG") for k in range(7, 10)]),
  distinct="",
  verbose=0,
)

colors = ["Red", "Yellow", "Blue", "Green"]
# get unique answers for number of red balls
uniq = unique_col([y for _, y in p.solve()])
print(*list(zip(colors, uniq[0])))

      Like

    • GeoffR's avatar

      GeoffR 9:01 am on 28 May 2022 Permalink | Reply

      Separate research found three possible values for Green between 30 and 69:

      G = 30, prime factors = 2 * 3 * 5
      G = 42, prime factors = 2 * 3 * 7
      G = 60, prime factors = 2 * 2 * 3 * 5

      
from collections import defaultdict
COL = defaultdict(list)

# Using R = Red, Y = Yellow, B = Blue, G = Green
for R in (36, 49, 64):  # Squares from 30..69
  # Primes between 30 and 69
  for Y in (31, 37, 41, 43, 47, 53, 59, 61, 67):
    # Palindromes between 30 and 69
    for B in (33, 44, 55, 66):
      for G in (30, 42, 60):
        if R + Y + B + G != 200:
          continue
        COL[R] += [(R, Y, B, G)]

for k, v in COL.items():
  if len(v) == 1:
    print(f"R={v[0][0]}, Y={v[0][1]}, B={v[0][2]}, G={v[0][3]}")

      Like

    • Frits's avatar

      Frits 10:12 am on 28 May 2022 Permalink | Reply

      No imports, using methods from Brian and Jim.

         
# pick one value from each entry of a <k>-dimensional list <ns>
# so that all elements sum up to <t>
def pickOneFromEach(k, ns, t, s=[]):
  if k == 1:
     # does the remainder occur in the first list?
     if t in ns[0]:
       yield s + [t]
  else:
    for n in ns[k-1]:
      yield from pickOneFromEach(k - 1, ns, t - n, s + [n])

sqs = [x * x for x in range(6, 9)]
# use set() as it will be only used for lookups
prms = set(x for x in range(31, 70, 2) if all(x % i for i in [2, 3, 5, 7]))
pals = [11 * x for x in range(3, 7)]
divs = [x for x in range(30, 70) if sum(x % i == 0 for i in [2, 3, 5, 7]) == 3]

# place the list with the most elements up front and squares at the end
mlst = [prms, divs, pals, sqs]
  
seen_once = dict()
# get unique answers for number of red balls
for x in pickOneFromEach(4, mlst, 200):  
  seen_once[x[0]] = x if x[0] not in seen_once else []

colors = ["Red", "Blue", "Green", "Yellow"]
for k, vs in seen_once.items():
  if vs:
    print(*list(zip(colors, vs)))

      Like

  • Unknown's avatar

    Jim Randell 9:11 am on 26 May 2022 Permalink | Reply
    Tags:   

    Teaser 2858: Beach game 

    From The Sunday Times, 2nd July 2017 [link] [link]

    Ken, Leanne, Mike, Nancy, Olive and Paul were playing on the beach. They had drawn a large circle in the sand and written their names clockwise, in that order, equally spaced around the edge of the circle. They also had a circular piece of card around which they had written the numbers 1 to 6 clockwise in order, also equally spaced. Then they spun the card in the middle of the sand circle and each child was awarded the number of points equal to the number closest to their name. They kept repeating this process and after each spin they kept a total of their scores so far. Mike was ahead after the first spin and after each of the first five spins there was a different clear leader. Then the tide came in and washed the game away.

    Which child was never in the lead, and what was that child’s total after the five spins?

    [teaser2858]

     
    • Jim Randell's avatar

      Jim Randell 9:12 am on 26 May 2022 Permalink | Reply

      This Python program runs in 58ms.

      Run: [ @replit ]

      from enigma import (irange, rotate, Record, map2str, printf)

# possible scores
scores = [1, 2, 3, 4, 5, 6]

# play <k> rounds of the game
# ss = scores
# ls = leaders
def play(k, ss, ls):
  if k == 0:
    yield (ss, ls)
  else:
    # choose a rotation
    for i in irange(0, 5):
      # calculate the new totals
      s = list(a + b for (a, b) in zip(ss[-1], rotate(scores, i)))
      # do we have a new clear leader?
      t = list(Record(pos=i, score=x) for (i, x) in enumerate(s))
      t.sort(key=(lambda x: x.score), reverse=1)
      if not (t[0].score > t[1].score and t[0].pos not in ls): continue
      # play the next game
      yield from play(k - 1, ss + [s], ls + [t[0].pos])

# M (pos 2) won the first game, so gets 6 points
s = rotate(scores, 3)
assert s[2] == 6

# play 4 more rounds of the game
for (ss, ls) in play(4, [s], [2]):
  # who was never in the lead?
  for n in irange(0, 5):
    if n in ls: continue
    # output solution
    name = "KLMNOP"
    for (i, s) in enumerate(ss):
      printf("{r}: {s}; leader={l}", r=i + 1, s=map2str(zip(name, s)), l=name[ls[i]])
    printf("never={name}, score={score}", name=name[n], score=ss[-1][n])
    printf()

      Solution: Nancy was never in the lead. After five spins she had 15 points.

      Like

  • Unknown's avatar

    Jim Randell 11:19 am on 24 May 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 704: … Go! 

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

    Peter and Robert run a ten-lap race on the track. They each have their own standard fast and slow times for a lap and they change pace only after complete laps.

    Peter runs his first five laps in the order: slow, slow, fast, slow, fast and repeats the sequence in the second half of the race. Robert starts with a slow lap and then runs alternate fast and slow laps throughout.

    Robert takes an immediate lead but his time advantage after 6 laps is halved by the finish. Peter takes the lead only once to reach a maximum advantage of one second, but he also once draws level only to fall behind again.

    What is Robert’s greatest time lead, and by what margin does he win the race?

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

    [teaser703]

     
    • Jim Randell's avatar

      Jim Randell 11:21 am on 24 May 2022 Permalink | Reply

      P and R both start at their slow pace, and R takes the lead, so P’s slow pace is slower than R’s slow pace.

      If we consider the time taken to complete a lap. P’s slow pace will be the longest time.

      Let the number of seconds to complete a lap be:

      P (slow): x
      R (slow): x − a
      P (fast): x − b
      R (fast): x − c

      where a, b, c are positive values, and c > a.

      P’s laps are: (slow, slow, fast, slow, fast) ×2, so his cumulative times are:

      1: x
      2: 2x
      3: 3x − b
      4: 4x − b
      5: 5x − 2b
      6: 6x − 2b
      7: 7x − 2b
      8: 8x − 3b
      9: 9x − 3b
      10: 10x − 4b

      R’s laps are (slow, fast) ×5 , so his cumulative times are:

      1: x − a
      2: 2x − a − c
      3: 3x − 2a − c
      4: 4x − 2a − 2c
      5: 5x − 3a − 2c
      6: 6x − 3a − 3c
      7: 7x − 4a − 3c
      8: 8x − 4a − 4c
      9: 9x − 5a − 4c
      10: 10x − 5a − 5c

      We can then calculate the time advantage R has over P at the end of each lap (= P’s time − R’s time):

      1: a
      2: a + c
      3: 2a − b + c
      4: 2a − b + 2c
      5: 3a − 2b + 2c
      6: 3a − 2b + 3c
      7: 4a − 2b + 3c
      8: 4a − 3b + 4c
      9: 5a − 3b + 4c
      10: 5a − 4b + 5c

      And we have 3 constraints on the values a, b, c.

      [1] P’s time advantage after 6 laps is twice the advantage after 10 laps:
      [2] One of the advantages has a value of −1
      [3] And another one has a value of 0.

      The equations can then be solved manually or programatically.

      This Python program chooses laps for the −1 and 0 seconds advantages, and then solves the 3 equations to find positive values for a, b, c.

      We then check P has a positive advantage on 8 of the laps, and this gives the result.

      This Python program runs in 62ms. (The internal run time is 5ms).

      Run: [ @replit ]

      from enigma import (Matrix, subsets, dot, printf)

# R's time advantage at the end of each lap
adv = {
   #   a   b  c
   1: (1,  0, 0),
   2: (1,  0, 1),
   3: (2, -1, 1),
   4: (2, -1, 2),
   5: (3, -2, 2),
   6: (3, -2, 3),
   7: (4, -2, 3),
   8: (4, -3, 4),
   9: (5, -3, 4),
  10: (5, -4, 5),
}

ks = sorted(adv.keys())

# choose laps to have an advantage of -1 and 0
for (a0, a1) in subsets(adv.keys(), size=2, select="P"):
  # adv 0 is not in lap 1 or lap 10
  if a0 in {1, 10}: continue

  # construct the equations
  eqs = [
    # adv[6] = 2 * adv[10]
    (tuple(x - 2 * y for (x, y) in zip(adv[6], adv[10])), 0),
    # adv[a0] = 0
    (adv[a0], 0),
    # adv[a1] = -1
    (adv[a1], -1),
  ]

  # and solve them
  try:
    (a, b, c) = Matrix.linear(eqs)
  except ValueError:
    continue

  # we are interested in positive a, b, c
  if not (c > a > 0 and b > 0): continue

  # calculate the P's advantage in each lap
  advs = dict((k, dot((a, b, c), adv[k])) for k in ks)

  # there shoud be 8 laps where P has a positive advantage
  if sum(v > 0 for v in advs.values()) != 8: continue

  # output solution
  printf("[a={a} b={b} c={c}]")
  for k in ks:
    printf("[lap {k}: adv = {v}]", v=advs[k])
  printf("max adv = {m}; win margin = {w}", m=max(advs.values()), w=advs[10])
  printf()

      Solution: Robert’s greatest lead is 6 seconds. He won the race by 2 seconds.

      The time advantage (in seconds) for R on each lap is:

      1: +1
      2: +6
      3: 0
      4: +5
      5: −1
      6: +4
      7: +5
      8: +3
      9: +4
      10: +2

      Like

      • Frits's avatar

        Frits 1:01 pm on 25 May 2022 Permalink | Reply

        @Jim,

        Maybe you have coded it already but did you also prevent a draw immediately followed by a lead for Peter?

        Like

        • Jim Randell's avatar

          Jim Randell 1:14 pm on 25 May 2022 Permalink | Reply

          @Frits: I didn’t explicitly check for this, but it turns out it is not the case.

          In any case we know R must win the race, so that P must fall behind by the end of the race.

          Like

    • Frits's avatar

      Frits 8:33 am on 26 May 2022 Permalink | Reply

      More analysis.

       
from (6) = 2 * (10) we can deduce:

3a - 2b + 3c = 2 * (5a - 4b + 5c)

7a - 6b + 7b = 0 --> a + c = 6/7 b

1: a              -->   a
2: a + c          -->   6/7 b
3: 2a - b + c     -->   a - 1/7 b
4: 2a - b + 2c    -->   5/7 b 
5: 3a - 2b + 2c   -->   a - 2/7 b
6: 3a - 2b + 3c   -->   4/7 b
7: 4a - 2b + 3c   -->   a + 4/7 b
8: 4a - 3b + 4c   -->   3/7 b
9: 5a - 3b + 4c   -->   a + 3/7 b
10: 5a - 4b + 5c  -->   2/7 b

Only lap 3 and 5 can be nonpositive, so lap 3 must be 0 and lap 5 must be -1.
Difference between (5) and (3) is -1/7 b which must be equal to -1 --> b = 7.
So a = 1 and c = 5. The answers follow from substitution.

      Like

  • Unknown's avatar

    Jim Randell 10:28 am on 22 May 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 87: Inter-schools trophy 

    From The Sunday Times, 25th November 1962 [link]

    Annually in the Easter and summer terms from 1957 Ardington and Bradling competed in five matches at different sports. Points were given for win (6 each for cricket and football, 4 each for hockey, swimming and athletics), the points being shared equally in the case of a draw or tie. The total points score decides the annual winner of the Topp Cup.

    From 1957 to 1961 inclusive Ardington, won the cup three times and Bradling won it twice, but their grand totals of points were then equal. The winning margin decreased each year, from 12 points in 1957 to 2 points in 1961.

    In each of the sports there was [exactly] one draw or tie; the hockey being drawn in 1959. Bradling last won the cricket in 1958, a year in which they won the cup. Ardington have never won the swimming but have the better record at athletics (which they won in 1957).

    What were the results of all matches in the series?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser87]

     
    • Jim Randell's avatar

      Jim Randell 10:29 am on 22 May 2022 Permalink | Reply

      I made a MiniZinc model to solve this puzzle:

      %#! minizinc -a --solver chuffed --output-mode json

% results for A
% x[<year>, <event>] = 0 (loss) | 1 (draw) | 2 (win)
% <year> = 1 (1957) .. 5 (1961)
% <event> = 1 .. 5 (C, F, H, S, A)
array [1..5, 1..5] of var 0..2: x;

% points for each year
function var int: ptsA(var int: i) = 3 * (x[i, 1] + x[i, 2]) + 2 * (x[i, 3] + x[i, 4] + x[i, 5]);
function var int: ptsB(var int: i) = 24 - ptsA(i);

% cumulative points
function var int: cumA(var int: y) = sum (i in 1..y) (ptsA(i));
function var int: cumB(var int: y) = sum (i in 1..y) (ptsB(i));

% A won the cup 3 times, B won the cup twice
constraint sum (i in 1..5) (ptsA(i) > ptsB(i)) = 3;
constraint sum (i in 1..5) (ptsB(i) > ptsA(i)) = 2;

% final cumulative total is equal
constraint cumA(5) = cumB(5);

% winning margin decreased each year ...
constraint forall (i in 1..4) (abs(ptsA(i) - ptsB(i)) > abs(ptsA(i + 1) - ptsB(i + 1)));
% ... from 12 points in 1957 ...
constraint abs(ptsA(1) - ptsB(1)) = 12;
% ... to 2 points in 1961
constraint abs(ptsA(5) - ptsB(5)) = 2;

% each sport has exactly one tie
constraint forall (j in 1..5) (sum (i in 1..5) (x[i, j] = 1) = 1);

% H was drawn in 1959
constraint x[3, 3] = 1;

% B last won C in 1958
constraint x[2, 1] = 0;
constraint forall (i in 3..5) (x[i, 1] > 0);

% B won the cup in 1958
constraint ptsA(2) < ptsB(2);

% A have never won the swimming
constraint forall (i in 1..5) (x[i, 4] < 2);

% team A have a better record at event A
constraint sum (i in 1..5) (x[i, 5]) > 5;

% team A won event A in 1957
constraint x[1, 5] = 2;

solve satisfy;

      And a Python wrapper to format the output (using the minizinc.py library):

      from enigma import join, printf
from minizinc import MiniZinc

for [x] in MiniZinc("teaser87.mzn").solve(result='x', use_shebang=1):
  printf("      C F H S A | pA pB | cA cB")
  cA = cB = 0
  for (y, vs) in enumerate(x, start=1957):
    # points for A, B
    pA = sum(x * y for (x, y) in zip(vs, [3, 3, 2, 2, 2]))
    pB = 24 - pA
    # cumulative totals
    cA += pA
    cB += pB
    # output the table row
    r = join(("BdA"[x] for x in vs), sep=" ")
    printf("{y}: {r} | {pA:2d} {pB:2d} | {cA:2d} {cB:2d}")
  printf()

      Solution: The full results are (d = drawn):

      1957: cricket = A, football = A, hockey = B, swimming = d, athletics = A; cup = A (18 – 6)
      1958: cricket = B, football = d, hockey = B, swimming = B, athletics = A; cup = B (17 – 7)
      1959: cricket = A, football = B, hockey = d, swimming = B, athletics = B; cup = B (16 – 8)
      1960: cricket = A, football = A, hockey = B, swimming = B, athletics = d; cup = A (14 – 10)
      1961: cricket = d, football = A, hockey = B, swimming = B, athletics = A; cup = A (13 – 11)

      At the end of the 5 years each team has a cumulative total of 60 points each.

      The winning margin for each year is: 12, 10, 8, 4, 2.

      Like

  • Unknown's avatar

    Jim Randell 4:32 pm on 20 May 2022 Permalink | Reply
    Tags: ,   

    Teaser 3113: The plumber’s buckets 

    From The Sunday Times, 22nd May 2022 [link] [link]

    A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. He calculated that he could exactly empty the tank, but only by using all three buckets and completely filling each bucket a different number of times.

    He filled and emptied each bucket the calculated number of times but the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

    What were the marked capacities of the three buckets?

    The version of this puzzle that appears in the book The Sunday Times Teasers Book 2 (2023) is as follows (with modified sections underlined):

    A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. He calculated that he could exactly empty the tank, but only by using all three buckets.

    He then emptied the tank as calculated, filling each bucket a different number of times, but then found the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

    What were the marked capacities of the three buckets?

    This corresponds to my own re-wording of the puzzle given in the comments.

    [teaser3113]

     
    • Jim Randell's avatar

      Jim Randell 4:51 pm on 20 May 2022 Permalink | Reply

      Perhaps I misread this puzzle, but I couldn’t find a solution that fits the text.

      However, I did find a solution where the dent reduces the capacity of the largest bucket (not the smallest) by 3 litres. This is my preferred way to “rescue” the puzzle, as it is a minimal change to the text, and the dent would be less noticeable in the largest bucket. However, another way to rescue the puzzle (but with a different solution) is if the capacity of the smallest bucket is reduced by 2 litres (not 3 litres).

      This Python program runs in 58ms.

      from enigma import (
  irange, subsets, express, seq_all_different as all_different,
  singleton, printf
)
 
# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # there is only one way to use the buckets
  qs = singleton(express(100, bs))
  if qs is None: continue
  # each bucket is used
  if 0 in qs: continue
  # the number of uses are all different
  if not all_different(qs): continue
  # largest [was: smallest] bucket must be used twice
  if qs[-1] != 2: continue
  printf("bs={bs} qs={qs}")

      Solution: The puzzle, as originally worded, has no solution.

      If we look for combinations of (correctly labelled) buckets that can be used (completely filling each bucket a number of times) to empty a 100 litre tank, such that all three buckets must be used, each of them a different number of times, we find there are 5 viable combinations (buckets × uses):

      (11, 18, 19) × (4, 1, 2)
      (12, 17, 18) × (1, 2, 3)
      (12, 17, 18) × (4, 2, 1)
      (13, 15, 19) × (1, 2, 3)
      (15, 18, 19) × (3, 2, 1)

      (And if we require there to be only a single way to use the buckets we can discard the (12, 17, 18) combination, leaving only 3 viable combinations).

      The original text asked for a combination where the smallest bucket was used twice, but as we see there are no such combinations.

      In my rescued version, where the largest bucket (not the smallest) has the dent, the solution is that the buckets are labelled (11, 18, 19) litres (although they are actually (11, 18, 16) litres).

      The published solution was that the buckets are labelled (13, 17, 19) litres (although they are actually (10, 17, 19) litres). Which corresponds to my re-wording of the puzzle given below.

      However we can use (correctly labelled) buckets (13, 17, 19) to empty the tank in the following ways:

      1× 13 + 4× 17 + 1× 19 = 100
      2× 13 + 1× 17 + 3× 19 = 100

      So it is not true to say that it can “only [be done] by using all three buckets and completely filling each bucket a different number of times”. (The first line achieves the required result using two of the buckets the same number of times). Hence the requirement for rewording of the puzzle.

      But if we suppose “the calculated number of times” requires that there is only one possible way to fill the buckets, then the reworded puzzle also has no solutions. (As there are 2 ways to use these (correctly labelled) buckets to empty the tank).

      It is possible that the setter intended that when the plumber sat down to work out how many times to use the buckets, he only considers using each bucket a different number of times. He tried using just one bucket and found it was not possible, then he tried using combinations of two buckets and found none of those were possible, and finally he tried using all three buckets and found that there was a single way they could be used. And he then proceeded to use this calculated number of ways, but when he finished there was 6 litres remaining in the tank, because the smallest bucket’s capacity was reduced by 3 litres from the labelled capacity.

      In this scenario, there are 9 candidate bucket combinations, and only one of them has the smallest bucket having 2 uses, so this gives a unique solution, and it is the published solution.

      The published solution is: “13, 17 and 19 litres”.

      Like

      • Jim Randell's avatar

        Jim Randell 5:58 pm on 20 May 2022 Permalink | Reply

        This might be a stricter interpretation of the puzzle text, which finds a couple more candidate solutions. But still doesn’t find a solution that fits the text.

        Instead I have coded it to find the same solution I found above.

        There remains an issue as to whether “he filled and emptied each bucket the calculated number of times” is intended to imply that there is only a single way of filling the buckets (each a different non-zero number of times), or he chose one from multiple viable ways. Fortunately this does not change the answer to my “rescued” version of the puzzle.

        This Python program runs in 56ms. (Internal run time is 1.5ms).

        from enigma import (irange, subsets, express, seq_all_different as all_different, printf)

# find viable ways to use the buckets
def buckets(t, bs):
  rs = list()
  for qs in express(t, bs):
    # each bucket is used
    if 0 in qs: return []
    # the numbers of uses are all different
    if not all_different(qs): return []
    # is viable
    rs.append(qs)
  return rs

# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # find viable ways to use the buckets
  for qs in buckets(100, bs):
    # largest [was: smallest] bucket must be used twice
    if qs[-1] != 2: continue
    # output solution
    printf("bs={bs} qs={qs}")

        The interpretation of the puzzle text where there is just a single way to fill the buckets can be implemented at line 13 by only returning the list of candidates if it has a length of 1. But this doesn’t change the answer found.

        Like

      • Frits's avatar

        Frits 5:59 pm on 20 May 2022 Permalink | Reply

        Correct, with SubstitutedExpression I end up with 3 options (the third solution would be if the capacity of the smallest bucket is reduced by 1.5 litres).

        Like

      • Jim Randell's avatar

        Jim Randell 8:26 am on 21 May 2022 Permalink | Reply

        It has been suggested to me that the intended interpretation of this puzzle is more like this (with {{ changed sections }} in double braces):

        A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. {{ He calculated that by completely filling each bucket a number of times, he could exactly empty the tank, but only by using all three buckets. }}

        He filled and emptied each bucket the calculated number of times, {{ each bucket being used a different number of times. But when he finished }} the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

        What were the marked capacities of the three buckets?

        To solve this formulation of the puzzle we can take my program and just move the “different number of times” test (line 10 in the program above is moved to line 18 below):

        from enigma import (irange, subsets, express, seq_all_different as all_different, printf)

# find viable ways to use the buckets
def buckets(t, bs):
  rs = list()
  for qs in express(t, bs):
    # each bucket is used
    if 0 in qs: return []
    # is viable
    rs.append(qs)
  return rs

# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # find viable ways to use the buckets
  for qs in buckets(100, bs):
    # the numbers of uses are all different
    if not all_different(qs): continue
    # smallest bucket must be used twice
    if qs[0] != 2: continue
    # output solution
    printf("bs={bs} qs={qs}")

        Like

      • Mark Valentine's avatar

        Mark Valentine 12:00 pm on 22 May 2022 Permalink | Reply

        I think the text is absolutely fine. Clearly you need three different bucket sizes, where no two (or one) of which can combine to make exactly 100. Then from these triples you apply the condition for the smallest bucket size.

        Like

        • Jim Randell's avatar

          Jim Randell 12:27 pm on 22 May 2022 Permalink | Reply

          @Mark: You also need to check that the numbers of uses of each bucket are all different. And where this requirement is placed in the puzzle text makes a difference.

          The original puzzle text has no solutions. My revised text does have a unique solution. (And it seems that this revised text corresponds to the intended puzzle).

          Like

          • Mark Valentine's avatar

            Mark Valentine 9:00 pm on 22 May 2022 Permalink | Reply

            Ok to be fair I didn’t check for uniqueness . Just stopped at a solution. so will defer.

            Like

    • Hugh+Casement's avatar

      Hugh+Casement 9:47 am on 21 May 2022 Permalink | Reply

      I don’t see that changing the passages in double braces makes any difference!

      Does the clue lie in “but only by using all three buckets” ?
      That is to say, no (different) integer multiples of any two undented buckets would sum to 100 litres.

      Like

      • Jim Randell's avatar

        Jim Randell 10:03 am on 21 May 2022 Permalink | Reply

        There is a subtle difference between “but only using all three buckets” and “but only using all three buckets, each a different number of times” that stops the puzzle from working in the originally published formulation.

        The “using all three buckets” requirement means we can’t use buckets with capacity 10 or 20, as then we could exactly empty the tank using just one of them. Similarly if a collection of buckets includes a pair that can be used to exactly empty the tank then that is also disallowed.

        Like

        • Hugh+Casement's avatar

          Hugh+Casement 12:23 pm on 21 May 2022 Permalink | Reply

          Yes, but he used the buckets the calculated number of times.

          Like

    • J Slusar's avatar

      J Slusar 6:55 pm on 21 May 2022 Permalink | Reply

      But what is wrong with buckets marked 13, 14 and 15 filling the smallest twice, the middle one once and the larger one 4 times? The total would have been 100, but the reduced capacity of the smaller bucket would mean 6 litres remained in the tank?

      Like

      • Jim Randell's avatar

        Jim Randell 10:01 pm on 21 May 2022 Permalink | Reply

        Thanks for the comment.

        I think this combination is ruled out by the requirement that “he could exactly empty the tank, but only by using all three buckets and completely filling each bucket a different number of times”.

        With (13, 14, 15) there are three ways we can make 100:

        100 = 0×13 + 5×14 + 2×15
        100 = 1×13 + 3×14 + 3×15
        100 = 2×13 + 1×14 + 4×15

        The first of these means that you don’t have to use all three buckets, and the second means that you don’t have to use each bucket a different number of times. So the requirement is not met.

        Like

    • bencooperjamin's avatar

      bencooperjamin 1:46 am on 23 May 2022 Permalink | Reply

      Doesnt work because 5*14 +2*15=100 ie the tank can be emptied with only 2 of the buckets.

      Like

    • GeoffR's avatar

      GeoffR 12:34 pm on 23 May 2022 Permalink | Reply

      I finally managed to find a program solution, which agrees with Jim’s last posting i.e 3rd posting (21 May 2022).

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

int: Tank == 100;   % litres

% Three buckets - capacity ranges in litres
var 10..20:B1; var 10..20:B2; var 10..20:B3; 

% Three different size buckets are required
constraint B1 < B2 /\ B2 < B3;

% No of times buckets B1, B2 and B3 are emptied
var 1..10:n1;  var 1..10:n2;  var 1..10:n3; 

constraint all_different([n1, n2, n3]);

% Smallest bucket B1 must be emptied twice due to a 3L dent
constraint n1 == 2;

% Tank emptying constraints for one and two buckets
% Tank cannot be emptied with any single bucket
constraint forall(i in 1..10) ( Tank mod (B1 * i) != 0 );
constraint forall(i in 1..10) ( Tank mod (B2 * i) != 0 );
constraint forall(i in 1..10) ( Tank mod (B3 * i) != 0 );

% Buckets B1 and B2 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B1 + j * B2) != 0);

% Buckets B1 and B3 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B1 + j * B3) != 0);
      
% Buckets B2 and B3 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B2 + j * B3) != 0);

% Empty the tank with three buckets B1, B2 and B3
constraint Tank mod (n1 * B1 + n2 * B2 + n3 * B3) == 0;

solve satisfy;

output [" Capacities of three buckets (B1, B2, B3) = " 
++ show([B1, B2, B3 ] )
++ "\n" ++ " No of times each bucket emptied (n1, n2, n3) = "
 ++ show([n1, n2, n3 ]) ];

      Like

    • Frits's avatar

      Frits 10:39 am on 25 May 2022 Permalink | Reply

      To simplify restraints you can use:

         
constraint forall(i in 0..10, j in 0..10, k in 0..10) (
i * B1 + j * B2 + k * B3 != Tank \/ i * j * k > 0);

      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