Recent Updates Page 32 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 11:55 am on 26 June 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 101: Midsummer birthday madness 

    From The Sunday Times, 3rd March 1963 [link]

    Midsummer Day, 1962 (June 24) was my youngest grandson John’s first birthday, and I was then able to claim that my nine grandchildren were aged 0, 1, 2, 3, 4, 5, 6, 7, and 8 years old (neglecting, of course, the odd days). They were all born in June, and if they are arranged in birthday order through the month the following facts are true:

    John is the middle grandchild;

    The sum of the dates of the last four is an exact multiple of the sum of the dates of the first four;

    The sum of the ages of the last four is two-thirds of the sum of the ages of the first four;

    The sum of the years of birth of the first three is equal to the sum of the years of birth of the last three;

    The intervals between birthdays are 0, 1, 2, 3, 4, 5, 6, and 7 days, but not in that order;

    Also:

    My eldest son’s two daughters are exactly two years apart;

    The twins were born four hours apart;

    Two children are as old as their dates of birth.

    What was the date of birth of the grandchild born in 1954?

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

    There are now 700 Teaser puzzles available on the site.

    [teaser101]

     
    • Jim Randell's avatar

      Jim Randell 11:56 am on 26 June 2022 Permalink | Reply

      The ages are all different, so the twins must be born either side of midnight on the 24th, so John is one of the twins, and the other must have a birthday of the 25th. John is the youngest grandson, so his (younger) twin must be a girl.

      This Python program starts with the 24th in the middle of the order, and then chooses an ordering for the intervals to give the remaining dates. It then assigns the ages, and checks all the required conditions apply.

      It runs in 161ms.

      Run: [ @replit ]

      from enigma import (subsets, div, printf)
      
      # the middle birthday is on the 24th, and the separation between
      # birthdays is (0, 1, 2, 3, 4, 5, 6, 7), in some order
      for ss in subsets((0, 1, 2, 3, 4, 5, 6, 7), size=len, select="P"):
        # construct the dates
        d5 = 24
        (d4, d6) = (d5 - ss[3], d5 + ss[4])
        (d3, d7) = (d4 - ss[2], d6 + ss[5])
        (d2, d8) = (d3 - ss[1], d7 + ss[6])
        (d1, d9) = (d2 - ss[0], d8 + ss[7])
        if d1 < 1 or d9 > 30: continue
        ds = [ d1, d2, d3, d4, d5, d6, d7, d8, d9]
      
        # John's twin must be born on the 25th
        if 25 not in ds: continue
      
        # sum of the dates of the last 4 is an exact multiple of the sum of
        # the dates of the first four
        x = div(sum(ds[-4:]), sum(ds[:4]))
        if x is None or x < 2: continue
      
        # choose values for the ages (John is 1)
        for ns in subsets((0, 2, 3, 4, 5, 6, 7, 8), size=len, select="P", fn=list):
          # insert 1
          ns.insert(4, 1)
      
          # John's twin (age 0) was born on the 25th
          if ds[ns.index(0)] != 25: continue
      
          # the sum of the ages of the last four is 2/3 the sum of the ages
          # of the first four
          if 3 * sum(ns[-4:]) != 2 * sum(ns[:4]): continue
      
          # [exactly] 2 ages are the same as the date
          if sum(x == y for (x, y) in zip(ds, ns)) != 2: continue
      
          # the sum of the years of birth of the first three is the same as
          # the sum of the years of birth of the last three
          ys = list(1962 - x for x in ns[:5]) + list(1961 - x for x in ns[5:])
          if sum(ys[:3]) != sum(ys[-3:]): continue
      
          # find the 2 grandchildren that share a birthday
          i = ss.index(0)
          # neither can be John
          if i == 3 or i == 4: continue
          # the ages must differ by 2
          if abs(ns[i] - ns[i + 1]) != 2: continue
      
          # output solution
          for (d, n, y) in zip(ds, ns, ys):
            printf("{d:02d} June {y} -> age = {n}{s}", s=(' [*** SOLUTION ***]' if y == 1954 else ''))
          printf()
      

      Solution: The birthday of the grandchild born in 1954 is 11th June.

      The dates of birth and ages are:

      02 June 1960 → age = 2 (age 2 on the 2nd)
      07 June 1955 → age = 7 (age 7 on the 7th)
      11 June 1954 → age = 8 (answer)
      17 June 1958 → age = 4
      24 June 1961 → age = 1 (today, John’s birthday)
      25 June 1961 → age = 0 (John’s twin sister)
      28 June 1958 → ages = 3 & 5 (two granddaughters, exactly 2 years apart)
      30 June 1955 → age = 6

      The program prints two solutions because the granddaughters born on 28th June could appear in either order.

      Like

    • Frits's avatar

      Frits 3:09 pm on 29 June 2022 Permalink | Reply

         
      # dates: A,  B,  C,  D,  E,  F,  G,  H,  I  in order
      # ages : R,  S,  T,  U,  V,  W,  X,  Y,  Z  not necessarily in order
      
      '''
      Notation: XYZ stands for X + Y + Z
      
      The ages are all different, so the twins must be born either side of 
      midnight on the 24th, so John is one of the twins, and the other must
      have a birthday of the 25th. John is the youngest grandson, 
      so his (younger) twin must be a girl.
      
      E = 24, F = 25, V = 1, zero age is either W or X 
      
      After F (25) we can only have intervals 0, 2 and 3 otherwise I exceeds 30
      so I has to be 30 
      A has to be equal to E (24) - intervals 4, 5, 6 and 7, so A = 2
      
      Two children are as old as their dates of birth
      so R = A and S = B
      
      The sum of the ages of the last four is two-thirds of the sum of the
      ages of the first four, sum of all ages is 36, John in the middle is 1
      so we have to split the remaining 35 into a 21 and 14. 
      
      The sum of the years of birth of the first three is equal to the sum of 
      the years of birth of the last three, RST must be equal to XYZ + 3.
      
      2 * RSTU = 3 * WXYZ ==> 2 * RST + 2 * U = 3 * W + 3 * RST - 9
      ==> ST = 2 * U - 3 * W + 7  (using R = 2)
      
      RSTUVWXYZ = 36 
      
      R    [     ST      ]       V       [    XYZ      ]   
      2 +  2 * U - 3 * W + 7 + U + 1 + W + 2 * U - 3 * W + 6 = 36
      5 * (U - W) = 20 ==> U = W + 4
      (U, W) is (4, 0), (7, 3) or (8, 4)
      
      If W is not zero:
        X must be zero leaving (U, W) to be (7, 3) or (8, 4).
        Two daughters with same birthday are exactly two years apart.
        These must be Y and Z (not W as V is male and Y can't be 2)
        W + Y + Z = 14. if W is odd than Y and Z can't be two years apart.
        This leaves W = 4 and Y + Z = 10, only two years apart option for Y and Z
        is 4 and 6. This is impossible as W already is 4. So W = 0 and U = 4.
      '''
      
      # dates: 2,  B,  C,  D, 24, 25,  G,  H, 30  in order
      # ages : 2,  S,  T,  4,  1,  0,  X,  Y,  Z  not necessarily in order
      
      '''
      In order to have after F the intervals 2 and 3 either G or H must be 27 or 28
      so 109 <= FGHI <= 115.
      In order to have intervals 4, 5, 6, 7 we have 36 <= ABCD <= 46
      (using 2, 6, 11, 17 resp. 2, 9, 15, 20 for A, B, C, D). 
      
      So FGHI = 3 * ABCD (using multiplier three) leaving only values 37 and 38
      for ABCD (with FGHI resp. 111 and 114) .
      Using (2, 8, C, D) for (A, B, C, D) we get at least a sum of 39
      then (A, B, C, D) is either (2, 6, C, D) or (2, 7, C, D).
      
      As U = 4 RST must be 17, ST = 15 so R and S must use 7 and 8 
      leaving 3, 5 and 6 for X, Y and Z.
      
      As S is 7 or 8 and B is either 6 or 7 we can deduce R = 7, B = 7, S = 8.
      
      Using (2, 7, 13, 17) for (A, B, C, D) we get at a sum of 39 so 
      (A, B, C, D) is (2, 7, 11, 17). 
      '''
      
      # dates: 2,  7, 11, 17, 24, 25,  G,  H, 30  in order
      # ages : 2,  7,  8,  4,  1,  0,  X,  Y,  Z  not necessarily in order
      
      '''
      As a grandchild born in 1954 can only occur with age 8 and date before 25
      or age 7 and date after 24 we see the answer is 11th June 1954.
      '''
      

      Like

  • 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

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