Design a site like this with WordPress.com
Get started

Updates from July, 2020 Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:28 pm on 31 July 2020 Permalink | Reply
    Tags: by: Bill Scott   

    Teaser 3019: William’s prime 

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

    William was searching for a number he could call his own. By consistently replacing digits with letters, he found a number represented by his name: WILLIAM.

    He noticed that he could break WILLIAM down into three smaller numbers represented by WILL, I and AM, where WILL and AM are prime numbers.

    He then calculated the product of the three numbers WILL, I and AM.

    If I told you how many digits there are in the product, you would be able to determine the number represented by WILLIAM.

    What number is represented by WILLIAM?

    [teaser3019]

     
    • Jim Randell 4:40 pm on 31 July 2020 Permalink | Reply

      We can use the [[ SubstitutedExpresison() ]] solver to solve the alphametic problem, and [[ filter_unique() ]] function to collect the answer (both from the enigma.py library).

      This Python program runs in 71ms.

      Run: [ @repl.it ]

      from enigma import SubstitutedExpression, filter_unique, nsplit, unpack, printf
      
      # the alphametic problem
      p = SubstitutedExpression(
        [ "is_prime(WILL)", "is_prime(AM)" ],
        answer="(WILLIAM, WILL * I * AM)",
        verbose=0,
      )
      
      # find results unique by the length of the product in the answer
      (rs, _) = filter_unique(
        (ans for (_, ans) in p.solve()),
        unpack(lambda w, p: len(nsplit(p))),
      )
      
      # output solution
      for (w, p) in rs:
        printf("WILLIAM = {w} [product = {p}]")
      

      Solution: WILLIAM = 4177123.

      If the value of I is unconstrained there are 579 solutions to the alphametic puzzle. (If we don’t allow I to be prime this number is reduced to 369 solutions, but the answer to the puzzle remains unchanged).

      114 give a 1-digit product (when I is 0), 221 give a 7-digit product, 243 give a 6-digit product, and 1 solution gives a 5-digit product, so this gives us the answer to the problem.

      As suggested by the puzzle’s title, 4177123 is prime.


      Using the recently added [[ accumulate ]] parameter for the [[ SubstitutedExpression() ]] solver in the enigma.py library (and the even more recently added annotated return value from [[ filter_unique() ]]), we can write a run-file that solves this puzzle:

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      "is_prime(WILL)"
      "is_prime(AM)"
      #"not is_prime(I)" # [optional] can require I is not prime
      
      --answer="(WILLIAM, WILL * I * AM)"
      
      # find answers that are unique by the number of digits in the product
      --code="unique = lambda s: filter_unique(s, unpack(lambda w, p: ndigits(p))).unique"
      --accumulate="unique"
      --verbose=16
      

      Like

    • GeoffR 8:53 am on 4 August 2020 Permalink | Reply

      I found I had to test for the three constraints individually (for the three constraints following this line) by remmimg out two of the three constraints to test the other constraint. Using all the constraints together gave multiple solutions.
      i.e.
      % Three tests for product – if 5, 6 or 7 digits long

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      var 1..9:W; var 1..9:I; var 1..9:L; 
      var 1..9:A; var 1..9:M;
      
      constraint all_different([W, I, L, A, M]);
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      var 1000..9999: WILL = 1000*W + 100*I + 11*L;
      
      var 10..99: AM = 10*A + M;
      
      var 1000000..9999999: WILLIAM = 1000000*W + 100000*I + 10000*L 
      + 1000*L + 100*I + 10*A + M;
      
      constraint is_prime(AM) /\ is_prime(WILL);
      
      % find min and max range of product WILL * I * AM
      % minimum value of product = 2133 * 1 * 45 = 95,985 
      % maximum value of product = 9877 * 8 * 65 = 5,136,040 
      % so product (WILL * I * AM) is either 5, 6 or 7 digits long
      
      var 95985..5136040: prod = WILL * I * AM; 
      
      % Three tests for product - if 5, 6 or 7 digits long 
      constraint (95985 < prod  /\ prod < 100000);    % 5 digits
      %constraint (100000 < prod /\ prod < 999999);   % 6 digits     
      %constraint (1000000 < prod /\ prod < 5136040); % 7 digits 
      
      solve satisfy;
      
      output["WILLIAM = " ++ show(WILLIAM) ++ 
      ", product = " ++ show(prod) ];
      
      

      This is a part manual / part programme solution, but it does get the answer – but it is not an ideal programme solution.

      @Jim: Do you think there could be a better fix in MiniZinc to get a full programme solution?
      Unfortunately we don’t seem to have the len(str(int)) fix in MiniZinc.

      Like

      • Jim Randell 11:53 am on 4 August 2020 Permalink | Reply

        @Geoff: MiniZinc does have log10(), which can be used to determine the number of digits in a number.

        But I would probably have MiniZinc generate all the solutions to the alphametic, and then use Python to analyse the output.

        Like

    • Frits 12:03 am on 6 August 2020 Permalink | Reply

      Same as Jim’s but for me easier to understand.
      Ideal would be a kind of HAVING clause in the SubstitutedExpression
      (something like HAVING COUNT(len(nsplit(WILL * I * AM)) == 1).

      from enigma import SubstitutedExpression, nsplit, printf
        
      # the alphametic problem
      p = SubstitutedExpression(
        [ 
         "is_prime(WILL)", "is_prime(AM)",
        ],
        answer="(len(nsplit(WILL * I * AM)), WILLIAM, WILL * I * AM)",
        verbose=0,
      )
      
      # collect all answers and maintain frequency 
      answs = []
      mltpl = {} 
      for (_, ans) in p.solve(verbose=0): 
          answs.append(ans)
          mltpl[ans[0]] = ans[0] in mltpl
      
      # only print answers with a unique first element
      for (ans) in answs:
          if not mltpl[ans[0]]:  
              printf("WILLIAM = {ans[1]}, WILL * I * AM = {ans[2]}")
      

      Like

    • Frits 3:19 pm on 6 August 2020 Permalink | Reply

      prms = {2, 3, 5, 7}
      # P1 = AM primes
      P1 = {x for x in range(13, 97, 2) if all(x % p for p in prms)} 
      
      prms = {2, 3, 5, 7, 11} | P1
      # P2 = WILL primes, exclude primes WXYZ where Y!=Z and where X = 0
      P2 = {x for x in range(1001, 9999, 2) if all(x % m for m in prms)
              and str(x)[-1] == str(x)[-2] and str(x)[1] != '0'}
                 
      
      answs = {}
      mltpl = {} 
      for p2 in P2:
          I = str(p2)[1]
          # WIL digits have to be different
          if len(list(set(str(p2)[0:3]))) < 3: continue
          for p1 in P1:
              # WILAM digits have to be different
              if len(list(set(str(p1)+str(p2)[0:3]))) < 5: continue
              prodlen = len(str(p2 * int(I) * p1))
              mltpl[prodlen] = prodlen in mltpl
              # store first prodlen entry
              if not mltpl[prodlen] : 
                 answs[prodlen] = str(p2) +" " + I + " " + str(p1)
      
      print("WILL I AM")
      for ans in answs:
          # only print answers with a unique product length
          if not mltpl[ans]:  
              print(answs[ans])
       

      Like

    • GeoffR 11:05 pm on 2 December 2020 Permalink | Reply

      from collections import defaultdict
      from itertools import permutations
      from enigma import is_prime
      
      D = defaultdict(list)
      
      for P in permutations('123456789', 5):
          w, i, l, a, m = P
          will, am = int(w + i + l + l), int(a + m)
          if not is_prime(will) or not is_prime(am):
              continue
          i = int(i)
          product = str(will * i * am)
          D[len(product)] += [(will, i, am)]
      
      for k, v in D.items():
          # there must be a unique number of digits in the product
          if len(v) == 1:
              will, i, am = v[0][0], v[0][1], v[0][2]
              william = 1000 * will + 100 * i + am
              print(f"WILLIAM = {william}")
      
      # WILLIAM = 4177123
      
      
      

      Like

  • Jim Randell 4:59 pm on 24 July 2020 Permalink | Reply
    Tags:   

    Teaser 3018: Debased 

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

    Sarah writes down a four-digit number then multiplies it by four and writes down the resultant five-digit number. She challenges her sister Jenny to identify anything that is special about these numbers. Jenny is up to the challenge as she identifies two things that are special. She sees that as well as both numbers being perfect squares she also recognises that if the five-digit number was treated as being to base 7 it would, if converted to a base 10 number, be the same as the original four-digit number.

    What is the four-digit number?

    [teaser3018]

     
    • Jim Randell 5:08 pm on 24 July 2020 Permalink | Reply

      It is straightforward to implement this directly.

      The following Python program runs in 52ms.

      Run: [ @repl.it ]

      from enigma import powers, int2base, printf
      
      # consider 4-digit squares, where 4n is a 5-digit number
      for n in powers(50, 99, 2):
        # what is n in base 7?
        n7 = int2base(n, base=7)
        # which if interpreted in base 10 is 4n
        if int2base(4 * n) == n7:
          printf("n={n} [= {n7} (base 7)]")
      

      Solution: The four digit number is: 2601.

      2601 = 51², so the answer is found on the second number tested by the program.

      4×2601 = 10404, and 10404 (base 7) = 2601 (base 10).

      Or, as a single Python expression:

      >>> peek(n for n in powers(50, 99, 2) if int2base(n, base=7) == int2base(4 * n))
      2601
      

      Like

      • Jim Randell 4:40 pm on 30 July 2020 Permalink | Reply

        Or, using the [[ SubstitutedExpression() ]] solver from the enigma.py library:

        #!/usr/bin/env python -m enigma -r
        
        SubstitutedExpression
        
        --answer="ABCD"
        --distinct=""
        
        # the 4-digit number is ABCD, and it is a square
        "is_square(ABCD)"
        
        # multiplied by 4 gives a 5 digit number
        "9999 < 4 * ABCD"
        
        # interpreting 4 * ABCD as a base 7 number gives ABCD
        "int2base(ABCD, base=7) == int2base(4 * ABCD, base=10)"
        

        Like

    • GeoffR 7:54 am on 26 July 2020 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
       
      % digits for 4 digit number to base 10
      var 1..9:A; var 0..9:B; var 0..9:C; var 0..9:D; 
      var 1000..9999: ABCD = 1000*A + 100*B + 10*C + D;
      
      % digits for 5 digit number in base 7
      var 1..6:E; var 0..6:F; var 0..6:G; var 0..6:H; var 0..6:I;
      var 10000..99999: EFGHI = 10000*E + 1000*F + 100*G + 10*H + I;
      
      predicate is_sq(var int: y) =
        let {
           var 1..ceil(sqrt(int2float(ub(y)))): z
        } in
         z*z = y;
      
      % 5-digit number is four times the 4-digit number
      constraint 4 * ABCD == EFGHI;
      
      % Both 4-digit and 5-digit numbers are squares
      constraint is_sq(ABCD) /\ is_sq(EFGHI);
      
      % ABCD (base 10) = EFGHI (base 7)
      constraint ABCD == I + 7*H + 7*7*G + 7*7*7*F  + 7*7*7*7*E;
      
      solve satisfy;
      
      output [ "Four digit number (base 10) is " ++ show(ABCD) 
      ++ "\nFive digit number (base 7) is "++ show(EFGHI) ]; 
      
      

      Like

    • GeoffR 8:20 pm on 27 July 2020 Permalink | Reply

      
      from enigma import is_square, nsplit
      
      for n in range(50,100):
        if is_square(n*n):
          N4 = n*n      # 4-digit number (base 10)
          N5 = 4*n*n    # 5-digit number (base 7)
          
          # split 5-digit number N5 into digits
          a, b, c, d, e = nsplit(N5)
          
          # check N4 = N5 in specified bases
          if N4 == e + d*7 + c*7**2 + b*7**3 + a*7**4:
            print(f"4-digit number(base 10)= {n**2}")
            print(f"5-digit number(base 7)= {4*n**2}")
      
      
      

      Like

    • GeoffR 8:07 am on 28 July 2020 Permalink | Reply

      I have updated my programme to include a check that the digits (7,8,9) are not included in the 5-digit number before it is converted to base 7. In practice, the answer is found very early.

      
      from enigma import is_square, nsplit
      
      for n in range(50, 100):
        if is_square(n * n):
          N4 = n * n      # 4-digit number (base 10)
          N5 = 4 * n * n    # 5-digit number (base 7)
      
          # split 5-digit number N5 into digits
          a, b, c, d, e = nsplit(N5)
      
          # check digits 7,8,9 are not in N5, base 7
          if any(x in (a,b,c,d,e) for x in (7,8,9)):
            continue
          
          # check N4 = N5 in specified bases
          if N4 == e + d*7 + c*7**2 + b*7**3 + a*7**4:
            print(f"4-digit number(base 10)= {n**2}")
            print(f"5-digit number(base 7)= {4*n**2}")
      
      
      

      Like

      • Jim Randell 2:53 pm on 29 July 2020 Permalink | Reply

        @GeoffR: That’s why in my code I interpret a base 7 representation as base 10. There is no need to check for invalid digits, as every base 7 digit is a valid base 10 digit.

        Like

  • Jim Randell 4:30 pm on 17 July 2020 Permalink | Reply
    Tags:   

    Teaser 3017: Mr. Green’s scalene mean machine 

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

    My maths teacher, Mr. Green, stated that the average of the squares of any two different odd numbers gives the hypotenuse of a right-angled triangle that can have whole-number unequal sides, and he told us how to work out those sides.

    I used my two sisters’ ages (different odd prime numbers) to work out such a triangle, then did the same with my two brothers’ ages (also different odd prime numbers). Curiously, both triangles had the same three-figure palindromic hypotenuse. However, just one of the triangles was very nearly a 45° right-angled triangle (having a relative difference between the adjacent side lengths of less than 2%).

    In ascending order, what were my siblings’ ages?

    [teaser3017]

     
    • Jim Randell 5:34 pm on 17 July 2020 Permalink | Reply

      We don’t need to work out how to calculate the non-hypotenuse sides of the triangle (although I have worked out a rule which works).

      This Python program groups together Pythagorean triples by the hypotenuse, then looks for groups that have a palindromic hypotenuse, and more than one corresponding triangle. It then works out pairs of odd squares that average to the hypotenuse, and looks for two of these pairs where each number in the pair is prime. Then we need to look for a corresponding triangle where the non-hypotenuse sides are almost equal. And that gives us our solution.

      This Python program runs in 55ms.

      Run: [ @repl.it ]

      from enigma import pythagorean_triples, is_palindrome, nsplit, group, unpack, isqrt, compare, subsets, flatten, is_prime, printf
      
      # generate decompositions of n into the sum of two squares
      def sum_of_squares(n):
        (i, j) = (isqrt(n), 0)
        while not(i < j):
          r = compare(i * i + j * j, n)
          if r == 0: yield (j, i)
          if r != -1: i -= 1
          if r != 1: j += 1
      
      # collect pythagorean triples grouped by hypotenuse
      tris = group(
        pythagorean_triples(999),
        st=unpack(lambda x, y, z: z > 99 and is_palindrome(nsplit(z))),
        by=unpack(lambda x, y, z: z)
      )
      
      # look for multiple triangles that share a palindromic hypotenuse
      for (z, xyzs) in tris.items():
        if not(len(xyzs) > 1): continue
        # and look for multiple pairs of squares that average to the hypotenuse
        avgs = list((x, y) for (x, y) in sum_of_squares(2 * z) if x < y)
        if not(len(avgs) > 1): continue
        printf("[{z} -> {xyzs} -> {avgs}]")
        # look for triangles with x, y within 2% of each other
        t45ish = list((x, y, z) for (x, y, z) in xyzs if 100 * y < 102 * x)
        if not(0 < len(t45ish) < len(xyzs)): continue
        # collect two of the pairs for the ages
        for ages in subsets(avgs, size=2):
          ages = sorted(flatten(ages))
          # and check they are odd primes
          if not all(x % 2 == 1 and is_prime(x) for x in ages): continue
          # output solution
          printf("z={z} -> t45ish = {t45ish} -> ages = {ages}")
      

      Solution: The ages are: 13, 17, 29, 31.

      Removing the test for the ages being odd and prime does not give any additional solutions.

      If the two odd numbers are a and b (where a < b), then the following is a Pythagorean triple:

      x = (b² − a²) / 2
      y = ab
      z = (a² + b²) / 2

      where z is the hypotenuse. (All we actually require is that a and b have the same parity).

      Applying this rule to the two pairs (13, 31) and (17, 29) we get the following triangles:

      (13, 31) → sides = (396, 403, 565); angles = (44.5°, 45.5°, 90.0°)
      (17, 29) → sides = (276, 493, 565); angles = (29.2°, 60.8°, 90.0°)

      The first of these triangles is close to being a (45°, 45°, 90°) triangle, and the other one is quite close to being a (30°, 60°, 90°) triangle – the standard shapes for set squares.

      Like

    • GeoffR 8:15 am on 21 July 2020 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      % Siblings ages in teaser
      var 2..97:S1; var 2..97:S2; var 2..97:B1; var 2..97:B2;
      constraint all_different ([S1, S2, B1, B2]);
      
      constraint S1 < S2 /\ B1 < B2;
      
      constraint is_prime(S1) /\ is_prime(S2)
      /\ is_prime(B1) /\ is_prime(B2);
      
      % Palindromic hypotenuse
      var 100..999: HYP;
      
      constraint HYP div 100 == HYP mod 10 
      /\ HYP div 10 mod 10 != HYP mod 10;
      
      % Two other sides with a palindromic hypotenuse
      var 100..999: side1; var 100..999: side2;
      
      constraint side1 > side2
      /\ all_different([HYP, side1, side2]);
      
      % Mr Green's triangle formula
      constraint B1*B1 + B2*B2 = 2 * HYP
      /\ S1*S1 + S2*S2 = 2 * HYP;
      
      % The triangle sides are less than 2% different in size
      constraint side1 * side1 + side2 * side2 == HYP * HYP
      /\ 100 * (side1 - side2) < 2 * side1;
      
      solve satisfy;
      
      output [ "Sisters' ages are " ++ show(S1) ++ ", " ++ show(S2)]
      ++ [ "\nBrothers' ages are " ++ show(B1) ++ ", " ++ show(B2)]
      ++ [ "\nTriangle solution sides are " ++ show(HYP) ++ ", " ++ show(side1)]
      ++ [", " ++ show(side2) ];
      
      % Ascending siblings ages are 13,17,29,31
      
      % Sisters' ages are 17, 29
      % Brothers' ages are 13, 31
      % Triangle solution sides are 565, 403, 396
      % time elapsed: 0.05 s
      % ----------
      % Sisters' ages are 13, 31
      % Brothers' ages are 17, 29
      % Triangle solution sides are 565, 403, 396
      % time elapsed: 0.05 s
      % ----------
      % ==========
      
      

      I found the prime age constraint of the siblings was not essential for this solution.

      Like

  • Jim Randell 5:14 pm on 3 July 2020 Permalink | Reply
    Tags:   

    Teaser 3015: Quid pro quo 

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

    In Readiland the unit of currency is the quid. Notes are available in two denominations and with these notes it is possible to make any three-figure number of quid. However, you need a mixture of the denominations to make exactly 100 quid. Furthermore, there is only one combination of denominations that will give a total of 230 quid.

    What are the two denominations?

    [teaser3015]

     
    • Jim Randell 5:32 pm on 3 July 2020 Permalink | Reply

      See also: Enigma 228, Enigma 1194, Enigma 1154.

      If we suppose the denominations are x and y (where gcd(x, y) = 1). Then the largest amount that cannot be made using the denominations is given by F(x, y) = xy − x − y.

      Both denominations are needed to make 100, so they must both be less than 100, and neither can be a divisor of 100.

      The following Python 3 program runs in 67ms.

      Run: [ @repl.it ]

      from enigma import coprime_pairs, express, printf
      
      # consider denominations x, y
      for (x, y) in coprime_pairs(97):
        if 100 % x == 0 or 100 % y == 0: continue
      
        # largest inexpressible amount is < 100
        if not(x * y - x - y < 100): continue
      
        # there is exactly 1 way to express 230
        e230s = list(express(230, (x, y)))
        if len(e230s) != 1: continue
      
        # output solution
        printf("x={x} y={y}; 100 -> {e100s}, 230 -> {e230s}", e100s=list(express(100, (x, y))))
      

      Solution: The two denominations are 3 quid and 49 quid.

      The largest amount that cannot be made using these denominations is 95 quid. All larger amounts are possible.

      The only way to make 100 quid is 17× 3 quid + 1× 49 quid.

      The only way to make 230 quid is 44× 3 quid + 2× 49 quid.


      Manually:

      The largest integer that is not expressible in k different ways using denominations x, y is given by:

      F[k](x, y) = kxy − x − y

      So we need to find co-prime values for x, y, less than 100 that are not divisors of 100, and the following hold:

      F[1](x, y) < 100
      F[2](x, y) ≥ 230

      This will ensure that all 3-digit amounts are expressible, and that to make 100 requires both denominations. All that remains for each pair of candidate denominations is to determine if there is a unique expression for 230.

      Given a value for x we can use the inequalities to find a range of viable values for y.

      Starting with x = 3, gives y = 47 .. 51 and only y = 47, 49 are co-prime with x.

      230 can be expressed in two ways using (3, 47): 230 = 14× 3 + 4× 47 = 61× 3 + 1× 47.

      230 can be expressed in only one way using (3, 49): 230 = 44× 3 + 2× 49.

      So (3, 49) is a viable solution.

      For x = 4, we get only y = 34, but x divides 100, so this is not a candidate solution.

      And for larger values of x there are no possibilities for y, so we are done.

      Like

  • Jim Randell 5:08 pm on 26 June 2020 Permalink | Reply
    Tags:   

    Teaser 3014: Family business 

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

    George and Martha run a company with their five daughters. The telephone extensions all have four positive unequal digits and strangely only four digits appear in the seven extensions:

    Andrea: ABCD
    Bertha: ACDB
    Caroline: BACD
    Dorothy: DABC
    Elizabeth: DBCA
    George: CABD
    Martha: CDAB

    They noticed the following:

    Andrea’s and Bertha’s add up to Dorothy’s.
    Bertha’s and Elizabeth’s add up to George’s.
    Caroline’s and Dorothy’s add up to Martha’s.

    What is Andrea’s extension?

    [teaser3014]

     
    • Jim Randell 5:14 pm on 26 June 2020 Permalink | Reply

      Any one of the expressions is sufficient to determine the answer.

      I used the [[ SubstitutedExpression() ]] solver from the enigma.py library to evaluate the alphametic expressions.

      The following run file executes in 96ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      --digits="1-9"
      
      "ABCD + ACDB = DABC"
      "ACDB + DBCA = CABD"
      "BACD + DABC = CDAB"
      
      --answer="ABCD"
      

      Solution: Andrea’s extension is 2385.


      Here’s my manual solution:

      We can split each of the three sums into columns to give us partial equations, that may have a carry out or a carry in.

      B + D = C appears at both the left- and right-hand side of a sum, so can’t have a carry in or a carry out, so it is a complete equation.

      We then see that the partial sum BC + CD = AB cannot have a carry in, so the sum A + B = D is also a complete equation.

      The sum A + A = D cannot have a carry out, and if it does not have a carry in then we deduce that B = A, which is not possible. So it does have a carry in, and B = A + 1 is a complete equation.

      Using these three complete equations we derive:

      B = A + 1
      D = 2A + 1
      C = 3A + 2

      For digits in the range 1-9 the only viable values are:

      A = 1, B = 2, C = 5, D = 3
      A = 2, B = 3, C = 8, D = 5

      Only one of these assignment works in the original three sums, so we have the answer.

      Or, we can use the partial equation BC + CD = AB, which we now know must have a carry out, to give a fourth complete equation: 9B + 11C + D = 10A + 100. We can then substitute in the other equations to get the value of A, and from that the remaining values:

      9B + 11C + D = 10A + 100
      9(A + 1) + 11(3A + 2) + (2A + 1) = 10A + 100
      44A + 32 = 10A + 100
      34A = 68
      A = 2, B = 3, C = 8, D = 5

      Like

    • GeoffR 9:19 am on 27 June 2020 Permalink | Reply

      I simulated a normal addition sum in MiniZinc for the first equation to find an answer.

      The values obtained confirmed the other two equations.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      % Using the first equation only ie Andrea + Bertha = Dorothy
      % 
      %  A B C D
      %  A C D B
      %  -------
      %  D A B C
      %  -------
      
      var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D;
      var 0..1:carry1; var 0..1:carry2; var 0..1:carry3; 
      
      constraint C == (B + D) mod 10 
      /\ carry1 = (B + D) div 10;
      
      constraint B = (carry1 + C + D) mod 10 /\ 
      carry2 = (carry1 + C + D) div 10;
      
      constraint A = (carry2 + B + C) mod 10
      /\ carry3 = (carry2 + B + C) div 10;
      
      constraint D = carry3 + 2*A;
      
      solve satisfy;
      
      output ["A,B,C,D = " ++ show([A,B,C,D]) ];
      
      
      

      Like

    • GeoffR 2:41 pm on 27 June 2020 Permalink | Reply

      A short Python programme confirms that the second and third equations give the same value for Andrea’s extension as my MiniZinc programme for the first equation:

      
      from itertools import permutations
      
      # Bertha’s and Elizabeth’s extensions add up to George’s extn.
      # 2nd Equation: ACDB + DBCA = CABD
      
      for p in permutations((1,2,3,4,5,6,7,8,9),4):
          a, b, c, d = p
          acdb = 1000*a + 100*c + 10*d + b
          dbca = 1000*d + 100*b + 10*c + a
          cabd = 1000*c + 100*a + 10*b + d
          if acdb + dbca == cabd:
              # Find Andrea's extension
              abcd = 1000*a + 100*b + 10*c + d
              print("2. Andrea's extension =", abcd)
      
      # Caroline’s and Dorothy’s extensions add up to Martha’s extn.
      # 3rd Equation : BACD + DABC = CDAB
      
      for p in permutations((1,2,3,4,5,6,7,8,9),4):
          a, b, c, d = p
          bacd = 1000*b + 100*a + 10*c + d
          dabc = 1000*d + 100*a + 10*b + c
          cdab = 1000*c + 100*d + 10*a + b
          if bacd + dabc == cdab:
              # Find Andrea's extension
              abcd = 1000*a + 100*b + 10*c + d
              print("3. Andrea's extension =", abcd)
      
      

      Like

  • Jim Randell 7:06 pm on 19 June 2020 Permalink | Reply
    Tags:   

    Teaser 3013: Arian Pen-blwydd 

    From The Sunday Times, 21st June 2020 [link]

    When I thought that my daughter was old enough to be responsible with money I gave her on her next, and all subsequent birthdays, cash amounts (in pounds) which were equal to her birthday age squared.

    On her last birthday her age was twice the number of years for which she received no such presents. I calculated at this birthday that if I had made these gifts on all of her birthdays then she would have received 15% more than she had actually received. I then decided that I would stop making the payments after her birthday when she would have received only 7.5% more if the payments had been made on all of her birthdays.

    What was the amount of the final birthday payment?

    There are now 300 puzzles available on the site.

    [teaser3013]

     
    • Jim Randell 9:43 pm on 19 June 2020 Permalink | Reply

      If she didn’t receive gifts for the first k years, then the “missing” gifts are the sum of the squares of 1 .. k. The amounts actually received are the sum of the squares of (k + 1) .. 2k.

      This Python program finds the value of k when the amount of the missing gifts is 15% of the actual amount, and then continues looking at future gifts until the amount becomes 7.5%.

      It runs in 53ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, printf
      
      # solve the puzzle
      def solve():
        # consider the k years before the gifts started
        for k in irange(1, inf):
          # total before amount
          before = sum(x * x for x in irange(1, k))
          # total after amount
          after = sum(x * x for x in irange(k + 1, 2 * k))
          # before = 0.15 * after
          if not(100 * before == 15 * after): continue
          printf("k = {k}; before = {before}, after = {after}")
      
          # now add in future gifts
          future = after
          for n in irange(2 * k + 1, inf):
            future += n * n
            # before = 0.075 * future
            if not(1000 * before == 75 * future): continue
            printf("-> n = {n}; n^2 = {n2}, future = {future}", n2=n * n)
            return
      
      solve()
      

      Solution: The final gift was £ 1,764.

      The gifts started on the 18th birthday, so the “missing” gifts (years 1 – 17) would amount to £ 1,785.

      The actual gifts between ages 18 and 34 amount to £ 11,900, and 15% of £ 11,900 is £ 1,785.

      The gifts are to continue to age 42, making the total amount £ 23,800, and 7.5% of £ 23,800 is also £ 1,785.

      Which means the final gift is made on the 25th (silver) anniversary of the first gift.


      Analytically:

      (See: Enigma 1086).

      The sum of the first n squares is given by the square pyramidal numbers:

      SP(n) = n (n + 1) (2n + 1) / 6

      So the first part of the puzzle is to solve:

      SP(k) = 0.15 (SP(2k) − SP(k))
      20 SP(k) = 3 (SP(2k) − SP(k))
      23 SP(k) = 3 SP(2k)
      23k (k + 1) (2k + 1) = 6k (2k + 1) (4k + 1)
      23k + 23 = 24k + 6
      k = 17

      The second part is to solve, for n > 34:

      SP(k) = 0.075 (SP(n) − SP(k))
      3 SP(n) = 43 SP(k)
      SP(n) = 25585
      n = 42

      The required answer is then: n² = 42² = 1764.

      Like

      • Jim Randell 11:19 pm on 20 June 2020 Permalink | Reply

        Or, more simply:

        We are looking for values of n, k where:

        SP(k) = (3/43) SP(n)
        SP(2k) = (23/43) SP(n)

        This Python program runs in 51ms.

        Run: [ @repl.it ]

        from enigma import irange, inf, div, printf
        
        # accumulate the square pyramidal numbers, map: SP[n] -> n
        d = dict()
        x = 0
        for n in irange(1, inf):
          # calculate: x = SP(n)
          x += n * n
          d[x] = n
          # can we find a corresponding y = SP(k)?
          y = div(x * 3, 43)
          k = d.get(y, None)
          if k is None: continue
          # and verify z = SP(2k)
          z = div(x * 23, 43)
          k2 = d.get(z, None)
          if k2 is None or k2 != k * 2: continue
          printf("n^2={n2} [n={n} k={k}; SP[{k}]={y} SP[{k2}]={z} SP[{n}]={x}]", n2=n * n)
          break
        

        Like

  • Jim Randell 4:48 pm on 12 June 2020 Permalink | Reply
    Tags:   

    Teaser 3012: Number blind rage 

    From The Sunday Times, 14th June 2020 [link]

    After school, angry at getting “50 lines”, I kicked my satchel around. Impacts made my 11-digit calculator switch on. An 11-digit number was also entered and the display was damaged. Strangely, I found “dYSCALCULIA” displayed and saved this to memory (as shown).

    After various tests I confirmed that all arithmetic operations were correct and the decimal point would appear correctly if needed. No segments were permanently “on”, two digits were undamaged, and for the other digits, overall, several segments were permanently “off”.

    Retrieving “dYSCALCULIA”, I divided it by 9, then the result by 8, then that result by 7, then that result by 6. No decimal point appeared and the last result (at the right-hand side of the display) had three digits appearing as numerals.

    What number was “dYSCALCULIA”?

    [teaser3012]

     
    • Jim Randell 9:07 pm on 12 June 2020 Permalink | Reply

      I used the standard set of digits (as illustrated in Enigma 1701).

      This Python program runs in 90ms.

      from itertools import product
      from enigma import join, div, printf
      
      # normal digits
      normal = "0123456789"
      
      # map digits to illuminated segments, arranged as:
      #
      #   0
      # 1   2
      #   3
      # 4   5
      #   6
      #
      # map digits to segments
      f = lambda *ss: frozenset(ss)
      seg = {
        # normal digits
        '0': f(0, 1, 2, 4, 5, 6),
        '1': f(2, 5),
        '2': f(0, 2, 3, 4, 6),
        '3': f(0, 2, 3, 5, 6),
        '4': f(1, 2, 3, 5),
        '5': f(0, 1, 3, 5, 6),
        '6': f(0, 1, 3, 4, 5, 6), # or could be (1, 3, 4, 5, 6)
        '7': f(0, 2, 5), # or could be (0, 1, 2, 5)
        '8': f(0, 1, 2, 3, 4, 5, 6),
        '9': f(0, 1, 2, 3, 5, 6), # or could be (0, 1, 2, 3, 5)
        # malformed digits
        'a': f(0, 1, 2, 3, 4, 5),
        'c': f(0, 1, 4, 6),
        'd': f(2, 3, 4, 5, 6),
        'l': f(1, 4, 6),
        'u': f(1, 2, 4, 5, 6),
      }
      # map segments to normal digits
      norm = dict((seg[k], k) for k in normal)
      
      # the display
      display = "d45calcul1a"
      
      # compute possible replacement (superset) digits for the symbols
      r = dict((k, list(d for d in normal if seg[d].issuperset(seg[k]))) for k in set(display))
      
      # choose possible replacement digits for the symbols
      for ds in product(*(r[x] for x in display)):
        if ds[0] == '0': continue
        # two of the digits are unaffected
        if sum(x == y and x in normal for (x, y) in zip(display, ds)) < 2: continue
        # make the number
        n = int(join(ds))
        # and the result
        s = div(n, 9 * 8 * 7 * 6)
        if s is None: continue
        # remove broken segments from the result
        # x = original display, y = original digit, z = result digit
        rs = list(
          norm.get(seg[z].difference(seg[y].difference(seg[x])), '?')
            for (x, y, z) in zip(display[::-1], ds[::-1], str(s)[::-1])
        )
        # there should be 3 normal digits
        if len(rs) - rs.count('?') != 3: continue
        # output solution
        printf("{n} -> {s} -> {rs}", rs=join(rs[::-1]))
      

      Solution: dYSCALCULIA = 84588800688.

      The digits displaying 4 and 5 must be the undamaged ones.

      So the segments that are definitely broken are as shown below:

      There are 22 segments that are definitely broken, and a further 3 that we cannot determine if they are broken or not.

      The result of dividing the number by 9×8×7×6 = 3024 is 27972487, which would look something like this:

      (Only showing the segments that we definitely know to be broken, there are two segments shown lit that may be broken).

      The 2nd digit (7) displays as a 7. The 7th digit (8) displays as a 1. The 8th digit (7) displays as a 7.

      Like

  • Jim Randell 5:14 pm on 5 June 2020 Permalink | Reply
    Tags:   

    Teaser 3011: Optical illusion 

    From The Sunday Times, 7th June 2020 [link]

    George and Martha are studying optics. If you place an object a specific distance from a lens, an image will appear at a distance from that lens according the following formula:

    The reciprocal of the object distance plus the reciprocal of the image distance is equal to the reciprocal of the focal length of the lens.

    The object distance was a two-digit whole number of cm (ab). The image distance and the focal length of the lens were also two-digit whole numbers (cd and ef respectively). The six digits were all different and non-zero. Also, the object distance and the focal length were of the same parity and b was an exact multiple of d. Martha pointed out that the sum of those three two-digit numbers was a prime number.

    What was that prime number?

    [teaser3011]

     
    • Jim Randell 5:27 pm on 5 June 2020 Permalink | Reply

      I used uppercase letters for the alphametic symbols, as that is more usual.

      We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library, to solve the relevant alphametic expressions. The following run file executes in 104ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      --digits="1-9"
      
      "fraction(1, AB, 1, CD) == (1, EF)"
      "B % 2 == F % 2"
      "div(B, D) > 1"
      "is_prime(AB + CD + EF)"
      
      --answer="AB + CD + EF"
      

      Solution: The sum of the numbers is 211.

      The object distance is 78 cm, the image distance is 91 cm and the focal length is 42 cm.

      (1 / 78) + (1 / 91) = (1 / 42)

      The optical constraint and multiple constraint (lines 12 and 14) are sufficient to arrive at a unique answer to the puzzle.


      However, if we remove the constraint that the symbols stand for different digits there is a further solution:

      (1 / 28) + (1 / 21) = (1 / 12)

      In this case the numbers sum to 61.

      Like

    • GeoffR 7:33 pm on 5 June 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9: a; var 1..9: b; var 1..9: c; 
      var 1..9: d; var 1..9: e; var 1..9: f;
      
      constraint all_different ([a, b, c, d, e, f]);
      
      var 10..99: ab = 10*a + b;  % object distance
      var 10..99: cd = 10*c + d;  % image distance
      var 10..99: ef = 10*e + f;  % focal length
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x)))))
       ((i < x) -> (x mod i > 0));
       
      % optical formula is  1/ab + 1/cd = 1/ef, so... 
      constraint (cd * ef) + (ab * ef) == (ab * cd);
      
      % parity is same for numbers ab and ef
      constraint ab mod 2 == ef mod 2;
      
      % b was an exact multiple of d
      constraint b div d > 1 /\ b mod d == 0;
      
      % sum of three two-digit numbers was a prime number
      constraint is_prime(ab + cd + ef);
      
      solve satisfy;
      
      output ["Prime number is " ++ show(ab + cd + ef) ++
      "\nab = " ++ show(ab) ++ ", cd = " ++ show(cd) ++ ", ef = " ++ show(ef)];
      
      
      

      Like

  • Jim Randell 9:44 pm on 29 May 2020 Permalink | Reply
    Tags:   

    Teaser 3010: Putting game 

    From The Sunday Times, 31st May 2020 [link]

    A putting game has a board with eight rectangular holes, like the example (not to scale), but with the holes in a different order.

    If you hit your ball (diameter 4cm) through a hole without touching the sides, you score the number of points above that hole. The sum of score and width (in cm) for each hole is 15; there are 2cm gaps between holes.

    I know that if I aim at a point on the board, then the ball’s centre will arrive at the board within 12cm of my point of aim, and is equally likely to arrive at any point in that range. Therefore, I aim at the one point that maximises my long-term average score. This point is the centre of a hole and my average score is a whole number.

    (a) Which hole do I aim at?

    (b) Which two holes are either side of it?

    [teaser3010]

     
    • Jim Randell 9:23 am on 30 May 2020 Permalink | Reply

      The 4cm diameter ball is not allowed to touch the sides of the hole, so we can consider the outside 2cm of each hole to be “out of bounds”. Which is the same as if the ball was a point, the gaps between holes are extended 2cm in each direction (so they become 6cm wide), and each hole is reduced by a corresponding 2cm on either edge.

      To be sure I satisfy all the conditions this Python program constructs all possible orderings for the holes, and then for each ordering looks at possible target positions. It looks for orderings that have a unique maximum targeting point that is at the centre of a hole, and that yields an integer average score per shot. Once an ordering passes these tests we record the hole that the target is in, along with the two holes on either side. This gives a unique target + left/right value (although there are many orderings that contain the three holes appropriately positioned).

      It runs in 1.58s, but I think this could be improved with some additional analysis.

      from enigma import irange, subsets, multiset, ordered, printf
      
      # available holes (points)
      holes = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
      
      # layout for a sequence of holes
      # return a list of: (region size (in mm), points scored) pairs
      def layout(ps):
        for (i, p) in enumerate(ps):
          if i > 0: yield (60, 0) # gap between holes
          yield (110 - 10 * p, p) # hole size
      
      # generate intervals ((a, b), p) from a layout
      # where a, b are absolute distances, p is number of points scored
      def intervals(ss):
        a = b = 0
        for (d, p) in ss:
          if b == 0:
            (a, b) = (0, d)
          else:
            (a, b) = (b, b + d)
          yield ((a, b), p)
      
      # analyse the layout (working in 5mm steps)
      # return list of (d, (v, r)) values, where:
      # d = absolute target distance
      # v + r/240 = max average score
      def analyse(ss):
        # determine total length
        t = sum(d for (d, _) in ss)
        rs = list()
        # consider target positions (in 5mm steps)
        for x in irange(120, t - 120, step=5):
          # consider each zone
          r = 0
          for ((a, b), p) in intervals(ss):
            # overlap?
            if b < x - 120: continue
            if a > x + 120: break
            d = min(x + 120, b) - max(x - 120, a)
            r += p * d
          rs.append((x, r))
        # find maximum average value
        m = max(r for (_, r) in rs)
        return list((x, divmod(r, 240)) for (x, r) in rs if r == m)
      
      # collect results
      m = multiset()
      
      # choose an order for the holes
      for ps in subsets(holes, size=len, select="P"):
        # but ignore the order in the diagram
        if ps == (6, 3, 8, 7, 2, 5, 1, 4): continue
        # construct the sequence of (regions, points)
        ss = list(layout(ps))
        # analyse it
        rs = analyse(ss)
        # there should only be one max position
        if len(rs) != 1: continue
        (x, (v, r)) = rs[0]
        # and the average score should be an integer
        if r != 0: continue
        # find the interval x is in
        for ((a, b), p) in intervals(ss):
          # and check it is centred
          if p > 0 and a < x < b and b - x == x - a:
            # find the holes on either side
            i = ps.index(p)
            z = ps[i - 1:i + 2]
            printf("[{ps} -> target = {x} mm, avg pts = {v}; segment = {z}]")
            m.add((p, ordered(ps[i - 1], ps[i + 1])))
      
      # output solution
      for ((x, (l, r)), n) in m.most_common():
        printf("centre = {x}, left/right = {l}/{r} [{n} solutions]")
      

      Solution: (a) You should aim at the centre of the 5 point hole. (b) The 6 point and 8 point holes are either side of the 5 point hole.

      Here is a diagram of the arrangement:

      The “out of bounds” areas are indicated in red, and we score zero points if the centre of the ball lands in these.

      In the 24cm section centred on the 5 point hole we see that there is a 3cm zone where we can score 6 points, a 6cm zone where we can score 5 points, and a 3cm zone where we can score 8 points.

      The average expected score is thus: (6×3 + 5×6 + 8×3) / 24 = 72 / 24 = 3.

      Like

      • Jim Randell 6:28 pm on 30 May 2020 Permalink | Reply

        Here is the program adapted to just consider the centre + left/right values. It finds there is only one segment that must appear in any solution (or its reverse), and this gives the required answer. It runs in 54ms.

        Run: [ @repl.it ]

        from enigma import irange, subsets, peek, printf
        
        # available holes (points)
        holes = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
        
        # layout for a sequence of holes (in mm)
        # return a list of: (region size, points scored) pairs
        def layout(ps):
          for (i, p) in enumerate(ps):
            if i > 0: yield (60, 0) # gap between holes
            yield (110 - 10 * p, p) # hole
        
        # generate intervals ((a, b), p) from a layout
        # where a, b are absolute distances, p is the number of points scored
        def intervals(ss):
          a = b = 0
          for (d, p) in ss:
            if b == 0:
              (a, b) = (0, d)
            else:
              (a, b) = (b, b + d)
            yield ((a, b), p)
        
        # analyse the layout (working in 5mm steps)
        # return list of (d, (v, r)) values, where:
        # d = absolute target distance
        # v + r/240 = max average score
        def analyse(ss):
          # determine total length
          t = sum(d for (d, _) in ss)
          rs = list()
          # consider target positions (in 5mm steps)
          for x in irange(120, t - 120, step=5):
            # consider each zone
            r = 0
            for ((a, b), p) in intervals(ss):
              # overlap?
              if b < x - 120: continue
              if a > x + 120: break
              d = min(x + 120, b) - max(x - 120, a)
              r += p * d
            rs.append((x, r))
          # find maximum average value
          m = max(r for (_, r) in rs)
          return list((x, divmod(r, 240)) for (x, r) in rs if r == m)
        
        # find triples with integer scores max average scores at the centre of the centre hole
        
        # choose the centre hole and left/right holes
        for (X, L, R) in subsets(holes, size=3, select="P"):
          if not(L < R): continue
          # create the layout
          ss = list(layout((L, X, R)))
          # analyse it
          rs = analyse(ss)
          # there should be only one max position
          if len(rs) != 1: continue
          (x, (v, r)) = rs[0]
          # and the max average score should be an integer
          if r != 0: continue
          # and it should be centred on X
          ((a, b), _) = peek(intervals(ss), 2)
          if a < x < b and b - x == x - a:
            printf("segment = ({L}, {X}, {R}) -> target = {x} mm, avg pts = {v}")
        

        I suppose really I should demonstrate that we can construct an ordering containing the required segment that satisfies all the requirements, but as my first program finds lots I don’t think it is necessary.

        Like

    • Robert Brown 10:02 am on 30 May 2020 Permalink | Reply

      If the middle & adjacent slots are too small, the ±12 cm range goes into the next slot, which is undefined. This reduces the solution space and quickly leads to what appears to be a unique result. But if you reduce the smaller adjacent slot by 1 and increase the other one, it still works. This would be valid if the smaller slot was the first one on the board, so a possible duplicate result?

      Like

      • Jim Randell 1:11 pm on 30 May 2020 Permalink | Reply

        @Robert: I don’t think it is possible for the target area to extend beyond the centre hole and the holes on either side. The smallest holes are 7cm and 8cm and the distance from the centre of one to the edge of the other is always greater than 12cm, so I think we only need to consider centre + left/right configurations. (Which I’m looking at to give a more efficient program).

        Like

    • Robert Brown 10:52 am on 30 May 2020 Permalink | Reply

      Further to above. The ‘not to scale’ drawing masks the fact that low value slots are quite wide. I assume there are 8 values as per the drawing, with corresponding slot widths.
      So there is a solution where the mid value is low, and the adjacent values can take one of two different pairs (they have the same sum), and where the total length measured from the centre of the mid slot is > 12 in each case. Definitely two sets of results, doesn’t matter where they are on the board. Maybe I’m missing something?

      Like

    • Robert Brown 12:17 pm on 30 May 2020 Permalink | Reply

      This is not a good place to have a conversation. You have my email address, but I don’t have yours!
      Both of the above sets of results work, but each post has typos which I cannot correct. An in depth exploration reveals 5 different solutions, all with 3 different L M R values between 1 & 8, and with average values of 3, 4 or 5. In each case the minimum distance from the centre of the middle value (where he aims for) is at least 15.5 cm before going into the next (unknown) slot, plenty of room for the 2cm radius ball to have it’s centre up to 12 cm from that centre. So no need for any of the slots to be the first one on the board.

      Like

      • Jim Randell 6:55 pm on 1 June 2020 Permalink | Reply

        @Robert: It’s a limitation of WordPress.com I’m afraid, but if there are any corrections you would like to make, just post a followup comment, and I will use it to correct errors in the original.

        Like

  • Jim Randell 5:08 pm on 22 May 2020 Permalink | Reply
    Tags:   

    Teaser 3009: Head count 

    From The Sunday Times, 24th May 2020 [link]

    My grandson and I play a simple coin game. In the first round we toss seven coins and I predict how many “heads” there will be whilst my grandson predicts the number of “tails”. After the tossing I score a point for each head plus a bonus of ten if my prediction was correct — my grandson scores likewise for the tails. We then repeat this with six coins, then five, and so on down to a single coin. After each round we keep cumulative totals of our scores. In one game, for over half of the pairs of cumulative scores, my grandson’s total was like mine but with the digits in reverse order. In fact he was ahead throughout and at one stage his cumulative total was double mine — and he had an even bigger numerical lead than that on just one earlier occasion and one later occasion.

    List the number of heads in each of the seven rounds.

    [teaser3009]

     
    • Jim Randell 11:03 pm on 22 May 2020 Permalink | Reply

      Originally I missed the significance of the word “numerical”, and got no solutions. But careful interpretation of the puzzle text does lead to a single solution.

      I wrote a recursive function that keeps track of all the conditions as it goes along.

      The following Python 3 program runs in 320ms.

      Run: [ @repl.it ]

      from itertools import product
      from enigma import irange, nsplit, join, cached, printf
      
      # does A mirror B?
      mirror = cached(lambda A, B: nsplit(A) == nsplit(B)[::-1])
      
      # play the game starting with a round of k coins,
      # where A plays heads, B plays tails, and B is always ahead
      # ms = number of points B is ahead of A
      # s = index in ms when B = 2A
      # rv = count number of scores that are reverse of each other
      def play(k, tA=0, tB=0, ms=[], s=None, rv=0, ss=[]):
        # are we done?
        if k == 0:
          if s is not None and rv > 3:
            # there must be exactly 1 round after s where B is further ahead
            if sum(x > ms[s] for x in ms[s + 1:]) == 1:
              yield ss
        else:
          # consider the number of heads, and predictions for heads and tails
          for (n, h, t) in product(irange(0, k), (0, 1), (0, 1)):
            # calculate the points for each player
            a = n + h * 10
            b = k - n + t * 10
            # and the total points
            A = tA + a
            B = tB + b
            m = B - A
            # B is always ahead
            if not(m > 0): continue
            # look for cases where B = 2A
            s_ = s
            if B == 2 * A:
              # it only happens once
              if s is not None: continue
              # there must be exactly 1 previous round where B is further ahead
              if not(sum(x > m for x in ms) == 1): continue
              s_ = len(ms)
            # are A, B mirrored scores?
            rv_ = rv + mirror(A, B)
            # in the final 4 rounds we must have encountered some mirrored scores
            if k < 5 and rv_ < 5 - k: continue
            # play the remaining rounds
            yield from play(k - 1, A, B, ms + [m], s_, rv_, ss + [(n, h, t, A, B)])
      
      # play the game, starting with 7 coins
      for ss in play(7):
        # output the rounds
        (pA, pB) = (0, 0)
        s = list(i for (i, (n, h, t, A, B)) in enumerate(ss) if B == 2 * A)[0]
        for (i, (n, h, t, A, B)) in enumerate(ss):
          k = 7 - i
          fs = [ f"lead = {B - A}" ]
          if i == s: fs.append("double")
          if mirror(A, B): fs.append("mirror")
          printf(
            "{k} coins: heads={n}; predictions = ({h}, {t}); points = ({a}, {b}); totals = ({A},  {B}); {fs}",
            a=A - pA, b=B - pB, fs=join(fs, sep="; "),
          )
          (pA, pB) = (A, B)
        printf()
      

      Solution: The number of heads in each of the rounds was: 0, 2, 4, 4, 3, 1, 1.

      The full description of the rounds is:

      k   h  t  |  H   T  |  a   b  |  A   B
      7:  0  7  |  -  10  |  0  17  |  0  17  [lead >16]
      6:  2  4  | 10   -  | 12   4  | 12  21  [mirror]
      5:  4  1  |  -  10  |  4  11  | 16  32  [double, lead =16]
      4:  4  0  |  -   -  |  4   0  | 20  32
      3:  3  0  |  -   -  |  3   0  | 23  32  [mirror]
      2:  1  1  | 10  10  | 11  11  | 34  43  [mirror]
      1:  1  0  |  -  10  |  1  10  | 35  53  [mirror, lead >16]
      

      (k = number of coins; h, t = number of heads/tails; H, T = bonus points; a, b = points in round; A, B = cumulative totals)


      However, keeping the cumulative totals always using 2 digits gives us three further solutions where the totals 03 and 30 are used as mirrored pairs:

      k   h  t  |  H   T  |  a   b  |  A   B
      7:  1  6  |  -  10  | 01  16  | 01  16
      6:  2  4  |  -  10  | 02  14  | 03  30  [mirror, lead >16]
      5:  3  2  | 10   -  | 13  02  | 16  32  [double, lead =16]
      4:  4  0  |  -   -  | 04  00  | 20  32
      3:  3  0  |  -   -  | 03  00  | 23  32  [mirror]
      2:  1  1  | 10  10  | 11  11  | 34  43  [mirror]
      1:  1  0  |  -  10  | 01  10  | 35  53  [mirror, lead >16]
      
      
      k   h  t  |  H   T  |  a   b  |  A   B
      7:  2  5  |  -  10  | 02  15  | 02  15
      6:  1  5  |  -  10  | 01  15  | 03  30  [mirror, lead >16]
      5:  3  2  | 10   -  | 13  02  | 16  32  [double, lead =16]
      4:  4  0  |  -   -  | 04  00  | 20  32
      3:  3  0  |  -   -  | 03  00  | 23  32  [mirror]
      2:  1  1  | 10  10  | 11  11  | 34  43  [mirror]
      1:  1  0  |  -  10  | 01  10  | 35  53  [mirror, lead >16]
      
      
      k   h  t  |  H   T  |  a   b  |  A   B
      7:  3  4  |  -  10  | 03  14  | 03  14
      6:  0  6  |  -  10  | 00  16  | 03  30  [mirror, lead >16]
      5:  3  2  | 10   -  | 13  02  | 16  32  [double, lead =16]
      4:  4  0  |  -   -  | 04  00  | 20  32
      3:  3  0  |  -   -  | 03  00  | 23  32  [mirror]
      2:  1  1  | 10  10  | 11  11  | 34  43  [mirror]
      1:  1  0  |  -  10  | 01  10  | 35  53  [mirror, lead >16]
      

      The program will find all 4 solutions if we replace the calls to [[ nsplit(x) ]] with [[ nsplit(x, 2) ]] in the function [[ mirror() ]] (line 5).

      Like

    • Robert Brown 11:57 am on 24 May 2020 Permalink | Reply

      Turns out there’s a simple manual solution. After each section (7,6,5 etc) there’s a total sum for all heads & tails. Last digit is different in each case. Adding bonuses makes no difference.
      Need to find 4 sections that end in reversible numbers, so just look for reversible pairs where the sum of the pair has the same last digit. Only works for 4 sections, QED.

      Like

  • Jim Randell 5:13 pm on 15 May 2020 Permalink | Reply
    Tags:   

    Teaser 3008: Three-fruit fractions 

    From The Sunday Times, 17th May 2020 [link]

    The owner of the old curiosity shop repaired an antique mechanical fruit machine having three wheels of identical size and format. Afterwards each wheel was independently fair, just as when new. Each wheel’s rim had several equal-sized zones, each making a two-figure whole number of degrees angle around the rim. Each wheel had just one zone showing a cherry, with other fruits displayed having each a different single-figure number (other than one) of zone repetitions.

    Inside the machine were printed all the fair chances (as fractions) of getting three of the same fruit symbol in one go. Each of these fractions had a top number equal to 1 and, of their bottom numbers, more than one was odd.

    What was the bottom number of the chance for three cherries?

    [teaser3008]

     
    • Jim Randell 7:26 am on 16 May 2020 Permalink | Reply

      I assumed the wheels are identical duplicates of each other, which gives a unique solution.

      This Python 3 program runs in 49ms.

      Run: [ @repl.it ]

      from enigma import Rational, divisors, div, irange, join, printf
      
      F = Rational()
      
      # decompose t into numbers between 2 and 9
      def decompose(t, m=2, M=9, s=[]):
        if not(t < m or t > M):
          yield s + [t]
        for x in irange(m, min(t - m, M)):
          yield from decompose(t - x, x + 1, M, s + [x])
      
      # each wheel is divided into n equal sized divisions
      # each spanning d degrees
      for n in divisors(360):
        d = div(360, n)
        if d < 10: break
        if d > 99: continue
      
        # probability of 3 cherries
        p = F(1, n) ** 3
      
        # consider the number of other fruits (all different and between 2 and 9)
        for ns in decompose(n - 1):
          # calculate the probabilities of getting 3 of each of the other fruits
          ps = list(F(x, n) ** 3 for x in ns)
          # probabilities are all 1/N
          if not all(x.numerator == 1 for x in ps): continue
          # and more than one N is odd
          if sum(x.denominator % 2 == 1 for x in ps) < 2: continue
      
          # output solution
          printf("{n} divisions, {d} degrees -> 1 + {ns}; p={p}, ps=[{ps}]", ps=join(ps, sep=", "))
      

      Solution: There is a 1 / 5832 chance of getting 3 cherries.

      Each wheel is divided into 18 sectors. Each sector subtends 20°.

      There are 4 fruits, each is allocated 1, 2, 6, 9 sectors on each wheel.

      The probabilities for each of the 4 fruits are: 1/5832 (= 1/18³), 1/729 (= 1/9³), 1/27 (= 1/3³), 1/8 (= 1/2³).

      Like

  • Jim Randell 3:59 pm on 7 May 2020 Permalink | Reply
    Tags:   

    Teaser 3007: Paving stones 

    From The Sunday Times, 10th May 2020 [link]

    James has decided to lay square block paving stones on his rectangular patio. He has calculated that starting from the outside and working towards the middle that he can lay a recurring concentric pattern of four bands of red stones, then three bands of grey stones, followed by a single yellow stone band. By repeating this pattern and working towards the centre he is able to finish in the middle with a single line of yellow stones to complete the patio.

    He requires 402 stones to complete the first outermost band. He also calculates that he will require exactly 5 times the number of red stones as he does yellow stones.

    How many red stones does he require?

    [teaser3007]

     
    • Jim Randell 4:33 pm on 7 May 2020 Permalink | Reply

      Assuming an x by y rectangle, with x > y.

      If there are k repeats of the (red, grey yellow) bands, then y = 16k − 1.

      And the first band of red stones requires 2x + 2y − 4 = 402 stones, so x + y = 203.

      Here is a constructive program that counts the number of stones in each band. It runs in 78ms.

      from enigma import irange, inf, printf
      
      # calculate the number of stones with <k> repeats
      # and the initial band being <x> by <y>
      def stones(k, y, x):
        d = dict(R=0, G=0, Y=0)
        for i in ("RRRRGGGY" * k):
          if y < 2:
            d[i] += x * y
            break
          d[i] += 2 * (x + y - 2)
          x -= 2
          y -= 2
        return (d['R'], d['G'], d['Y'])
      
      # consider the number of repeats of the bands
      for k in irange(1, inf):
        y = 16 * k - 1
        x = 203 - y
        if not(x > y): break
       
        # calculate the number of stones needed
        (R, G, Y) = stones(k, y, x)
       
        # output solution
        if 5 * Y == R:
          printf("k={k}, y={y} x={x}; R={R} G={G} Y={Y}")
      

      Solution: James requires 5520 red stones.

      The patio consists of 6 red/grey/yellow layers, finishing with a single row of 14 yellow stones:

      The number of stones required is: red = 5520, grey = 3636, yellow = 1104; total = 10260.

      The outer band measures 108×95 stones.

      Like

    • Jim Randell 9:33 am on 10 May 2020 Permalink | Reply

      Each band requires 8 fewer stones than the previous band, so we can just start with the outermost band (402 stones) and work our way in. When we get to the number blocks for the yellow band we can adjust the number to account for a single line to see if we have reached the middle of the design, and if not carry on. We don’t need to do any analysis to work out the dimensions of the patio, or consider the number of repeats.

      This gives us a simpler, and slightly shorter, program.

      Run: [ @repl.it ]

      from enigma import irange, chunk, printf
      
      # number of blocks in outer band
      n = 402
      
      # record Red, Grey, Yellow blocks required
      R = G = Y = 0
      
      # work inwards in chunks of 8 bands
      # each band has 8 less blocks than the previous band
      for s in chunk(irange(n, 1, step=-8), 8):
        if len(s) < 8: break
        (r1, r2, r3, r4, g1, g2, g3, y) = s
        R += r1 + r2 + r3 + r4
        G += g1 + g2 + g3
        # the middle is a single row
        m = 1 + y // 2
        if 5 * (Y + m) == R:
          printf("R={R} G={G} Y={Y}", Y=Y + m)
        # otherwise, carry on
        Y += y
      

      Like

  • Jim Randell 5:53 pm on 1 May 2020 Permalink | Reply
    Tags:   

    Teaser 3006: Raffle tickets 

    From The Sunday Times, 3rd May 2020 [link]

    At our local bridge club dinner we were each given a raffle ticket. The tickets were numbered from 1 to 80. There were six people on our table and all our numbers were either prime or could be expressed as the product of non-repeating primes (e.g. 18 = 2×3×3 is not allowed). In writing down the six numbers you would use each of the digits 0 to 9 once only. If I told you the sum of the six numbers (a perfect power) you should be able to identify the numbers.

    List the numbers (in ascending order).

    [teaser3006]

     
    • Jim Randell 6:14 pm on 1 May 2020 Permalink | Reply

      This Python program runs in 172ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, is_duplicate, factor, seq_all_different as all_different, filter_unique, iroot, printf
      
      # find numbers with different prime factors, and no repeated digits
      ns = list()
      for n in irange(1, 80):
        if is_duplicate(n): continue
        fs = factor(n)
        if fs and all_different(fs):
          ns.append(n)
      
      # find sets of k numbers, that use the digits 0-9 exactly once
      def generate(ns, k, ds=set(), s=[]):
        # are we done?
        if k == 0:
          if len(ds) == 10:
            yield tuple(s)
        else:
          # add in another number
          for (i, n) in enumerate(ns, start=1):
            t = str(n)
            if ds.intersection(t): continue
            yield from generate(ns[i:], k - 1, ds.union(t), s + [n])
      
      # find 6-sets that are unique by sum
      (ss, _) = filter_unique(generate(ns, 6), sum)
      
      # find powers for n
      def powers(n, p=1):
        for k in irange(p, inf):
          x = iroot(n, k)
          if x ** k == n:
            yield (x, k)
          if x == 1: break
      
      # output solution
      for s in ss:
        t = sum(s)
        ps = list(powers(t, 2))
        printf("{s} -> {t} {ps}")
      

      Solution: The numbers are: 2, 3, 41, 58, 69, 70.

      The sum is 243 (= 3^5).

      We can find 78 different sets of 6 numbers that use the digits 0-9 exactly once, but only the set given above has a unique sum (which is the largest possible sum).

      Like

    • GeoffR 11:25 am on 5 May 2020 Permalink | Reply

      The programme found four solutions, but only the first is a correct unique solution
      ie Tickets: 2, 3, 41, 58, 69, 70.

      There is anpother duplicate solution with a total of 216, but the programme did not find it. Two other potential solutions also had a total of 225, so do not give a unique solution.

      The programme would only run under the Chuffed solver in a reasonable time.

      
      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 0..9:A; var 0..9:B; var 0..9:C; var 0..9:D;
      var 0..9:E; var 0..9:F; var 0..9:G; var 0..9:H;
      var 0..9:I; var 0..9:J;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I,J]);
      
      % total of six factors
      var 100..400: total;
      
      % perfect powers possible between 100 and 400
      constraint total == pow(2,8) \/ total == pow(3,4) \/ total == pow(3,5) 
      \/ total == pow(5,3) \/ total == pow(6,3) \/ total == pow(7,3)
      \/ total == pow(12,2) \/ total == pow(13,2) \/ total = pow(14,2)
      \/ total == pow(15,2) \/ total == pow(17,2) \/ total = pow(18,2);
      
      % numbers are A, B, CD, EF, GH, IJ
      total = A + B + CD + EF + GH + IJ;
      var 11..80: CD = 10*C + D;
      var 11..80: EF = 10*E + F;
      var 11..80: GH = 10*G + H;
      var 11..80: IJ = 10*I + J;
      
      % Possible prime factors for CD, EF, GH and IJ
      var 2..79: a1; var 2..79: a2; var 2..79: a3;
      var 2..79: b1; var 2..79: b2; var 2..79: b3;
      var 2..79: c1; var 2..79: c2; var 2..79: c3;
      var 2..79: d1; var 2..79: d2; var 2..79: d3;
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      constraint is_prime (A) /\ is_prime(B);
      
      % CD is prime or has two or three different prime factors
      constraint (is_prime(CD))
      \/ 
      (a1 != a2 /\ CD == a1 * a2 /\ is_prime(a1) /\ is_prime(a2))
      \/  
      (a1 != a2 /\ a1 != a3 /\ a2 != a3 /\ CD == a1 * a2 * a3 /\ 
      is_prime(a1) /\ is_prime(a2) /\ is_prime(a3));
      
      % EF is prime or has two or three different prime factors
      constraint (is_prime(EF))
      \/ 
      (b1 != b2 /\ EF == b1 * b2 /\ is_prime(b1) /\ is_prime(b2))
      \/  
      (b1 != b2 /\ b1 != b3 /\ b2 != b3 /\ EF == b1 * b2 * b3 /\ 
      is_prime(b1) /\ is_prime(b2) /\ is_prime(b3));
      
      % GH is prime or has two or three different prime factors
      constraint (is_prime(GH))
      \/ 
      (c1 != c2 /\ GH == c1 * c2 /\ is_prime(c1) /\ is_prime(c2))
      \/  
      (c1 != c2 /\ c1 != c3 /\ c2 != c3 /\ GH == c1 * c2 * c3 /\ 
      is_prime(c1) /\ is_prime(c2) /\ is_prime(c3));
      
      % IJ is prime or has two or three different prime factors
      constraint (is_prime(IJ))
      \/ 
      (d1 != d2 /\ IJ == d1 * d2 /\ is_prime(d1) /\ is_prime(d2))
      \/  
      (d1 != d2 /\ d1 != d3 /\ d2 != d3 /\ IJ == d1 * d2 * d3 /\ 
      is_prime(d1) /\ is_prime(d2) /\ is_prime(d3));
      
      constraint increasing([A ,B, CD, EF, GH, IJ]);
      
      solve satisfy;
      
      output ["Tickets: " ++ show(A) ++ ", " ++ show(B) ++ ", " 
      ++ show(CD) ++ ", " ++ show(EF) ++ ", " ++ show(GH) ++ ", "
      ++ show(IJ) ++ ", total = " ++ show(total) ];
      
      
      % Tickets: 2, 3, 41, 58, 69, 70, total = 243  <<< Correct Solution
      % time elapsed: 0.03 s
      % ----------
      % Tickets: 2, 3, 14, 58, 69, 70, total = 216 << A duplicate solution exists
      % time elapsed: 0.03 s
      % ----------
      % Tickets: 2, 5, 38, 41, 69, 70, total = 225 - duplicate 
      % time elapsed: 0.03 s
      % ----------
      % Tickets: 2, 5, 30, 41, 69, 78, total = 225 _ duplicate
      % time elapsed: 0.03 s
      % ----------
      % ==========
      
      

      Like

  • Jim Randell 5:07 pm on 24 April 2020 Permalink | Reply
    Tags:   

    Teaser 3005: Tubular bales 

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

    Ten equal-length, rigid tubes, each a different prime-valued external radius from 11 mm to 43 mm, were baled, broadside, by placing the 43 mm and 11 mm tube together and the third tube, not the largest remaining, touching both of these. Each subsequent tube touched the previous tube placed and the 43 mm tube. A sub-millimetre gap between the final tube placed and the 11 mm tube, made a near perfect fit.

    The radius sum of the first three tubes placed against the 43 mm tube was a multiple of one of the summed radii. Curiously, that statement remains true when each of “four”, “five”, “seven” and “eight” replaces “three”. For “two” and “six” tubes placed their radius sum was a multiple of an as yet unplaced tube’s radius.

    What radius tube, in mm, was placed last?

    [teaser3005]

     
    • Jim Randell 5:30 pm on 24 April 2020 Permalink | Reply

      This Python program runs in 78ms.

      Run: [ @replit ]

      from enigma import (primes, printf)
      
      # numbers available to to use
      rs = list(primes.between(11, 44))
      assert len(rs) == 10
      
      # check n is a multiple of some element of ms
      check = lambda n, ms: any(n % m == 0 for m in ms)
      
      # solve for the specified numbers
      # ns = unused numbers
      # ss = used numbers
      def solve(ns, ss):
        # are we done?
        if not ns:
          yield ss
        else:
          # what number placement is this?
          k = len(ss) + 1
          t = sum(ss)
          # choose the next number to use
          for (i, n) in enumerate(ns):
            # 2nd: not the largest available
            if k == 2 and n == ns[-1]: continue
            t_ = t + n
            # 3rd, 4th, 5th, 7th, 8th: multiple of a used number
            ss_ = ss + [n]
            if k in (3, 4, 5, 7, 8) and not check(t_, ss_): continue
            # 2nd, 6th: multiple of an unused number
            ns_ = ns[:i] + ns[i + 1:]
            if k in (2, 6) and not check(t_, ns_): continue
            # solve for the remaining numbers
            yield from solve(ns_, ss_)
      
      # collect possible final numbers
      fs = set()
      for ss in solve(rs[1:-1], rs[:1]):
        fs.add(ss[-1])
        printf("{ss}")
      
      # output solution
      printf("final number = {fs}")
      

      Solution: The 37 mm tube was placed last.

      The conditions placed on the ordering of the numbers means that although there are four possible orders that the tubes could be assembled in, the answer to the puzzle (the radius of the final tube) is the same in all cases.

      So it is not necessary to check that the placement results in a gap of less than 1 mm, but if you do, you find all 4 orderings result in a gap less than 1 mm (and one of them is an almost perfect fit).

      Here is a diagram of the packing (11, 23, 17, 41, 29, 31, 19, 13, 37) around the 43 tube. This has the largest gap of 0.66 mm.

      Here is a list of 4 packings, and the corresponding gaps:

      (11, 23, 17, 41, 29, 31, 13, 19, 37) → gap = 0.36 mm
      (11, 23, 17, 41, 29, 31, 19, 13, 37) → gap = 0.66 mm
      (11, 23, 17, 41, 31, 29, 13, 19, 37) → gap = 0.000055 mm
      (11, 23, 17, 41, 31, 29, 19, 13, 37) → gap = 0.41 mm

      The third one has a gap of just 55 nm, which is about half the diameter of a single coronavirus particle, and probably quite a lot smaller than the tolerance of the tubes.

      Perhaps the puzzle was intended to be set with the radii of the tubes measured in centimetres, then there would be only one arrangement that had a sub-millimetre gap.

      Like

  • Jim Randell 4:27 pm on 17 April 2020 Permalink | Reply
    Tags:   

    Teaser 3004: Going up 

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

    In our football league, the teams all play each other once, with three points for a win and one for a draw. At the end of the season, the two teams with most points are promoted, goal difference being used to separate teams with the same number of points.

    Last season’s climax was exciting. With just two games left for each team, there were several teams tied at the top of the league with the same number of points. One of them, but only one, could be certain of promotion if they won their two games. If there had been any more teams on the same number of points, then none could have guaranteed promotion with two wins.

    How many teams were tied at the top of the league, and how many of the remaining matches involved any of those teams?

    [teaser3004]

     
    • Jim Randell 9:33 am on 18 April 2020 Permalink | Reply

      I supposed there were several teams, A, B, C, …, tied at the top. And we are looking for situations where team A is looking at a guaranteed promotion, if they win both their games.

      Obviously any of the other teams tied at the top of the table would also be in with a chance of promotion if they win both their games (as they will have the same maximum number of points as A).

      But if one of the teams were to win a match by an enormous number of goals, it would give them an unassailable goal difference. So A can only be guaranteed a win if there are fewer than three teams tied at the top after the games are played (so the goal difference rule doesn’t come into it).

      So we need to look at numbers of teams, such that there is an arrangement of remaining matches, where A (and only A) is guaranteed a promotion if they win both their matches, but if there were one more team then there would be no such arrangement of matches.

      This Python program is a bit slow (it takes 8.9s), but it does find what seems to be a reasonable answer. I may see if I can come up with a more efficient program later.

      from enigma import (cproduct, multiset, irange, join, printf)
      
      # generate matches for teams <ts> tied at the top
      # ts = teams tied at the top
      # ss = number of matches to be played by teams in <ts>
      # team Z is used to denote any other team not in <ts>
      def matches(ts, ss, ms=[]):
        # are we done?
        if not ss:
          yield ms
        else:
          # choose a team
          ks = sorted(ss.keys())
          t = ks.pop(0)
          # choose an opponent
          ks.append('Z')
          for x in ks:
            m = (t, x)
            if x == 'Z' or not (ms and m < ms[-1]):
              yield from matches(ts, ss.difference(m), ms + [m])
      
      # find teams that can be guaranteed promotion
      # ts = teams tied at the top
      # ms = remaining matches
      def solve(ts, ms):
        # find wins where 2 wins guarantees A a place in the top 2
        (inc, exc) = (set(), set())
        # choose winning teams for each match
        for wins in cproduct(ms):
          # collect teams with 2 wins
          m = multiset.from_seq(wins)
          ws = list(t for (t, n) in m.items() if n == 2 and t != 'Z')
          if len(ws) < 3:
            # a guaranteed win
            inc.update(ws)
          else:
            # not a guaranteed win
            exc.update(ws)
            if exc.issuperset(ts): return set()
        # return those teams that are guaranteed a win in all situations
        return inc.difference(exc)
      
      # format a sequence of matches
      fmt = lambda ms: join((x + "v" + y for (x, y) in ms), sep=", ", enc="()")
      
      # consider teams labelled A, B, C, ... (Z is used to denote "other" teams)
      # record teams where there is a set of matches that guarantees only team A a promotion
      r = dict()
      for n in irange(2, 25):
        teams = "ABCDEFGHIJKLMNOPQRSTUVWXY"[:n]
        ss = multiset.from_seq(teams * 2)
        for ms in matches(teams, ss):
          # does this set of matches guarantee a promotion for only A?
          ws = solve(teams, ms)
          if len(ws) == 1 and 'A' in ws:
            printf("n={n}: {ms} -> {ws}", ms=fmt(ms), ws=join(sorted(ws)))
            r[n] = ms
            break # we only need one set of matches
        if n not in r:
          printf("n={n}: <none>")
          # are we done?
          k = n - 1
          if k in r:
            ms = r[k]
            printf("{k} -> {ms}; {m} matches", m=len(ms), ms=fmt(ms))
            break
      

      Solution: There are 6 teams tied at the top. 7 of the remaining matches involve at least one of those teams.


      For six teams at the top:

      If A plays B and C and wins both matches, then neither B nor C can achieve the maximum number of points, so they are out of contention.

      And there are three more teams at the top, D, E, F, and they all play each other, then only one of them can achieve 2 wins, to tie with A at the top of the table.

      So A is guaranteed to finish in the top 2 if they win both their games, and get promotion.

      Introducing a seventh team, G, would mean that a third team could get two wins, so A‘s promotion would not be guaranteed.

      Like

  • Jim Randell 5:27 pm on 9 April 2020 Permalink | Reply
    Tags:   

    Teaser 3003: All that glitters 

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

    My aunt has a collection of sovereigns, and she set me a challenge:

    “You can have the coins if you can work out the dates, which (in increasing order) are equally spaced and all in the 20th century. The number of coins is an odd prime. The highest common factor of each pair of dates is an odd prime. The sum of the number of factors of each of the dates (including 1 and the date itself) is an odd prime.”

    I worked out the dates, though the gift was much less valuable than I’d hoped.

    What were the dates?

    [teaser3003]

     
    • Jim Randell 5:46 pm on 9 April 2020 Permalink | Reply

      I assumed the dates we are looking for are the years in the 20th century for each coin.

      This Python program runs in 93ms.

      Run: [ @repl.it ]

      from enigma import Primes, subsets, irange, gcd, tau, printf
      
      primes = Primes(100, expandable=1)
      
      # check a number is an odd prime
      check = lambda n: n > 2 and n in primes
      
      # choose years for the first 2 coins
      for (a, b) in subsets(irange(1901, 1999), size=2):
        if not check(gcd(a, b)): continue
      
        # consider a sequence with n terms
        d = b - a
        for n in primes.range(3):
          z = a + (n - 1) * d
          if z > 2000: break
          s = list(irange(a, z, step=d))
      
          # gcd of each pair is an odd prime
          if not all(check(gcd(x, y)) for (x, y) in subsets(s, size=2)): break
      
          # sum of the number of divisors of each year is an odd prime
          if not check(sum(tau(x) for x in s)): continue
      
          printf("a={a} b={b}, d={d} -> n={n}: {s}")
      

      Solution: The dates of the coins were: 1903, 1936, 1969.


      Manually (as suggested by Robert):

      Most number have divisors that come in pairs, so have an even number of divisors. The exception is the square numbers, which have an odd number of divisors (see: Puzzle #08).

      So, in order for the sum of the divisors of the dates to be odd, the list of dates must include an odd number of square numbers. And in the range 1901 – 2000 there is only one square number, 1936. So that must be one of the dates.

      1936 factorises as: (2^4)(11^2), so the other dates must have a GCD with 1936 of 11.

      For numbers less than 1936, we get: 1925, 1903. For numbers greater than 1936 we get: 1947, 1969, 1991.

      Looking for arithmetic sequences containing 1936, with a number of elements that is an odd prime we get:

      d=11: (1925, 1936, 1947); divisor sum = 35
      d=33: (1903, 1936, 1969); divisor sum = 23

      Only the second of these has a divisor sum that is prime, and gcd(1903, 1969) = 11 so this satisfies all the required conditions and gives the answer.

      Like

    • Robert Brown 9:08 pm on 9 April 2020 Permalink | Reply

      The only numbers with odd numbers of factors are perfect squares. There is only one of these in the 20th century, and that date has only has one factor >1 that’s an odd prime. Quite easy to find the answer by inspection.

      Like

  • Jim Randell 4:52 pm on 3 April 2020 Permalink | Reply
    Tags:   

    Teaser 3002: Short-cut 

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

    To demonstrate a bit of geometry and trigonometry to my grandson, I took a rectangular piece of paper whose shorter sides were 24 cm in length. With one straight fold I brought one corner of the rectangle to the midpoint of the opposite longer side. Then I cut the paper along the fold, creating a triangle and another piece. I then demonstrated to my grandson that this other piece had double the area of the triangle.

    How long was the cut?

    [teaser3002]

     
    • Jim Randell 5:40 pm on 3 April 2020 Permalink | Reply

      If we assume the fold goes from one of the corners of the rectangle, then we get a nice answer. (See: Enigma 1402). I don’t think other constructions are possible. [This assumption is justified below].

      Brainteaser 1798 is a puzzle with a similar theme.

      The triangles X, Y, Z are all right-angled. We need to find the value of h, the hypotenuse of triangle X.

      The area of triangle X must be the same as the sum of the areas of triangles Y and Z, so:

      (24 − a)b = 12b + ab/2
      12b = 3ab/2
      a = 8

      From triangle Z:

      b² = 16² − 8² = 192

      (So the long side of the rectangle is 2b = 16√3, approximately 27.71 cm).

      And from triangle X:

      h² = 16² + 2²×192 = 1024
      h = 32

      Solution: The length of the cut is 32 cm.

      And we can then demonstrate that X = Y + Z by constructing X from Y and Z:

      X, Y, Z are all (30°, 60°, 90°) triangles. The same shape as one of the standard set squares.

      Like

      • Jim Randell 3:39 pm on 5 April 2020 Permalink | Reply

        Adding a 24-by-2x strip on the left-hand side of the diagram (to account for the fold not going from a corner), and adjusting the bases of triangles Y and Z to (b − x) and (b + x) leads to the following 2 equations:

        [X = Y + Z + 48x] ⇒ 3b(8 − a) = (72 + a)x
        [Y and Z are similar] ⇒ (24 − a)x = 3b(8 − a)

        These can only be satisfied (for positive a, b) if x = 0 and a = 8 (i.e. a is 1/3 the height of the rectangle), as above.

        So the fold must go from one of the corners, and the assumption above is justified.

        Like

    • Benet Allen 7:49 pm on 5 April 2020 Permalink | Reply

      There’s only one shape where you can fold a corner to the midpoint of the opposite side and be left with a triangle. That’s a 2×1 rectangle. And surely, the remaining piece will have three times the area of the triangle? Am befuddled.

      Like

      • Jim Randell 9:23 pm on 5 April 2020 Permalink | Reply

        My diagram above [ link ] is actually to scale. If you print it out and cut out the rectangle you will find that you can fold the white X onto the grey X, and then fold Y and Z on top (or behind) to make another copy of X, neatly demonstrating that X = Y + Z as required.

        Like

  • Jim Randell 4:46 pm on 27 March 2020 Permalink | Reply
    Tags:   

    Teaser 3001: Tetragonal toy tiles 

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

    (see: [ @wikipedia ])

    Thirteen toy tiles comprised a square, rectangles, rhombuses (diamonds on a playing card are rhombuses) and kites (as shown in the diagram). All of each different type were identical. A rhombus’s longer diagonal was a whole number of inches (equalling any diagonal of any other type). Its shorter diagonal was half this. Also, one side of a rectangle was slightly over one inch.A pattern I made, using every tile laid flat, had all the symmetries of a square. After laying the first tile, each subsequent tile touched at least one other previously placed tile. Ultimately, any contact points were only where a vertex of a tile touched a vertex of just one other tile; only rhombuses touched every other tile type.

    What, in inches, was a square’s diagonal?

    [teaser3001]

     
    • Jim Randell 6:29 pm on 27 March 2020 Permalink | Reply

      I came up with a pattern for 13 tiles that has the same symmetries as a square (I’ll make a diagram of it later), and that gave me a way to calculate the sides of the rectangle, in terms of the larger diagonal of the rhombus, x.

      Once these are calculated the value of x can be determined manually, or here is a quick program to do it:

      Run: [ @replit ]

      from enigma import (sqrt, irange, inf, printf)
      
      # multipliers for the sides of the rectangle
      (ra, rb) = (sqrt(1, 8), sqrt(7, 8))
      
      # consider the diagonal of the square piece
      for x in irange(1, inf):
        # calculate the sides of the rectangle
        (a, b) = (ra * x, rb * x)
        if 1.0 < a < 1.1 or 1.0 < b < 1.1:
          printf("x={x} [a={a:.3f} b={b:.3f}]")
        elif a > 1.1:
          break
      

      Solution: The length of the square’s diagonal is 3 inches.


      I arranged 13 shapes (1 square, 4 rectangles, 4 rhombuses, 4 kites) into the following pattern:

      All the diagonals of all the shapes are equal (= x), except for the shorter diagonal of the rhombus (= x/2).

      In this arrangement the short side of the rectangle is the hypotenuse of a right-angled triangle where the other two sides have length x/4, so it has a length of x√(1/8), and so the longer side has a length of x√(7/8).

      Setting x = 3 gives dimensions of 1.061 × 2.806 inches. The smaller side being close to 1 + 1/16 inches. Which is “slightly over 1 inch” as required.

      The exact shape of the kite doesn’t matter (as long as both diagonals are x), it doesn’t affect the calculation for the rectangle. (In particular the kites could all be rotated through 180° to give a second arrangement).

      Placing the rhombuses the other way leaves a gap that cannot be filled by the required rectangle, and we don’t have enough shapes to fill the gap with multiple shapes.

      Like

    • Robert Brown 8:06 am on 28 March 2020 Permalink | Reply

      I did a scale drawing. My kite has the same aspect ratio as the one in the original text, which makes the large angle equal to that of the rhombus. I don’t think your program would have found my answer, which has the rectangle 1.03 inches high.

      Like

      • Jim Randell 8:13 am on 28 March 2020 Permalink | Reply

        @Robert: My arrangement looks like this [ link ], so the exact shape of the kite doesn’t affect the calculations. But I didn’t look too hard for alternative patterns (although you would hope the setter would have made sure there was a unique answer to the puzzle).

        Like

    • Robert Brown 11:54 am on 28 March 2020 Permalink | Reply

      Interesting. Each rhombus has a thin & thick ‘corner’. My layout has the thin corners connected to the square, then the kites & rhombuses are all angled to fit round the square. I tried (but failed) to get the rectangles in the corner, to give it ‘all the symmetries of a square’ ! My rectangle is long & thin, with diagonal =9 inches. I see Brian has 3 inches, I wonder what his layout looks like . . .

      Like

      • Jim Randell 12:36 pm on 28 March 2020 Permalink | Reply

        I tried my pattern with the rhombuses turned through 90°, but I found the gap between the remaining vertices was too large to fit any of the other shapes into.

        Looking at Brian’s attachment to the Google Sites page it looks like he has found the same layout I did (although I don’t think his kites are the right shape, but that doesn’t change the answer).

        Like

        • Brian Gladman 1:15 pm on 28 March 2020 Permalink | Reply

          That is because the teaser doesn’t explicitly constrain the non-rhombus shapes to have equal diagonals (of course, all except the kite do). The longest rhombus diagonal can be any diagonal of any other shape and I chose to match the longest diagonals of the rhombus and the kite.

          Like

          • Jim Randell 1:20 pm on 28 March 2020 Permalink | Reply

            @Brian: It does say that the longer diagonal of the rhombus should “equal any diagonal of any other type”, so I think the vertices of the kite must touch the sides of an x by x bounding box.

            Like

            • Brian Gladman 2:36 pm on 28 March 2020 Permalink | Reply

              Yes, you interpret it to mean “equal to the diagonals of the other types” (surely a simpler expression of this interpretation), whereas I interpret it to mean a choice between “any of the diagonals of any other type”. Fortunately this clear ambiguity (!) doesn’t have an impact on the answer.

              Like

    • Robert Brown 12:33 pm on 28 March 2020 Permalink | Reply

      So my alternative pattern lacks one of the required symmetries (it has clockwise & counter clockwise versions). We’ve had problems with words before . . . I guess Brian’s layout is similar to yours.

      Like

  • Jim Randell 4:25 pm on 20 March 2020 Permalink | Reply
    Tags:   

    Teaser 3000: The three thousandth 

    From The Sunday Times, 22nd March 2020 [link]

    In this addition digits have been consistently replaced by letters, different letters representing different digits. But instead of an addition in base 10 in which the letters represent the digits 0 to 9 this is an addition in base 11, using X for the extra digit, in which the letters represent the digits 1 to X, with 0 unused.

    Please submit the number (still in base 11) represented by TEASER.

    Congratulations to The Sunday Times for publishing 3000 Teaser puzzles.

    [teaser3000]

     
    • Jim Randell 4:30 pm on 20 March 2020 Permalink | Reply

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

      The following run file executes in 272ms.

      Run: [ @replit ]

      #! python -m enigma -r
      
      SubstitutedSum
      
      --base="11"
      --digits="1-10"
      
      "THREE + THOUS + ANDTH = TEASER"
      

      Solution: TEASER = 12X523.

      There are two ways to assign values to the letters, as D and O are interchangeable:

      17322 + 17495 + X6817 = 12X523 / A=10 D=8 E=2 H=7 N=6 O=4 R=3 S=5 T=1 U=9
      17322 + 17895 + X6417 = 12X523 / A=10 D=4 E=2 H=7 N=6 O=8 R=3 S=5 T=1 U=9

      Like

    • GeoffR 1:48 pm on 21 March 2020 Permalink | Reply

      The teaser uses the 10 different letters ([T,H,R,E,O,U,S,A,N,D] in this teaser), which can convieniently represent the digits (1..10), as zero is not required,

      The programme produces a single solution with the third digit as 10 (or X), alltough there are two sets of digits, with values of O and D interchangeable.

      The programme uses the standard method of adding digits in columns, with carry digits to adjacent columns for column digit sums exceeding 11.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      %    T H R E E
      %    T H O U S
      %    A N D T H
      %  -----------
      %  T E A S E R
      %  -----------
      
      % Using digits 1..10 in base 11
      var 1..10:T; var 1..10:H; var 1..10:R; var 1..10:E;
      var 1..10:O; var 1..10:U; var 1..10:S; var 1..10:A;
      var 1..10:N; var 1..10:D;
      
      constraint all_different ([T,H,R,E,O,U,S,A,N,D]);
      
      var 0..2: carry1; var 0..2: carry2; var 0..2: carry3;
      var 0..2: carry4; var 0..2: carry5;
      
      % Adding up digits in columns, starting from right side
      constraint (E + S + H) mod 11 == R 
      /\ carry1 == (E + S + H) div 11;
      
      constraint (E + U + T + carry1) mod 11 == E 
      /\ carry2 == (E + U + T + carry1) div 11;
      
      constraint (R + O + D + carry2) mod 11 == S 
      /\ carry3 == (R + O + D + carry2) div 11;
      
      constraint (H + H + N + carry3) mod 11 == A 
      /\ carry4 = (H + H + N + carry3) div 11;
      
      constraint (T + T + A + carry4) mod 11 == E 
      /\ carry5 == (T + T + A + carry4) div 11;
      
      constraint T == carry5;
      
      solve satisfy;
      
      output ["TEASER = " ++ show(T) ++ " " ++ show(E) ++ " " ++ show(A)
      ++ " " ++ show(S) ++ " " ++ show(E) ++ " " ++ show(R)  
      ++"\n" ++ "10 digits are [T,H,R,E,O,U,S,A,N,D] = " ++ show([T,H,R,E,O,U,S,A,N,D]) ];
      
      
      

      Like

  • Jim Randell 4:56 pm on 13 March 2020 Permalink | Reply
    Tags:   

    Teaser 2999: Triangular card tower 

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

    Robbie leans two very thin playing cards together, then another two together, placing an identical card across the top forming a platform, and proceeding sideways and upwards to build a roughly triangular tower.

    For the bottom layers, he uses a whole number of 53-card packs of large cards (integer length above 70mm), the number of packs equalling the number of bottom layers. He then uses small cards (75% size) to complete the tower, which is 1428mm high. The distance between the bases of two leaning cards is always 0.56 of the length of each card.

    Robbie would like to extend the tower sideways and upwards to the next possible integer height (measured in mm), still using large cards only for the bottom layers.

    How many extra cards would be needed in total?

    [teaser2999]

     
    • Jim Randell 5:49 pm on 13 March 2020 Permalink | Reply

      I assumed a classic “house of cards” construction, where the bottom layer has n triangular supports, each constructed from 2 cards, and (n − 1) horizontal cards bridging between the supports. Each higher layer has one fewer supports than the layer below it, until we reach the top, which is composed of a single triangular support. (See my comment below for a justification of this assumption).

      For the bottom layer, if there are n supports, that uses 2n cards, and then (n − 1) horizontal cards to make the platform for the next layer. In total it requires (3n − 1) cards.

      So the total number of cards required in a tower with n layers is:

      T(n) = n (3n + 1) / 2

      The supports are isosceles triangles. If the length of card is x, and the base of the support is 0.56x across, then the height of the support is 0.96x.

      The cards are described as “very thin”, which I am assuming means they have zero thickness (even when multiple cards are measured).

      This makes the height of a tower with n layers, of which the top m layers are constructed with cards that are 75% smaller as:

      H(n, m) = 0.96x ((n − m) + 0.75m)
      H(n, m) = 0.24x (4n − m)

      And in the first tower this total height is 1428 mm. Giving:

      (4n − m) x = 5950

      So the height of the larger cards is a divisor of 5950, and we are told it is greater than 70.

      This Python program runs in 76ms.

      Run: [ @repl.it ]

      from enigma import divisors, irange, inf, div, printf
      
      # consider the length of the larger cards
      for x in divisors(5950):
        if not(x > 70): continue
        d = 5950 // x
      
        # consider the number of top rows m
        # and the total number of rows n
        for m in irange(1, inf):
          (n, r) = divmod(d + m, 4)
          if not(n > m): break
          if r != 0: continue
      
          # the total number of cards required (for the n rows)
          t = n * (3 * n + 1) // 2
          # the number of smaller cards required (for the top m rows)
          s = m * (3 * m + 1) // 2
          # and so the number of larger cards required (for the bottom n-m rows)
          b = t - s
          # the number of 53 card packs used is equal to the number of bottom rows
          if 53 * (n - m) != b: continue
      
          printf("x={x} -> m={m} n={n}; t={t} s={s} b={b}")
      
          # start adding k extra rows, counting the additional cards
          a = 0
          for k in irange(1, inf):
            # add 3 cards for each bottom row
            a += 3 * (n - m)
            # and 3 cards for each top row, plus 2 for the new top
            a += 3 * (m + k) - 1
            # calculate the new height
            h = div(6 * x * (4 * n + 3 * k - m), 25)
            # is it an integer?
            if h is not None:
              printf("-> additional cards = {a} [k={k} h={h}]")
              break
      

      Solution: 355 extra cards are required.

      The larger cards are 85 mm long (so the smaller cards are 63.75 mm long).

      The original tower consisted of 21 layers. The top 14 layers being built using the smaller cards.

      This requires 672 cards in total. 301 smaller cards are required, and 371 larger cards (= 7× 53).

      Adding 5 extra layers to the tower requires 105 larger cards (1 short of 2 extra packs), and 250 smaller cards. Making the total number of extra cards required 355.

      The height of the new tower is 1734 mm.


      Analytically:

      If n is the total number of layers in the tower (= the number of supports in the base layer), and m is the number of layers of smaller cards (so: m < n), then the requirement that the number of packs of larger cards used is the same as the number larger layers is:

      53(n − m) = T(n) − T(m)
      ⇒ 106(n − m) = 3(n² − m²) + (n − m)
      ⇒ 106 = 3(n + m) + 1
      ⇒ n + m = 35

      This gives us a limited number of (n, m) pairs.

      Then considering values for x:

      x = 5950 / (4n − m)
      ⇒ x = 5950 / (5n − 35)
      ⇒ x = 1190 / (n − 7)

      And given that x > 70, this narrows (n, m, x) down to a single value, which defines the initial tower.

      We then want to know how many lots of 0.72x we need to get an integer number of millimetres height increase.

      And this gives us the number of extra oblique columns we need to add to the initial tower, and from this we can calculate the number of extra cards required.

      All this can easily be tackled manually, or here is a quick program which looks at the possibilities:

      from enigma import divisors_pairs, irange, div, printf
      
      # consider possible card sizes
      for (n, x) in divisors_pairs(1190):
        if not(x > 70): break
        # calculate n and m
        n += 7
        m = 35 - n
        if not(n > m): continue
      
        # how many extra obliques to add?
        for k in irange(1, 25):
          h = div(18 * x * k, 25) 
          if h is None: continue
          # calculate the additional number of cards
          a = k * (3 * k + 6 * n + 1) // 2
          printf("x={x} n={n} m={m} -> k={k} h={h} a={a}")
          break
      

      Like

    • Jim Randell 4:45 pm on 15 March 2020 Permalink | Reply

      Here is a diagram of the solution found by my program, which assumes that each layer has one fewer supports than the layer below it.

      However, if the spacing of the supports is constant, then the result is only “very roughly triangular”:

      I also looked for a solution where a more “roughly triangular” shape is maintained, but this means that number of supports on the bottom layer of the smaller cards does not necessarily have one fewer supports than the layer of larger cards it is resting on (it will probably have more supports).

      And I did find a solution:

      However it does require the wording “layers” and “packs” in the puzzle text to include the possibility of a single layer and a single pack.

      I think that my original solution is probably the one the setter is looking for.


      In the original solution we can narrow the gaps between the supports in the lower part of the tower, and widen them in the upper part of the tower, to get a “roughly pentagonal” shape that is perhaps closer to the “rough triangle” that the setter is looking for. (Although applying it to the second solution would make it look even more triangular).

      Here is the first solution rendered with altered spacing (but still constant within the sections):

      And by varying the spacing within the sections it should be possible to reduce the kink in the oblique sides of the triangle, and possibly even eliminate it completely.

      In fact the idea of varying the spacing opens up the possibility of many more possible towers where the number of supports in bottom layer of smaller cards is not one less than the number of supports in the top layer of the larger cards. (Or even violating this rule within a section). So I think it makes sense to restrict the towers considered to those where the number of supports decreases by one from the layer below.

      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
%d bloggers like this: