S2T2

Recent Updates Page 14 Toggle Comment Threads | Keyboard Shortcuts

• 

  Jim Randell 4:40 pm on 14 June 2024 Permalink | Reply
  Tags: by: Victor Bryant ( 143 )   

  Teaser 3221: Faulty towers 

  From The Sunday Times, 16th June 2024 [link] [link]

  

  The famous “Tower of Hanoi” puzzle consists of a number of different-sized rings in a stack on a pole with no ring above a smaller one. There are two other poles on which they can be stacked and the puzzle is to move one ring at a time to another pole (with no ring ever above a smaller one) and to end up with the entire stack moved to another pole.

  Unfortunately I have a faulty version of this puzzle in which two of the rings are of equal size. The minimum number of moves required to complete my puzzle (the two equal rings may end up in either order) consists of four different digits in increasing order.

  What is the minimum number of moves required?

  [teaser3221]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell is discussing. Toggle Comments

   
  • 

    Jim Randell 4:52 pm on 14 June 2024 Permalink | Reply

    See also: Teaser 1858 and Enigma 14.

    I re-used the [[ H() ]] function from Teaser 1858 to calculate the number of moves required for a configuration of discs.

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

    from enigma import (Accumulator, irange, inf, nsplit, is_increasing, printf)
    
    # number of moves for sequence of discs (largest to smallest)
    def H(ns):
      t = 0
      m = 1
      for n in ns:
        t += m * n
        m *= 2
      return t
    
    # consider numbers of different size discs
    for n in irange(1, inf):
      r = Accumulator(fn=min)
      # duplicate one of the discs
      for i in irange(n):
        ns = [1] * n
        ns[i] += 1
        # calculate the number of moves
        t = H(ns)
        # answer is a 4 digit number consisting of strictly increasing digits
        if 999 < t < 10000 and is_increasing(nsplit(t), strict=1):
          printf("{ns} -> {t}")
        r.accumulate(t)
      if r.value >= 6789: break
    

    Solution: The minimum number of moves required is 1279.

    The arrangement of discs is:

    

    There are 11 discs (of 10 different sizes) and discs 9 and 10 (counting from the bottom) are the same size.

    So the number of moves is:

    1×1 + 1×2 + 1×4 + 1×8 + 1×16 + 1×32 + 1×64 + 1×128 + 2×256 + 1×512 = 1279

    ---

    With analysis:

    The number of moves for a standard “Tower of Hanoi”, is the sum of the powers of 2 corresponding to each disc.

    So for a tower of 4 discs we would have:

    1 + 2 + 4 + 8 = 15 moves

    When one of the discs is duplicated we also duplicate one of the powers of 2, and this gives us a 4-digit increasing number (the smallest is 1234, and the largest 6789).

    So our starting tower must have between 10 and 12 different sizes.

    Summing the first n powers of 2:

    n=10: sum(1..512) = 1023
    n=11: sum(1..1024) = 2047
    n=12: sum(1..2048) = 4095

    And we need to duplicate one of the powers of 2 to give a number with (strictly) increasing digits:

    1023 + 256 = 1279
    2047 + 512 = 2559 (increasing, but not strictly increasing)

    LikeLike

  Reply Cancel reply

  Required fields are marked *

  Name *

  Email *

  Website

  Notify me of new comments via email.

  Notify me of new posts via email.

  Δ

• 

  Jim Randell 5:08 pm on 13 June 2024 Permalink | Reply
  Tags: by: Graham Smithers ( 83 )   

  Teaser 2577: Number waves 

  From The Sunday Times, 12th February 2012 [link] [link]

  I challenged Sam to find a 9-digit number using all of the digits 1 to 9, such that each digit occupying an even position was equal to the sum of its adjacent digits. (For example, the digit occupying position four would be equal to the sum of the digits occupying positions three and five). Sam produced a solution that was exactly divisible by its first digit, by its last digit, and by 11.

  What was his number?

  [teaser2577]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Ruud, Frits, GeoffR, and 1 other are discussing. Toggle Comments

   
  • 

    Jim Randell 5:08 pm on 13 June 2024 Permalink | Reply

    Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

    It runs in 77ms. (Internal runtime of the generated program is 230µs).

    #! python3 -m enigma -rr
    
    # suppose the number is: ABCDEFGHI
    #                  pos = 123456789
    
    SubstitutedExpression
    
    --digits="1-9"
    
    # even positions are the sum of the adjacent digits
    "A + C = B"
    "C + E = D"
    "E + G = F"
    "G + I = H"
    
    # solution is divisible by A, I and 11
    "ABCDEFGHI % A = 0"
    "ABCDEFGHI % I = 0"
    "ABCDEFGHI % 11 = 0"
    
    --answer="ABCDEFGHI"
    

    Solution: Sam’s number was: 143968275.

    LikeLike

    • 

      Ruud 7:49 pm on 15 June 2024 Permalink | Reply

      No a priori knowledge, just brute force:

      from istr import istr
      
      for i in istr.concat(istr.permutations(istr.digits("1-"), 9)):
          if (
              i[1] == i[0] + i[2]
              and i[3] == i[2] + i[4]
              and i[5] == i[4] + i[6]
              and i[7] == i[6] + i[8]
              and i.divisible_by(11)
              and i.divisible_by(i[0])
              and i.divisible_by(i[8])
          ):
              print(i)
      
      

      Note that this requires the latest-soon to be published- version of istr.

      LikeLike

  • 

    GeoffR 6:56 pm on 13 June 2024 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;
    var 1..9:g; var 1..9:h; var 1..9:i;
    
    constraint all_different([a,b,c,d,e,f,g,h,i]);
    
    var 123456789..987654321:N == a*pow(10,8) + b*pow(10,7) + c*pow(10,6) 
    + d*pow(10,5) + e*pow(10,4) + f*pow(10,3) + g*pow(10,2) + h*pow(10,1) + i;
     
    constraint N mod a == 0;
    constraint N mod i == 0;
    constraint N mod 11 == 0;
    
    constraint a + c == b /\ c + e == d /\ e + g == f /\ g + i ==h;
    
    solve satisfy;
     
    output [ "His number was " ++ show(N)];
    
    % His number was 143968275
    % ----------
    % ==========
    % Finished in 461 msec - Chuffed Solver
    
    

    LikeLike

  • 

    Frits 7:01 pm on 13 June 2024 Permalink | Reply

         
    #! python3 -m enigma -r
     
    # suppose the number is: ABCDEFGHI
    #                  pos = 123456789
     
    SubstitutedExpression
     
    --digits="1-9"
    
    # divisibility of 11 rule, abs(sum odd digits - sum even digits) is 0 or a 
    # multiple of 11, sum odd: A + C + E + G + I, sum even: A + 2.(C + G + E) + I
     
    "(11 if C + E < 11 else 22) - (C + E) = G"
     
    # even positions are the sum of the adjacent digits
    "A + C = B"
    "C + E = D"
    "E + G = F"
    "G + I = H"
     
    # solution is divisible by A and I
    "ABCDEFGHI % A = 0"
    "ABCDEFGHI % I = 0"
     
    --answer="ABCDEFGHI"
    

    LikeLike

    • 

      Frits 9:23 pm on 13 June 2024 Permalink | Reply

      You only need to know three digits (like the 1st, 3rd and 5th digits).

      from functools import reduce
      
      # convert digit sequences to number
      d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)
      
      dgts8 = set(range(1, 9))
      dgts9 = dgts8 | {9}
      
      for C in dgts8:
        for E in dgts8 - {C}:
          # 11 divisibility rule
          G = (11 if C + E < 11 else 22) - (C + E)
          D, F = C + E, E + G
          # different digits
          if len(r1 := dgts9 - {C, E, G, D, F}) != 4: continue
          for A in r1:
            B = A + C
            if len(r2 := sorted(r1 - {A, B})) != 2: continue
            H, I = r2[1], r2[0]
            if H != G + I: continue
            
            ABCDEFGHI = d2n([A, B, C, D, E, F, G, H, I])
            if ABCDEFGHI % A: continue
            if ABCDEFGHI % I: continue
            print("answer:", ABCDEFGHI)     
      

      LikeLike

  • 

    Ruud 6:44 am on 16 June 2024 Permalink | Reply

    This version does not require the divisible_by method:

    from istr import istr
    
    for i in istr.concat(istr.permutations(istr.digits("1-"), 9)):
        if i[1] == i[0] + i[2] and i[3] == i[2] + i[4] and i[5] == i[4] + i[6] and i[7] == i[6] + i[8] and i % 11 == 0 and i % i[0] == 0 and i % i[8] == 0:
            print(i)
    

    LikeLike

• 

  Jim Randell 4:42 pm on 7 June 2024 Permalink | Reply
  Tags: by: Angela Newing ( 38 )   

  Teaser 3220: Graffiti 

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

  Six pupils were in detention having been caught painting graffiti on the school wall. The teacher decided to show them some examples of abstract art and produced seven different pictures in order ABCDEFG for them to study for a few minutes. Teacher took them back, showed them again upside down and in random order, and asked them to write down which of ABCDEFG each one was.

  The answers were:

  Helen: A B C D E F G
  Ian:   A B C F E D G
  Jean:  A D F G C E B
  Kevin: A D B F C E G
  Lee:   A F C G E D B
  Mike:  C A F B E D G

  It transpired that each picture had been correctly identified by at least one pupil, and everyone had a different number of correct answers.

  What was the correct order for the upside down ones?

  [teaser3220]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Rob, Ruud, Frits, and 1 other are discussing. Toggle Comments

   
  • 

    Jim Randell 4:54 pm on 7 June 2024 Permalink | Reply

    This Python program runs in 55ms. (Internal runtime is 786µs).

    from enigma import (cproduct, seq_all_different, join, printf)
    
    # guesses
    guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()
    
    # count number of correct answers
    correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))
    
    # consider possible correct orderings (each is correctly placed by someone)
    for order in cproduct(set(xs) for xs in zip(*guesses)):
      if not seq_all_different(order): continue
      # each pupil got a different number of correct answers
      if not seq_all_different(correct(order, guess) for guess in guesses): continue
      # output solution
      printf("order = {order}", order=join(order))
    

    Solution: The correct order was: C A F G E D B.

    So the number of correct identifications for each pupil were:

    H = 1 (E)
    I = 2 (D E)
    J = 3 (B F G)
    K = 0
    L = 4 (B D E G)
    M = 5 (A C D E F)

    There are factorial(7) = 5040 possible orders that the paintings could be presented in, but as we know that each must appear in the correct position for one of the pupils we only need to look for positions that have received a guess, and using the disjoint cartestian product of the possible positions brings the number of candidate orderings down to 15.

    LikeLike

    • 

      Jim Randell 10:21 am on 8 June 2024 Permalink | Reply

      I had a look at a more efficient way to generate the disjoint cartesian product of a sequence of sets (where no value can appear in more than one position).

      It is possible to implement this fairly directly using the [[ exact_cover() ]] function from the enigma.py library, but it was slightly faster to implement a specific algorithm.

      The following Python program has an internal runtime of 331µs.

      from enigma import (peek, seq_all_different, join, printf)
      
      # guesses
      guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()
      
      # count number of correct answers
      correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))
      
      # disjoint cartestian product of a bunch of sets, any value may only appear in one position
      def disjoint_cproduct(ss):
        ss = dict(enumerate(set(xs) for xs in ss))
        return _disjoint_cproduct(ss, [None] * len(ss))
      
      # ss = remaining sets to process
      # vs = selected values
      def _disjoint_cproduct(ss, vs):
        # final slot?
        if len(ss) == 1:
          j = peek(ss.keys())
          for x in ss[j]:
            vs[j] = x
            yield tuple(vs)
        else:
          # choose a slot with the fewest options
          j = min(ss.keys(), key=(lambda j: len(ss[j])))
          for x in ss[j]:
            ss_ = dict((k, v.difference([x])) for (k, v) in ss.items() if k != j)
            vs[j] = x
            yield from _disjoint_cproduct(ss_, vs)
      
      # consider possible correct orderings (each is correctly placed by someone)
      for order in disjoint_cproduct(zip(*guesses)):
        # each pupil got a different number of correct answers
        if not seq_all_different(correct(order, guess) for guess in guesses): continue
        # output solution
        printf("order = {order}", order=join(order))
      

      Expect to see [[ disjoint_cproduct() ]] appearing in the next update to enigma.py. (Note: It is available from version 2024-06-07).

      LikeLike

  • 

    Frits 6:41 pm on 7 June 2024 Permalink | Reply

    guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()
    M, N = len(guesses), len(guesses[0])
     
    # count number of correct answers
    correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))
    
    # candidate correct pictures per slot
    sols = sorted([(set(g[i] for g in guesses), i) for i in range(N)], 
                   key=lambda x: len(x[0]))
    # save the original order
    order = [x[1] for x in sols]
    
    # get a sequence of different pictures
    def solve(ps, k, ss=[]):
      if k == 0:
        yield ss
      else:
        for n in ps[0][0]:
          if n in ss: continue
          yield from solve(ps[1:], k - 1, ss + [n])
    
    # get a sequence of <N> different pictures     
    for s in solve(sols, N):
      # put solution in the right order
      sol = ''.join(x for x, y in sorted(zip(s, order), key=lambda z: z[1]))
      # check for different numbers of correct answers
      if len(set(correct(sol, g) for g in guesses)) != M: continue
      print("answer", sol)     
    

    LikeLike

    • 

      Frits 1:36 pm on 8 June 2024 Permalink | Reply

      I assumed choosing slots with the fewest options was more efficient but without it the program is slightly faster. Jim’s disjoint_cproduct program is definitely faster compared to the version with “j = min(ss.keys())”.

      LikeLike

      • 

        Ruud 7:24 pm on 8 June 2024 Permalink | Reply

        It’s because the number of combinations of 4 out of 15 is the same as the number of combinations of 11 out of 15. Both are 1365.

        LikeLike

  • 

    Ruud 7:27 pm on 7 June 2024 Permalink | Reply

    Here’s my version:

    from itertools import permutations
    
    guesses = ["A B C D E F G".split(), "A B C F E D G".split(), "A D F G C E B".split(), "A D B F C E G".split(), "A F C G E D B".split(), "C A F B E D G".split()]
    for correct in permutations("A B C D E F G".split()):
        counts = set()
        for guess in guesses:
            count = sum(1 for c0, c1 in zip(correct, guess) if c0 == c1 and c0 != " ")
            counts.add(count)
        if len(counts) == 6:
            print(" ".join(correct))
    

    LikeLike

  • 

    Rob 5:39 pm on 16 June 2024 Permalink | Reply

    Jim’s solution shows CAFGEBD provides Jean (ADFGCEB) with 3 correct matches (BFG). It seems there are only 2 correct matches (BF) in which case the solution does not meet the criterion of “everyone having a different number of correct answers”
    The correct solution is CAFGEDB

    LikeLike

• 

  Jim Randell 5:20 pm on 6 June 2024 Permalink | Reply
  Tags: by: Danny Roth ( 86 )   

  Teaser 2573: Prime cricketers 

  From The Sunday Times, 15th January 2012 [link] [link]

  George and Martha support their local cricket team and keep records of all the results. At the end of last season, they calculated the total number of runs scored by each of the 11 players. George commented that the totals were all different three-digit palindromic primes. Martha added that the average of the 11 totals was also a palindromic prime.

  What were the two highest individual totals?

  [teaser2573]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Frits, Ruud, GeoffR, and 1 other are discussing. Toggle Comments

   
  • 

    Jim Randell 5:21 pm on 6 June 2024 Permalink | Reply

    Very straightforward constructive solution.

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

    from enigma import (primes, is_npalindrome, subsets, div, printf)
    
    # 3-digit palindromic primes
    scores = list(n for n in primes.between(100, 999) if is_npalindrome(n))
    
    # choose 11 different scores
    for ss in subsets(scores, size=11):
      # calculate the mean
      avg = div(sum(ss), 11)
      # which is also in scores
      if avg and avg in scores:
        # output solution
        printf("{avg} -> {ss}")
    

    Solution: The two highest individual totals are 787 and 919.

    The full list of totals is:

    101, 131, 151, 181, 191, 313, 353, 373, 383, 787, 919
    mean = 353

    LikeLike

  • 

    Ruud 6:41 pm on 6 June 2024 Permalink | Reply

    Very similar to @Jim Randell’s solution, but without enigma:

    import sympy
    from itertools import combinations
    
    palindromic_primes_with_length_3 = []
    for i in range(1, 1000):
        prime = sympy.prime(i)
        prime_as_str = str(prime)
        if len(prime_as_str) > 3:
            break
        if len(prime_as_str) == 3 and str(prime_as_str) == str(prime_as_str)[::-1]:
            palindromic_primes_with_length_3.append(prime)
    
    solutions = set()
    for scores in combinations(palindromic_primes_with_length_3, 11):
        average_score = sum(scores) / 11
        if average_score in palindromic_primes_with_length_3:
            solutions.add((scores, int(average_score)))
    print(solutions)
    

    LikeLike

    • 

      Frits 11:28 am on 7 June 2024 Permalink | Reply

      Sympy also has a primerange() method.

      LikeLike

  • 

    GeoffR 8:16 pm on 6 June 2024 Permalink | Reply

    
    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D;
    var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H;
    var 100..999:I; var 100..999:J; var 100..999:K; 
    
    constraint all_different([A,B,C,D,E,F,G,H,I,J,K]);
    
    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 A div 100 == A mod 10 /\ is_prime(A);
    constraint B div 100 == B mod 10 /\ is_prime(B);
    constraint C div 100 == C mod 10 /\ is_prime(C);
    constraint D div 100 == D mod 10 /\ is_prime(D);
    constraint E div 100 == E mod 10 /\ is_prime(E);
    constraint F div 100 == F mod 10 /\ is_prime(F);
    constraint G div 100 == G mod 10 /\ is_prime(G);
    constraint H div 100 == H mod 10 /\ is_prime(H);
    constraint I div 100 == I mod 10 /\ is_prime(I);
    constraint J div 100 == J mod 10 /\ is_prime(J);
    constraint K div 100 == K mod 10 /\ is_prime(K);
    
    var 1000..9999:asum;
    var 100..999:average;
    
    constraint asum  == A+B+C+D+E+F+G+H+I+J+K;
    constraint average == asum div 11 /\ asum mod 11 == 0;
    
    constraint is_prime(average);
    
    constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1;
    
    constraint increasing( [A,B,C,D,E,F,G,H,I,J,K]);
    
    solve satisfy;
    
    output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K])
    ++ "\n" ++ "Average = " ++ show(average) ];
    
    % Scores are [101, 131, 151, 181, 191, 313, 353, 373, 383, 787, 919]
    % Average = 353
    % ----------
    % ==========
    
    

    LikeLike

    • 

      GeoffR 9:39 am on 7 June 2024 Permalink | Reply

      Shorter code, but still slow.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Eleven cricket scores
      var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D;
      var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H;
      var 100..999:I; var 100..999:J; var 100..999:K; 
       
      constraint all_different([A,B,C,D,E,F,G,H,I,J,K]);
      
      var 100..999:average;
       
      predicate is_pr_pal(var int: x) = 
       x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
       ((i < x) -> (x mod i > 0)) /\ x div 100 == x mod 10;
       
      constraint sum([is_pr_pal(A), is_pr_pal(B),is_pr_pal(C), is_pr_pal(D),
       is_pr_pal(E), is_pr_pal(F), is_pr_pal(G), is_pr_pal(H),
       is_pr_pal(I), is_pr_pal(J), is_pr_pal(K)]) == 11;
         
      constraint average == (A+B+C+D+E+F+G+H+I+J+K) div 11
      /\ (A+B+C+D+E+F+G+H+I+J+K) mod 11 == 0;
       
      constraint is_pr_pal(average);
       
      constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1;
       
      constraint increasing( [A,B,C,D,E,F,G,H,I,J,K]);
       
      solve satisfy;
       
      output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K])
      ++ "\n" ++ "Average = " ++ show(average) ];
       
      
      
      

      LikeLike

  • 

    GeoffR 9:57 pm on 6 June 2024 Permalink | Reply

    
    from enigma import is_prime
    from itertools import combinations
    
    scores = [x for x in range(100,999) if is_prime(x) \
              if x // 100 == x % 10 ]
    
    for s in combinations(scores, 11):
        av, r = divmod(sum(s), 11)
        if r != 0: continue
        if av in scores and av //100 == av % 10:
            print(f"Average = {av}")
            print(f"Scores = {s}")
    

    LikeLike

    • 

      Ruud 10:20 am on 7 June 2024 Permalink | Reply

      You can leave out the av // 100 == av % 10 test in the final if condition, as that’d guaranteed by the membership of scores.

      LikeLike

  • 

    Frits 10:17 am on 7 June 2024 Permalink | Reply

    Same number of iteratons. It also works if scores would have had exactly 11 items.

    from itertools import combinations
    
    # prime numbers from 101-999
    P = [3, 5, 7]
    P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
    P = [x for x in range(101, 1000, 2) if all(x % p for p in P)]
    # 3-digit palindromic primes
    scores = {p for p in P if p // 100 == p % 10}
    assert (ln := len(scores)) >= 11
    
    t = sum(scores)
    
    # choose scores outside the 11
    for ss in combinations(scores, ln - 11):
      # calculate the average
      avg, r = divmod(t - sum(ss), 11)
      # which is also in scores
      if r or avg not in scores: continue
      print("answer", sorted(scores.difference(ss))[-2:])     
    

    LikeLike

• 

  Jim Randell 4:48 pm on 2 June 2024 Permalink | Reply
  Tags: by: W A Thatcher ( 13 )   

  Brain-Teaser 443: Space ship 

  From The Sunday Times, 2nd November 1969 [link]

  Says Bell at the pub:

  I’ve been reading about a space ship. They fly the thing round playing the usual Cops and Robbers stuff, but the way they name the crew is interesting. Using A, B, C and so on right up to I, no gaps, they make, once only, every possible pair of different letters; so there’s no AA, BB and so on, and they take no notice of the order in a pair; s0 BC is the same as CB.

  Four, including AD and BC, are on a list of officers and on that list no letter appears more than once. All the rest are just proles but do they have an A initial they call themselves A proles.

  All proles work in shifts with the same number on each shift — not just two shifts; more than that — and at the end of a shift every prole hands over to another whose initials are each one farther on in the alphabet than his own, so AB would hand over to BC. Of course I is followed by A.

  The shifts are picked so that when all shifts have been worked, every prole has been on duty once only.

  Now you tell me who’s on the first shift. I want the biggest possible list. Easier than it looks. Usual prize. One pint.

  Which A proles, if any, are on the first shift?

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

  [teaser443]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell is discussing. Toggle Comments

   
  • 

    Jim Randell 4:48 pm on 2 June 2024 Permalink | Reply

    A manual solution follows from a bit of analysis:

    There are C(9, 2) = 36 names, and 4 officers, so there are 32 proles, which we must form into shifts, and we want the shifts to be as large as possible (and more than 2 of them).

    So we are looking at:

    4 shifts, each of 8 proles; or:
    8 shifts, each of 4 proles

    If we start with a name we can consider the successor names until we get back to where we started, which forms the names into 4 groups:

    AB → BC → CD → DE → EF → FG → GH → HI → AI (→ AB) [adjacent letters]
    AC → BD → CE → DF → EG → FH → GI → AH → BI (→ AC) [separated by 1 letter (or 6)]
    AD → BE → CF → DG → EH → FI → AG → BH → CI (→ AD) [separated by 2 letters (or 5)]
    AE → BF → CG → DH → EI → AF → BG → CH → DI (→ AE) [separated by 3 letters (or 4)]

    Any officer (in bold) must be preceded by a member of the final shift and working backwards gives us members of previous shifts, giving a chain that is 8 long, which consists of 1 member for each of 8 shifts, or 2 members for each of 4 shifts.

    Each officer must appear in a different group, and as we have used ABCD, we must choose 2 officers from EFGHI.

    In the final group only EI is available to be an officer, so the remaining officer must be FH in the second group.

    And so we can construct 4 shifts, each of 8 proles:

    shift 4: (AB, EG, CI, DH) + (FG, AC, EH, DI)
    shift 3: (AI, DF, BH, CG) + (EF, BI, DG, CH)
    shift 2: (HI, CE, AG, BF) + (DE, AH, CF, BG)
    shift 1: (GH, BD, FI, AE) + (CD, GI, BE, AF)

    (And the two halves could be split to make 8 shifts, each of 4 proles = (1b, 2b, 3b, 4b, 1a, 2a, 3a, 4a)).

    Solution: AE and AF are on the first shift.

    ---

    Here is a program that performs the same steps:

    It runs in 64ms. (Internal runtime is 351µs).

    from enigma import (
      irange, subsets, diff, tuples, repeat, join,
      intersect, disjoint_union, cache, printf
    )
    
    # letters
    letters = "ABCDEFGHI"
    
    # construct possible crew names
    names = list(x + y for (x, y) in subsets(letters, size=2))
    
    # constrict successor names
    adj = dict(tuples(letters, 2, circular=1))
    succ = cache(lambda xs: join((adj[x] for x in xs), sort=1))
    
    # group names into successor chains
    def group(names):
      while names:
        # make the chain for the next name
        g = list(repeat(succ, names[0], 8))
        yield g
        names = diff(names, g)
    
    # collect groups
    gs = list(group(names))
    
    # choose an officer from each group
    def officers(gs, offs=[]):
      # are we done?
      if not gs:
        yield offs
      else:
        g = gs[0]
        # AD and BC are officers
        xs = intersect([{'AD', 'BC'}, g])
        if not xs:
          # choose officers that don't include ABCD
          xs = list(x for x in g if not intersect(['ABCD', x]))
        # process the candidates
        for x in xs:
          offs_ = offs + [x]
          if disjoint_union(offs_):
            yield from officers(gs[1:], offs_)
    
    # choose the officers
    for offs in officers(gs):
      # find the first shift
      shift = set()
      for (g, off) in zip(gs, offs):
        j = g.index(off)
        shift.update(g[(j + i) % 9] for i in [-4, -8])
      shift = sorted(shift)
      # output shifts 1-4
      for k in irange(1, 4):
        printf("shift {k} = {shift}", shift=join(shift, sep=" "))
        if k == 4: break
        # hand on to the next shift
        shift = list(succ(x) for x in shift)
    

    LikeLike

• 

  Jim Randell 4:36 pm on 31 May 2024 Permalink | Reply
  Tags: by: Howard Williams ( 44 )   

  Teaser 3219: Number funnel 

  From The Sunday Times, 2nd June 2024 [link] [link]

  Betty, being a keen mathematician, has devised a game to improve her children’s maths additions. She constructed an inverted triangular tiling of hexagonal shapes, with nine hexagons in the top row, eight in the second row etc., reducing to one at the bottom. Then, completing the top row with 0s and 1s, she asks them to complete each row below by adding in each hexagon shape the numbers in the two hexagons immediately above it.

  In the last game she noticed that if the top row is considered as a base-2 [binary] number, then this is exactly four and a half times the bottom total.

  What is the bottom total?

  [teaser3219]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  GeoffR, Hugo, Jim Randell, and 3 others are discussing. Toggle Comments

   
  • 

    Jim Randell 4:50 pm on 31 May 2024 Permalink | Reply

    If we suppose that the top row must have at least one of each binary digit present, then a single answer is found.

    This Python program runs in 64ms. (Internal runtime is 986µs).

    from enigma import (irange, tuples, repeat, nsplit, ediv, peek, printf)
    
    # process a row
    process = lambda ns: list(x + y for (x, y) in tuples(ns, 2))
    
    # consider possible start row values (must be a multiple of 9)
    for n in irange(0, 511, step=9):
      # this is 4.5 times the target
      t = ediv(n * 2, 9)
      # perform the process
      top = nsplit(n, 9, base=2)
      bot = peek(repeat(process, top, 8), 8)
      if bot == [t]:
        # output solution
        printf("{n} -> {t}; {top} -> {bot}")
    

    Solution: The final total is 102.

    The initial row is the binary representation of 4.5 × 102 = 459, which gives the following rows:

    (1, 1, 1, 0, 0, 1, 0, 1, 1)
    (2, 2, 1, 0, 1, 1, 1, 2)
    (4, 3, 1, 1, 2, 2, 3)
    (7, 4, 2, 3, 4, 5)
    (11, 6, 5, 7, 9)
    (17, 11, 12, 16)
    (28, 23, 28)
    (51, 51)
    (102)

    LikeLike

    • 

      Ruud 7:56 pm on 31 May 2024 Permalink | Reply

      This my version

      from istr import istr
      
      for s9 in istr.concat(istr.product((0, 1), repeat=9)):
          as_binary = int(s9, 2)
          if as_binary % 4.5 == 0:
              target = int(as_binary / 4.5)
              s = s9[:]
              while len(s) > 1:
                  s = [i + j for i, j in zip(s, s[1:])]
              if s[0] == target:
                  print(f'from {s9} to {target}')
      

      LikeLike

    • 

      NigelR 11:11 am on 1 June 2024 Permalink | Reply

      No external dependencies and a recursive approach for the shapes. I started at the high end for the top row and worked down as it might have been faster if I’d stopped once a valid solution was found. As it is, it makes no difference but it confirms a unique solution.

      #return bottom row from top row r
      def blox(r):
        #are we at the bottom row?
        if len(r)==1: return r
        #find the next row down
        else: return blox(nxt(r))
      
      #return next row down from list of current row
      nxt = lambda r: [(r[i]+r[i+1]) for i in range(0,len(r)-1)]
      
      #top row must be less than 512 and divisible by 9
      for top in range (504,0,-9):
        r1 = [int(y) for y in format(top,'09b')]
        #have we found a solution?
        if (bot:=blox(r1)[0])*9/2 == top:
            print(f"top row was {top}, bottom row was {bot}")
      

      LikeLike

  • 

    Jim Randell 4:51 pm on 1 June 2024 Permalink | Reply

    Here is a solution based on a bit of analysis:

    We have:

    9 × (final value) = 2 × (binary interpretation of top row)

    And we can write each of these in terms of the 0,1 values in the top row.

    So we can extract the coefficients of these top row values in the equation:

    (9 × (final value)) − (2 × (binary interpretation of top row)) = 0

    Some of them are positive, and some of them are negative. (And it turns out there are 2 negative values and 7 positive values).

    So we assign 0,1 values to the variables in the top row with negative coefficients (there are only 3 interesting cases), and then try to express the resulting value using the 0,1 quantities of the positive values.

    We can address this manually, or programatically.

    The following program has an internal runtime of 250µs, so it is slightly faster (although more complicated) than just applying the procedure to each of the possible top row values:

    from enigma import (irange, nCr, subsets, dot, express, nconcat, printf)
    
    # we have: 9 * (final value) = 2 * (binary representation)
    
    # calculate coefficients in the final value (= pascal_row(8))
    pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
    pr8 = pascal_row(8)
    lhs = tuple(9 * x for x in pr8)
    
    # calculate coefficients in the binary representation
    rhs = tuple(2**n for n in irange(9, 1, step=-1))
    
    # calculate coefficients in <lhs> - <rhs> = 0
    cs = tuple(a - b for (a, b) in zip(lhs, rhs))
    
    # collect indices for positive and negative values
    jps = sorted((j for (j, x) in enumerate(cs) if x > 0), key=cs.__getitem__)
    jns = list(j for (j, x) in enumerate(cs) if x < 0)
    
    # things we could work around, but don't need to
    assert not (len(jns) > len(jps))
    assert len(jps) + len(jns) == len(cs)
    assert len(set(cs[j] for j in jps)) == len(jps)
    
    # the positive and negative values
    ps = list(cs[j] for j in jps)
    ns = list(cs[j] for j in jns)
    
    # choose 0,1 values for the negative values
    for vs in subsets((0, 1), size=len(jns), select='M'):
      # calculate total for the negative values
      t = -dot(vs, ns)
      # express the same total using the positive values
      for qs in express(t, ps, qs=[0, 1]):
        # construct top row
        top = [None] * 9
        for (j, v) in zip(jns, vs): top[j] = v
        for (j, v) in zip(jps, qs): top[j] = v
        # output solution
        n = nconcat(top, base=2)
        bot = dot(top, pr8)
        printf("{top} {n} -> {bot}")
    

    ---

    Manually:

    We are looking to solve:

    −503a + −184b + 124c + 440d + 598e + 488f + 244g + 68h + 7i = 0

    The coefficients are all different, so we can uniquely identify a 0,1 valued variable with the corresponding coefficient.

    This boils down to choosing two subsets such that:

    sum(choose({503, 184})) = sum(choose({598, 488, 440, 244, 124, 68, 7}))

    There is a trivial solution where an empty set is chosen on both sides.

    Otherwise we have:

    LHS = 184 → not possible.
    LHS = 503 → not possible
    LHS = 184 + 503 = 687 → RHS = 488 + 124 + 68 + 7 = 687

    The final case corresponds to: a = 1, b = 1, c = 1, d = 0, e = 0, f = 1, g = 0, h = 1, i = 1.

    And so the top row is (1, 1, 1, 0, 0, 1, 0, 1, 1) and the bottom row is (102).

    LikeLike

    • 

      Frits 5:42 pm on 2 June 2024 Permalink | Reply

      I needed to print the variables to see understand the method.
      I had forgotten that “dot” stands for “vector product”.

      Thanks for the “key=cs.__getitem__” construct. I didn’t know that.

      LikeLike

      • 

        Jim Randell 10:27 am on 3 June 2024 Permalink | Reply

        @Frits: dict has the get() function which makes the equivalent look neater for dictionaries:

        # sort keys by value
        ks = sorted(d.keys(), key=d.get)
        

        Or I suppose you could use [[ key=(lambda i: seq[i]) ]] for sequences.

        LikeLike

    • 

      Frits 11:19 pm on 2 June 2024 Permalink | Reply

      @Jim, is there a reason why express() doesn’t support negative quantities? The code would have been more compact.

      LikeLike

      • 

        Jim Randell 8:02 am on 3 June 2024 Permalink | Reply

        @Frits: Allowing negative quantities should be possible, but in general there is no guarantee of termination if non-positive denominations are used in [[ express() ]].

        It feels like solving an integer equation where the variables take on (0, 1) values could have a specialised solver (I think an ILP solver would work). But I used [[ express() ]] in this instance to save having to write one.

        LikeLike

      • 

        Frits 12:38 pm on 3 June 2024 Permalink | Reply

        A minimal modification to Enigma’s express_quantities() is sufficient to make this program work (assuming the denominations are ordered). I don’t see how this subroutine can keep running without terminating.

        from enigma import (irange, nCr, dot, nconcat, printf)
        
        # express total <t> using denominations <ds>, quantities chosen from <qs>
        def express_quantities(t, ds, qs, ss=[]):
          if any(x for x in ss) and t == 0:
            if not ds:
              yield ss
            elif 0 in qs:
              yield ss + [0] * len(ds)
          elif ds:
            d = ds[0]
            for q in qs:
              if d * q > t: break
              for r in express_quantities(t - d * q, ds[1:], qs, ss + [q]): yield r
         
        # we have: 9 * (final value) = 2 * (binary representation)
         
        # calculate coefficients in the final value (= pascal_row(8))
        pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
        pr8 = pascal_row(8)
        lhs = tuple(9 * x for x in pr8)
         
        # calculate coefficients in the binary representation
        rhs = tuple(2**n for n in irange(9, 1, step=-1))
         
        # calculate coefficients in <lhs> - <rhs> = 0
        cs = tuple(a - b for (a, b) in zip(lhs, rhs))
        
        # express the same total using the positive values
        for top in express_quantities(0, cs, qs=[0, 1]):
          # construct top row
          # output solution
          n = nconcat(top, base=2)
          bot = dot(top, pr8)
          
          printf("{top} {n} -> {bot}")
        

        LikeLike

        • 

          Jim Randell 11:20 am on 4 June 2024 Permalink | Reply

          @Frits: But you asked about express() not express_quantities().

          Think about expressing a value using denominations of (-1, 0, +1) where you can use as many of each as you like.

          Of course with finite sets of denominations and quantities there is only a finite number of possible arrangements.

          LikeLike

    • 

      Jim Randell 3:27 pm on 4 June 2024 Permalink | Reply

      Or, using a single call to express():

      from enigma import (irange, nCr, express, nconcat, dot, printf)
      
      # solve the binary equation: sum(n[i] * x[i]) = 0, for x[i] in [0, 1]
      # return the sequences of binary x[] values
      def solve(ns):
        # collect the coefficients (all different absolute values)
        m = dict()  # value -> index
        ts = set()  # set of negative values
        for (i, n) in enumerate(ns):
          assert n != 0  # coefficients must be non-zero
          k = abs(n)
          if n < 0: ts.add(k)
          m[k] = i
        ds = sorted(m.keys())
        assert len(ds) == len(ns)  # coefficients must all be different
        # express the sum of the negative values using 0,1 quantities
        for qs in express(sum(ts), ds, qs=[0, 1]):
          # return the values in the required order
          xs = [None] * len(ns)
          for (d, q) in zip(ds, qs):
            xs[m[d]] = (1 - q if d in ts else q)
          yield xs
      
      # calculate coefficients for the final value (= pascal_row(8))
      pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
      pr8 = pascal_row(8)
      lhs = tuple(9 * x for x in pr8)
      
      # calculate coefficients in the binary representation
      rhs = tuple(2**n for n in irange(9, 1, step=-1))
      
      # calculate coefficients in <lhs> - <rhs> = 0
      ns = tuple(a - b for (a, b) in zip(lhs, rhs))
      
      # solve the 0,1-equation with coefficients <ns> to give the top row
      for top in solve(ns):
        # output solution
        n = nconcat(top, base=2)
        bot = dot(pr8, top)
        printf("{top} {n} -> {bot}")
      

      LikeLike

  • 

    Hugo 2:12 pm on 9 June 2024 Permalink | Reply

    If the numbers in the top row are a, b, c, d, e, f, g, h, i,
    then the value at the bottom has coefficients as given by the appropriate row of Pascal’s triangle: a + 8b + 28c + 56d + 70e + 56f + 28g + 8h + i.
    An exhaustive search is still needed, but my program (in Basic) found a solution immediately.

    This puzzle opens up the possibility of a whole family of puzzles, with factors other than 4.5. There could also be a different number of digits in the top row.

    Where do Jim’s negative values come from? The top row contains only 0s and 1s; each subsequent row is formed by addition, never subtraction.

    A further puzzle for me is Frits’ mention of dot for a vector product.
    I don’t speak Python, but normally dot is for a scalar product and cross for a vector product.

    LikeLike

  • 

    Hugo 8:48 am on 10 June 2024 Permalink | Reply

    I see now what Jim was doing: equating nine times the value of the bottom number and twice the value of the binary number, 256a + 128b + 64c + 32d + 16e + 8f + 4g + 2h + i.
    The mental leap was too much for me! I had evaluated them separately.

    LikeLike

  • 

    GeoffR 3:16 pm on 12 June 2024 Permalink | Reply

    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 0..1:a; var 0..1:b; var 0..1:c;
    var 0..1:d; var 0..1:e; var 0..1:f;
    var 0..1:g; var 0..1:h; var 0..1:i;
    
    var 1..512:top;
    var 1..512:btm;
    
    % top is abcdefghi in binary
    constraint top == a*pow(2,8) + b*pow(2,7) + c*pow(2,6)
    + d*pow(2,5) + e*pow(2,4) + f*pow(2,3) + g*pow(2,2) + h*2 + i;
    
    % 9th row Pascal Triangle coefficients
    constraint btm == a + 8*b + 28*c + 56*d + 70*e + 56*f + 28*g + 8*h + i;
    
    constraint 9 * btm == 2 * top;
    
    solve satisfy;
    
    output[ "Top row = " ++ show(top) ++
    "\n" ++ "Bottom row = " ++ show(btm)];
    
    % Top row = 459
    % Bottom row = 102
    % ----------
    % ==========
    
    
    

    LikeLike

  • 

    GeoffR 4:15 pm on 14 June 2024 Permalink | Reply

    I tried this teaser with ChatGPT trying to find a solution. Despite several hints, it failed, as we have experienced previously.

    I have been experimenting using AI to write poetry in recent months, so I tried a poem for this teaser by feeding the teaser description as a prompt for the poem for ChatGPT. to generate a poem.

    It worked well – poem below:

    The Hexagon Puzzle – ST 3219
    =====================
    A Poem by ChatGPT

    In Betty’s realm, where numbers dance,
    A game of wit and math’s advance,
    Hexagons align in rows so neat,
    A challenge for young minds to meet.

    From nine at the top, they descend,
    Each row a puzzle to comprehend,
    Zeros and ones adorn the crest,
    A binary code, a numeric test.

    With eager eyes, her children trace,
    The patterns woven in this maze,
    Adding the pairs above with care,
    Unveiling sums, a secret to share.

    And as they reach the final row,
    A revelation starts to glow,
    The top row’s binary, a key so bright,
    Unlocks the bottom’s total, a wondrous sight.

    Four and a half times, the answer lies,
    A mathematical truth that never dies,
    In Betty’s game, where numbers reign,
    Hexagons persist, and minds retain.

    LikeLike

• 

  Jim Randell 11:05 am on 30 May 2024 Permalink | Reply
  Tags: by: Victor Bryant ( 143 )   

  Brainteaser 1318: May I repeat? 

  From The Sunday Times, 6th December 1987 [link]

  In this letters-for-digits puzzle, as usual, different letters consistently replace different digits. I have thought of a two-digit number and worked out a fraction (in its lowest form) involving my number. The recurring decimal which I get consists of infinite repeats, i.e.:

  ? / MY = 0. REPEAT REPEAT …

  What is the value of PART?

  [teaser1318]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Frits, Ruud, Jim Randell, and 2 others are discussing. Toggle Comments

   
  • 

    Jim Randell 11:06 am on 30 May 2024 Permalink | Reply

    This solution uses the [[ farey() ]] function from the enigma.py library, which generates co-prime pairs (i.e. the numerator and denominator of a fraction in its lowest terms), and then uses the [[ recurring() ]] function to determine the representation of the fraction as a recurring decimal.

    It runs in 131ms. (Internal runtime is 55ms).

    from enigma import (farey as coprime_pairs, recurring, format_recurring as fmt, printf)
    
    # consider fractions a/b
    for (a, b) in coprime_pairs(98):
      # b is 2 different digits
      if b < 10 or b % 11 == 0: continue
      # check repetend
      (i, nr, rr) = recurring(a, b)
      if nr or len(rr) != 6 or rr[1] != rr[3]: continue
      rs = set(rr)
      if len(rs) != 5 or rs.intersection(str(b)): continue
      # output solution
      PART = rr[2] + rr[4] + rr[0] + rr[5]
      printf("PART = {PART} [{a}/{b} = {f}]", f=fmt((i, nr, rr)))
    

    Solution: PART = 8015.

    The required fraction is:

    5/39 = 0.(128205)…

    LikeLike

    • 

      Jim Randell 8:56 pm on 30 May 2024 Permalink | Reply

      Here’s my solution based on the observation:

      (MY / k) × REPEAT = 999999

      (Although I don’t assume k is a single digit number).

      It runs in 66ms. (Internal runtime is 502µs).

      from enigma import (irange, divisor_pairs, gcd, nsplit, join, printf)
      
      # (MY / k) * REPEAT = 999999
      
      # MY is a 2-digit divisor of 999999
      for (MY, r) in divisor_pairs(999999):
        if MY < 10 or MY % 11 == 0: continue
        if MY > 99: break
        # REPEAT is some multiple of r
        for k in irange(1, MY - 1):
          if gcd(k, MY) > 1: continue
          REPEAT = k * r
          ds = nsplit(REPEAT, 6)
          if ds[1] != ds[3]: continue
          ss = set(ds)
          if len(ss) != 5 or ss.intersection(nsplit(MY)): continue
          # output solution
          PART = join(ds[i] for i in (2, 4, 0, 5))
          printf("PART = {PART} [{k}/{MY} = 0.({REPEAT:06d})...]")
      

      LikeLike

      • 

        Frits 11:27 am on 31 May 2024 Permalink | Reply

        Nice. Indeed, MY must be a divisor of 999999.

        LikeLike

  • 

    GeoffR 2:09 pm on 30 May 2024 Permalink | Reply

    
    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 1..9:R; var 0..9:E; var 0..9:P; var 0..9:A;
    var 0..9:T; var 1..9:X; var 1..9:M; var 0..9:Y;
    
    constraint all_different([R,E,P,A,T,M,Y]);
    
    var 10..99:MY == 10*M + Y;
    var 100000..999999:REPEAT == 100000*R + 10100*E + 1000*P + 10*A + T;
    var 1000..9999:PART == 1000*P + 100*A + 10*R + T;
    
    % function ex Hakan Kjellerstrand 
    function var int: gcd(var int: x, var int: y) =
      let {
        int: p = min(ub(x),ub(y));
        var 1..p: g;
        constraint
           exists(i in 1..p) (
              x mod i = 0 /\ y mod i = 0
              /\
              forall(j in i+1..p) (
                 not(x mod j = 0 /\ y mod j = 0)
              ) /\ g = i);
      } in g;
      
    constraint gcd(X, MY) == 1;
    
    % As X/MY = 0.REPEATREPEAT..
    % Multiplying both sides by 1,000,000 gives..
    constraint 999999 * X == MY * REPEAT;
    
    solve satisfy;
    
    output ["PART = " ++ show(PART) ++ "\n"
    ++ "REPEAT = " ++ show(REPEAT) ++ "\n"
    ++ "X, MY =" ++ show([X, MY])];
    
    % PART = 8015
    % REPEAT = 128205
    % X, MY =[5, 39]
    % ----------
    % ==========
    
    

    LikeLike

  • 

    Frits 6:41 pm on 30 May 2024 Permalink | Reply

    Following GeoffR’s method.

     
    from enigma import divisor_pairs
    
    # 999999 * X == MY * REPEAT 
    for X in range(1, 10):
      LHS = 999999 * X
     
      #  fraction X / MY is in its lowest form
      for MY, REPEAT in [(str(x), str(y)) for x, y in divisor_pairs(LHS)
                         if 9 < x < 100 and (x % X or X == 1)]:
        # letter E                 
        if REPEAT[1] != REPEAT[3]: continue
        # different letters
        if len(set(MY + REPEAT)) != 7: continue
       
        print(f"answer: {REPEAT[2]}{REPEAT[4]}{REPEAT[0]}{REPEAT[5]}")
    

    LikeLike

    • 

      Frits 11:15 am on 31 May 2024 Permalink | Reply

      I did assume a 1-digit question mark. Line 9 should have been:
      if 9 < x < 100 and gcd(x, X) == 1]:

      LikeLike

  • 

    Ruud 6:33 am on 31 May 2024 Permalink | Reply

    Brute force with istr:

    from istr import istr
    
    for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
        if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
            print(f"{m|y} / {r|e|p|e|a|t}")
    

    LikeLike

    • 

      Ruud 6:50 am on 31 May 2024 Permalink | Reply

      Improved prints:

      from istr import istr
      
      for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
          if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
              print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} =  0.{r | e | p | e | a | t}...")
              print(f"part = {p | a | r | t}")
      

      LikeLike

    • 

      Jim Randell 8:40 am on 31 May 2024 Permalink | Reply

      @Ruud: How does this program ensure the fraction (?/MY) is in lowest terms?

      LikeLiked by 1 person

      • 

        Ruud van der Ham 10:26 am on 31 May 2024 Permalink | Reply

        Ok, no guarantee.
        Better would be to do

        
        for m, y, r, e, p, a, tin istr.permutations(istr.digits(), 7):
            if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
                print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} =  0.{r | e | p | e | a | t}...")
                print(f"part = {p | a | r | t}")
                break
        

        Although my original code also just result in one solution.
        Alth

        LikeLike

• 

  Jim Randell 11:11 am on 28 May 2024 Permalink | Reply
  Tags: by: Keith Austin ( 6 )   

  Brainteaser 1351: Letters find the largest 

  From The Sunday Times, 24th July 1988 [link]

  Each letter stands for one of the two digits 1 and 2.

  TEN is larger than SIX, which is larger than TWO, which is larger than ONE.

  NINE is larger than FIVE, which is larger than FOUR, which is larger than ZERO.

  EIGHT is larger than SEVEN, which is larger than THREE.

  Which is the larger in each of the following pairs?

  (a) ELEVEN and NINETY;
  (b) TWENTY and EIGHTY;
  (c) FIFTY and SIXTY;
  (d) SEVENTY and HUNDRED;
  (e) EIGHTY and NINETY?

  [teaser1351]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell and Ruud are discussing. Toggle Comments

   
  • 

    Jim Randell 11:11 am on 28 May 2024 Permalink | Reply

    Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

    It runs in 80ms. (Internal runtime of the generated program is 122µs).

    #! python3 -m enigma -rr
    
    SubstitutedExpression
    
    --digits="1,2"
    --distinct=""
    
    "TEN > SIX"
    "SIX > TWO"
    "TWO > ONE"
    
    "NINE > FIVE"
    "FIVE > FOUR"
    "FOUR > ZERO"
    
    "EIGHT > SEVEN"
    "SEVEN > THREE"
    
    --answer="(ELEVEN < NINETY, TWENTY < EIGHTY, FIFTY < SIXTY, SEVENTY < HUNDRED, EIGHTY < NINETY)"
    --template=""
    

    Solution: We have:

    NINETY > ELEVEN
    EIGHTY > TWENTY
    FIFTY > SIXTY
    SEVENTY > HUNDRED
    NINETY > EIGHTY

    The following letters have fixed values:

    E=2, F=2, G=2, H=1, I=2, N=2, O=1, S=2, T=2, V=1, W=1, X=1, Z=1

    And the letters D, L, R, U, Y can take on either value, and give rise to the 32 possible assignments.

    So:

    NINETY = 22222? > 2?2122 = ELEVEN
    EIGHTY = 22212? > 21222? = TWENTY
    FIFTY = 2222? > 2212? = SIXTY
    SEVENTY = 221222? > 1?2??2? = HUNDRED
    NINETY = 22222? > 22212? = EIGHTY

    LikeLike

  • 

    Ruud 3:51 pm on 28 May 2024 Permalink | Reply

    Brute force solution:

    from collections import defaultdict
    from istr import istr
    
    answers = defaultdict(set)
    for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
        if t | e | n > s | i | x > t | w | o > o | n | e:
            if n | i | n | e > f | i | v | e > f | o | u | r > z | e | r | o:
                if e | i | g | h | t > s | e | v | e | n > t | h | r | e | e:
                    answers["a"].add(("ninety", "eleven")[e | l | e | v | e | n > n | i | n | e | t | y])
                    answers["b"].add(("eighty", "twenty")[t | w | e | n | t | y > e | i | g | h | t | y])
                    answers["c"].add(("sixty", "fifty")[f | i | f | t | y > s | i | x | t | y])
                    answers["d"].add(("hundred", "seventy")[s | e | v | e | n | t | y > h | u | n | d | r | e | d])
                    answers["e"].add(("ninety", "eighty")[e | i | g | h | t | y > n | i | n | e | t | y])
    
    for letter, answer in answers.items():
        print(f"{letter}) {answer}")
    

    LikeLike

    • 

      Jim Randell 4:49 pm on 28 May 2024 Permalink | Reply

      I get:

      TypeError: tuple indices must be integers or slices, not istr
      

      LikeLike

      • 

        Ruud 5:05 pm on 28 May 2024 Permalink | Reply

        @Jim Randell
        Sorry, I forgot to tell that you need istr 1.0.7 to run this code.

        LikeLike

        • 

          Jim Randell 10:17 pm on 28 May 2024 Permalink | Reply

          @Ruud: Thanks. It works with the new version of istr.

          LikeLike

  • 

    Ruud 8:19 am on 29 May 2024 Permalink | Reply

    As some ‘Spielerei’, I did refactor my original istr-version.
    It uses n2w module to convert ints to ‘spoken’ strings. With that and a helper function, I can formulate all the comparison statements as ints, which make more compact code.

    A bit (?) overengineered, maybe …

    from collections import defaultdict
    from istr import istr
    import n2w  # this module can convert an integer to a 'spoken' string
    from functools import reduce, lru_cache
    
    
    @lru_cache
    def convert(number):
        """just as n2w.convert, but 100 is treated differenr]t as n2w.convert(100) is 'one hundred'"""
        return "hundred" if number == 100 else n2w.convert(number)
    
    
    def a(number):
        """translates an int into an istr, using the global variables that define the letter value"""
        return reduce(lambda x, y: x | globals()[y], convert(number), istr(""))
    
    
    def largest(number0, number1):
        return (convert(number1), convert(number0))[a(number0) > a(number1)]
    
    
    answers = defaultdict(set)
    for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
        if a(10) > a(6) > a(2) > a(1):
            if a(9) > a(5) > a(4) > a(0):
                if a(8) > a(7) > a(3):
                    answers["a"].add(largest(11, 90))
                    answers["b"].add(largest(80, 20))
                    answers["c"].add(largest(60, 50))
                    answers["d"].add(largest(100, 70))
                    answers["e"].add(largest(90, 80))
    
    for letter, answer in answers.items():
        print(f"{letter}) {answer}")
    

    LikeLike

  • 

    Jim Randell 10:09 am on 29 May 2024 Permalink | Reply

    All comparisons are between values of the same length, so we don’t need to convert the values into numbers, we can just use lexicographic ordering.

    This Python program uses integer keys to refer to the words, but considers the values of the words with all 2^18 possible assignments of symbols, so is much slower than my solution using the [[ SubstitutedExpression ]] solver.

    from enigma import (union, subsets, join, printf)
    
    # words we are interested in (use numbers as short keys)
    words = {
      10: 'TEN', 6: 'SIX', 2: 'TWO', 1: 'ONE',
      9: 'NINE', 5: 'FIVE', 4: 'FOUR', 0: 'ZERO',
      8: 'EIGHT', 7: 'SEVEN', 3: 'THREE', 50: 'FIFTY', 60: 'SIXTY',
      11: 'ELEVEN', 90: 'NINETY', 20: 'TWENTY', 80: 'EIGHTY',
      70: 'SEVENTY', 100: 'HUNDRED',
    }
    
    # answers we need to find (which is larger?)
    qs = [(11, 90), (20, 80), (50, 60), (70, 100), (80, 90)]
    
    # collect symbols used
    syms = sorted(union(words.values()))
    
    # collect answers
    ans = set()
    # assign the symbols to values
    for vs in subsets('12', size=len(syms), select='M'):
      m = dict(zip(syms, vs))
      # map the words to values
      w = dict((k, join(m[x] for x in v)) for (k, v) in words.items())
      # check the conditions
      if (w[10] > w[6] > w[2] > w[1] and w[9] > w[5] > w[4] > w[0] and w[8] > w[7] > w[3]):
        # accumulate answers
        ans.add(tuple(max(a, b, key=w.get) for (a, b) in qs))
    
    # output solution
    for ks in ans:
      for (q, k) in zip("abcde", ks):
        printf("({q}) {k}", k=words[k])
      printf()
    

    LikeLike

• 

  Jim Randell 4:31 pm on 24 May 2024 Permalink | Reply
  Tags: by: Stephen Hogg ( 63 )   

  Teaser 3218: Algorithm Al 

  From The Sunday Times, 26th May 2024 [link] [link]

  On his 35th birthday, maths teacher Al’s three younger half-sisters bought him “The Book of Numbers for Nerds” as a tease. It showed how to find right-angle triangles with whole-number sides using any two unequal odd square numbers. You take half their sum; half their difference; and the square root of their product to get the three sides. Any multiple of such a triplet would also work. He told his sisters this and that their ages were the sides of such a triangle. “Algorithm Al!” they yelled.

  Knowing the age of any one sister would not allow you to work out the other ages with certainty, but in one case you could be sure of her place chronologically (youngest, middle or oldest).

  Give the three sisters’ ages (youngest to oldest).

  [teaser3218]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Frits and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 5:33 pm on 24 May 2024 Permalink | Reply

    (See also: Teaser 3017).

    The construction of primitive Pythagorean triples in this way is known as Euclid’s formula [@wikipedia].

    This program collects Pythagorean triples with sides less than 35, and looks for triangles where all sides appear in more than one candidate triangle.

    Of the selected triangles we look for a side that can only appear in one specific position in the ordering (again, considering all candidate triangles). And this identifies the required answer.

    It runs in 63ms. (Internal runtime is 193µs).

    from enigma import (
      defaultdict, pythagorean_triples, multiset, singleton, icount, printf
    )
    
    # collect possible triangles
    tris = list(pythagorean_triples(34))
    
    # record positions of each side
    d = defaultdict(multiset)
    for tri in tris:
      for (i, x) in enumerate(tri):
        d[x].add(i)
    
    # check a candidate triangle
    def check_tri(tri):
      # each side must appear in multiple triangles
      if not all(d[x].size() > 1 for x in tri): return
      printf("tri = {tri}; all sides occur in multiple triangles")
      # look for sides that can only appear in a single position
      for x in tri:
        k = singleton(d[x].distinct_elements())
        if k is not None:
          printf("-> {x} only appears in pos {k}")
          yield (x, k)
    
    # check triangles, exactly one side appears in a single position
    for tri in tris:
      if icount(check_tri(tri)) == 1:
        printf("=> SOLUTION: ages = {tri}")
    

    Solution: The three ages are: 15, 20, 25.

    There are just five primitive triangles we are interested in:

    euclid(1, 3) = (3, 4, 5)
    euclid(1, 5) = (5, 12, 13)
    euclid(1, 7) = (7, 24, 25)
    euclid(3, 5) = (8, 15, 17)
    euclid(3, 7) = (20, 21, 29)

    Candidate triangles are formed from these, along with multiples such that the largest side does not exceed 34.

    And the only candidate triangles where every side length occurs in another triangle are:

    (12, 16, 20) = (3, 4, 5) × 4
    (15, 20, 25) = (3, 4, 5) × 5

    And of these sides only 25 always appears as the largest side length:

    (7, 24, 25)
    (15, 20, 25)

    LikeLike

  • 

    Frits 5:55 pm on 24 May 2024 Permalink | Reply

    Following the instructions.

     
    sols = set()
    # odd squares
    osqs = [i * i for i in range(1, 68, 2)]
    for i, a in enumerate(osqs):
      if a > 33: break
      for b in osqs[i + 1:]:
        # calculate sister's ages
        p = (a + b) // 2
        if p > 34: break
        q = abs(a - b) // 2
        r = int((a * b) ** .5)
        # allow for multiples
        for k in range(1, 35):
          if any(x > 34 for x in [k * p, k * q, k * r]): break
          sols.add(tuple(sorted([k * p, k * q, k * r])))
    
    sides = set(y for x in sols for y in x)
    # dictionary of age appearing as y/m/o
    d = {s: [sol.index(s) for sol in sols if s in sol] for s in sides}
    
    # group of sisters that qualify
    gs = [sol for sol in sols if all(len(d[s]) > 1 for s in sol)]
    for sisters in gs:
      if sum([len(set(d[s])) == 1 for s in sisters]) == 1:  # in one case ...
        print("answer:", sisters)   
    

    LikeLike

• 

  Jim Randell 8:59 am on 21 May 2024 Permalink | Reply
  Tags: by: R Postill ( 20 )   

  Brain-Teaser 350: Catering crisis 

  From The Sunday Times, 21st January 1968 [link]

  The caterer at our Village Hall is in a quandary, as the Hall has been double-booked for next Saturday — by the Cricket Club and the Darts Club.

  Unfortunately the matter cannot be resolved until the return of the Vicar on Saturday morning. He is quite unpredictable in such decisions, and the caterer must order the food by Friday.

  The Cricketers want 100 sausage rolls and 60 meat pies; the Darts Club wants 50 sausage rolls and 90 meat pies.

  The caterer is empowered to spend exactly £6.00. He buys sausage rolls at 3p and sells at 4p; meat pies cost him 5p and sell at 8p. Any left-overs are disposed of at a loss to a local prep school, which pays 2p per sausage roll and 3p a pie.

  What should the caterer order so that he makes the best safe profit no matter which club gets the booking? And what will that profit be?

  This puzzle is included in the book Sunday Times Brain Teasers (1974). The puzzle text is taken from the book.

  [teaser350]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell, Frits, and Lise Andreasen are discussing. Toggle Comments

   
  • 

    Jim Randell 8:59 am on 21 May 2024 Permalink | Reply

    This Python program looks at possible orders of sausage rolls and pies that cost the caterer exactly 600p, and then the amount made if these supplies are available for each club, and records the minimum profit made in each case. We then look for the largest of these profits to find the answer to the puzzle.

    It runs in 58ms. (Internal runtime is 240µs).

    from enigma import (Accumulator, express, printf)
    
    # amount earned for supply <s>, demand <d>, price <p>, disposal price <x>
    def amount(s, d, p, x):
      return (d * p + (s - d) * x if s > d else s * p)
    
    # calculate amount earned for a supply (s, p) and a demand (S, P)
    # of sausage rolls and pies
    def earned(s, p, S, P):
      return amount(s, S, 4, 2) + amount(p, P, 8, 3)
    
    # find the maximum profit
    r = Accumulator(fn=max, collect=1)
    
    # the caterer spends 600p
    for (s, p) in express(600, [3, 5]):
      # calculate amount earned from each club
      C = earned(s, p, 100, 60)
      D = earned(s, p, 50, 90)
      # record profit
      r.accumulate_data(min(C, D), (s, p, C - 600, D - 600))
    
    # output solution
    for (s, p, C, D) in r.data:
      printf("{s} sausages rolls + {p} pies -> cricket = {C} / darts = {D}")
    

    Solution: The caterer should order 80 sausage rolls and 72 pies. Whichever club arrives he will make a profit of 236p.

    ---

    In the originally published puzzle pre-decimal currency was used and the numbers were different:

    The Cricketers want 200 sausage rolls and 120 meat pies; the Darts Club wants 100 sausage rolls and 180 meat pies.

    The caterer is empowered to spend exactly £5 [= 1200 pence].

    And the answer is: 160 sausage rolls, 144 pies. The profit is 472 pence = £1, 19s, 4d.

    LikeLike

    • 

      Frits 10:35 am on 21 May 2024 Permalink | Reply

      This program doesn’t assume that the caterer will spend exactly 600p.

         
      from enigma import SubstitutedExpression, Accumulator
      
      # invalid digit / symbol assignments
      d2i = dict()
      # try to spend close to 600p in order to maximize the profit
      for dgt in range(0, 101):
        vs = set()
        if dgt < 50: vs.update('S')
        if dgt < 60: vs.update('P')
        if dgt > 90: vs.update('P')
        d2i[dgt] = vs
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          # expenditure close to the maximum
          "595 < S * 3 + P * 5 <= 600",
          # calculate profits for cricketers and darters
          "(pc := S + min(P, 60) * 3 - (P - 60) * 2 * (P > 60))",
          "(pd := min(S, 50) + P * 3 - (S - 50) * 1 * (S > 50))",
        ],
        answer="min(pc, pd), S, P",
        base=101,
        d2i=d2i,
        distinct="",
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # find the maximum profit
      r = Accumulator(fn=max).accumulate_from(ans for (_, ans) in p.solve())
      
      # output solution
      w, s, p = r.value
      print(f"he should order {s} sausages and {p} pies for a profit of {w}p")
      

      LikeLike

      • 

        Frits 10:32 am on 22 May 2024 Permalink | Reply

        Assuming that the caterer will spend exactly 600p and that the caterer will order a sensible amount of sausages S (50, 55, 60, …, 95, 100) the profit (if the cricketers get the booking) can be expressed as: 2.2 * S + 60 and 460 – 2.8 * S if the darters get the booking.

        As the first function is increasing and the latter is decreasing for S the safe profit will be maximized if 2.2 * S + 60 = 460 – 2.8 * S or S = 80.

        LikeLiked by 1 person

  • 

    Lise Andreasen 2:17 am on 22 May 2024 Permalink | Reply

    Interesting.

    I approached it differently and arrived at 100 sausage rolls and a profit of 280.

    https://onlinephp.io/c/47cce

    LikeLike

    • 

      Lise Andreasen 2:23 am on 22 May 2024 Permalink | Reply

      Oh, hang on. Read the puzzle incorrectly.

      LikeLike

      • 

        Lise Andreasen 2:25 am on 22 May 2024 Permalink | Reply

        Yeah. I get the correct result now.

        https://onlinephp.io/c/37baa

        LikeLike

      • 

        Lise Andreasen 2:27 am on 22 May 2024 Permalink | Reply

        Read the numbers in an early version of this page?

        LikeLike

    • 

      Jim Randell 12:44 pm on 24 May 2024 Permalink | Reply

      Sorry. For a short while the numbers were mixed up between the original puzzle and the version published in the book. The puzzle text now reflects the version from the book, rather than the originally published version.

      LikeLike

• 

  Jim Randell 8:04 am on 19 May 2024 Permalink | Reply
  Tags: by: Oliver Anderson ( 3 )   

  Brainteaser 1315: The nineteenth hole 

  From The Sunday Times, 15th November 1987 [link]

  A famous English mathematician, J.E. Littlewood, once posed the following puzzle:

  Find a number N (sensibly the smallest) such that, if you shift the first digit to the end, the result is exactly one-and-a-half times N.

  The solution to this being:

  N = 1,176,470,588,235,294.

  Professor Egghead has discovered a similar intriguing fact (not in his bath, nor sitting under a fruit-tree; but while relaxing in the club-house, after a round of golf). It is:

  A smallest positive integer, M, such that, if one again shifts the leading digit to the end, the result is, this time, exactly just one half of M.

  How many digits has M?

  [teaser1315]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Frits and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 8:11 am on 19 May 2024 Permalink | Reply

    See: Puzzle #180, Enigma 653, Enigma 924, Teaser 2565, Enigma 1036, Enigma 455, Enigma 1161 (but note these may reveal the answer to this puzzle).

    Normally a parasitic number [ @wikipedia ] involves multiplying the number by a(n integer) value by moving the final digit to the front.

    This puzzle moves the front digit to the end, so we are looking at the inverse of the process involved in parasitic numbers. So if we find a 2-parasitic number, we can start with it, move the front digit (back) to the end, and it is divided by 2.

    For this Python program I adapted my [[ parasitic() ]] function from Enigma 924 to deal with fractional multipliers, and this allows us to solve both problems mentioned in the puzzle text.

    This program runs in 59ms. (Internal runtime is 167µs).

    from enigma import (irange, inf, div, ndigits, first, printf)
    
    # find numbers such that moving the final digit to the front
    # result in a multiplication of the original number by k/q
    def parasitic(k, q=1, M=inf, base=10):
      assert k < q * base and q < k * base
      b = base * k - q
    
      # consider n digit numbers
      for n in irange(1, M):
        a = base**n * q - k
        m = base**(n - 1)
        # consider non-zero digits d
        for d in irange(1, base - 1):
          x = div(d * a, b)
          if x is not None and m * base > x >= m:
            yield base * x + d
    
    # find numbers such that moving the first digit to the end
    # result in a multiplication of the original number by p/q
    # this is the same as finding a (q/p)-parasitic number
    for (p, q) in [(3, 2), (1, 2)]:
      # find the lowest number
      for x in first(parasitic(q, p), 1):
        n = div(x * q, p)
        # output solution
        printf("[{p}/{q}] {n} * {p}/{q} = {x} [{k} digits]", k=ndigits(n))
    

    Solution: M has 18 digits.

    The smallest number is 210526315789473684.

    210526315789473684 × 1/2 = 105263157894736842

    Note that this is the repetend of 4/19 = 0.(210526315789473684)…

    If you don’t mind leading zeros we can apply the same procedure to the result (which also has 18 digits), to get:

    105263157894736842 × 1/2 = 052631578947368421

    See also: OEIS A337922, OEIS A146088.

    LikeLike

  • 

    Frits 3:24 pm on 19 May 2024 Permalink | Reply

      
    # k-digit number n = fp = 2(10p + f) with 19p = (10^(k - 1) - 2)f
    # 19p = a999...999b with a = f - 1 and b = 10 - 2f
    
    for k in range(2, 99):
      for f in range(2, 6):
        # check for a multiple of 19
        if (p19 := f * 10**(k - 1) - 2 * f) % 19: continue
        s19 = str(p19)
        a = str(f - 1)
        b = str(10 - 2 * f)
        
        if s19[1:-1] == "9" * (k - 2) and (s19[0], s19[-1]) == (a, b):
          print("answer:", k)
          break
      else:
        continue
      break   
    

    LikeLike

• 

  Jim Randell 4:33 pm on 17 May 2024 Permalink | Reply
  Tags: by: Danny Roth ( 86 )   

  Teaser 3217: Peace in rest 

  From The Sunday Times, 19th May 2024 [link] [link]

  George and Martha regularly read the obituaries in the national press; as well as the date of death, the date of birth of the person discussed is always shown. “That is interesting!” commented Martha as she looked at the three obituaries displayed one morning. Two of them have palindromic dates of birth (e.g., 13/11/31, 21/6/12). “Very unlikely, indeed!” agreed George.

  Assuming that birth dates are expressed as day (1-31), month (1-12) year (00-99), what is the probability of a palindromic birth date in the 20th century (1900 to 1999 inclusive), and will it be greater, equal or less in the 21st century?

  [teaser3217]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Pete Good and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 4:50 pm on 17 May 2024 Permalink | Reply

    Technically the dates of the 20th century are 1st January 1901 – 31st December 2000, but that is not the convention followed in this puzzle. We are interested in the 19xx years and the 20xx years.

    The answer to the second part of the puzzle comes from a fairly straightforward observation.

    However, here is a constructive solution, that counts the palindromic dates in years 19xx and 20xx (assuming the calendar continues as expected, and that birth dates are uniformly distributed).

    There are two ways we can check for palindromes, with or without the separators in the dates. In the following I am assuming that we only check the digits of the date, but the separators can be included at line 11 if required (although this changes the number of palindromic dates found).

    from datetime import (date, timedelta)
    from enigma import (repeat, inc, is_palindrome, rdiv, compare, printf)
    
    # return fraction of palindromic dates in years <a> - <b>
    def pal(a, b):
      p = t = 0
      for d in repeat(inc(timedelta(days=1)), date(a, 1, 1)):
        if d.year > b: break
        t += 1
        # look for palindromic dates
        s = d.strftime("%-d%-m%y")
        if is_palindrome(s): p += 1
      r = rdiv(p, t)
      printf("{a}..{b} -> {p}/{t} = {r}")
      return r
    
    # calculate fractions for years 19xx and 20xx
    (P19, P20) = (pal(1900, 1999), pal(2000, 2099))
    r = compare(P20, P19, vs=['less than', 'equal to', 'more than'])
    printf("P(20xx) {r} P(19xx)")
    

    Solution: The proportion of palindromic dates in the years 1900 – 1999 is 7/794. In the years 2000 – 2099 there will be a (slightly) smaller proportion of palindromic dates.

    In each of the 19xx and 20xx years there are a total of 322 palindromic dates. (Each palindromic date can refer to a 19xx date and a 20xx date).

    However, as the year 1900 was not a leap year and the year 2000 was, there is 1 less day in the 19xx years, and so there is a higher proportion of palindromes compared to the 20xx years.

    Note, that if we use the actual definition of 20th and 21st centuries (1901 – 2000 and 2001 – 2100) the result is reversed, as the leap day in 2000 is included in the earlier period.

    ---

    Manually, we can count the number of palindromic dates in a 100 year period by considering the following constructions:

    x/y/yx → x = 1..9, y = 1..9 ⇒ 9×9 = 81 dates
    xy/z/yx → xy = 10..31, z = 1..9 ⇒ 22×9 = 198 dates
    x/yz/yx → x = 1..9, yz=10..12 ⇒ 9×3 = 27 dates
    xy/zz/yx → xy = 10..31, zz=11 ⇒ 22×1 = 22 dates

    For a grand total of 81 + 198 + 27 + 22 = 328 dates.

    However not all of these dates are valid, as some months don’t have 31 days. So we can remove the following invalid dates:

    30/2/03
    31/2/13
    31/4/13
    31/6/13
    31/9/13
    31/11/13

    (Note that: 29/2/92 is a valid date).

    And that leaves 322 palindromic dates in a century.

    We can also count the total number of days in a century:

    There are 365×100 = 36500 non-leap days, plus the number of leap days.

    There are 24 leap years per century, plus an extra one when the year is divisibly by 400. So 2000 was a leap year, but 1900 was not.

    Hence, there are 24 leap days in the years 1900..1999, and 25 in the years 2000..2099.

    The proportions are:

    P(1900..1999) = 322/36524 = 7/794 ≈ 0.881612%
    P(2000..2099) = 322/36525 ≈ 0.881588%

    So the proportion of palindromic dates in the years 2000..2099 is slightly smaller than the proportion in the years 1900..1999.

    LikeLike

  • 

    Pete Good 4:54 pm on 18 May 2024 Permalink | Reply

    Jim, I tried to run this program in Windows (using the Microsoft Visual Studio environment) but it generates the error INVALID FORMAT STRING because %-d and %-m are not supported by Microsoft. I am therefore hoping that my own C++ program has produced the correct solution!

    LikeLike

    • 

      Jim Randell 5:26 pm on 18 May 2024 Permalink | Reply

      Yes, I think this format is a glibc extension to strftime(). (Although it looks like Windows might use %# instead of %- to suppress zero padding).

      But in Python 3 you can replace line 11 with:

      s = f"{d.day}{d.month}{d.year % 100:02d}"
      

      (which also seems to be faster).

      or more generally:

      s = str.format("{d}{m}{y:02d}", d=d.day, m=d.month, y=d.year % 100)
      

      LikeLike

  • 

    Pete Good 5:44 pm on 18 May 2024 Permalink | Reply

    Thanks Jim, both of your suggestions work fine in Visual Studio and the program generated the same solution as my C++ program.

    LikeLike

• 

  Jim Randell 8:04 am on 16 May 2024 Permalink | Reply
  Tags: by: Angela Newing ( 38 )   

  Teaser 2615: Gunpowder, treason and plot 

  From The Sunday Times, 4th November 2012 [link] [link]

  Last year I overheard this conversation one day during the first seven days of November:

  Alec: It’s the 5th today, let’s have a bonfire.
  Bill: No, the 5th is tomorrow.
  Chris: You’re both wrong — the 5th is the day after tomorrow.
  Dave: All three of you are wrong.
  Eric: Yesterday was certainly not the 1st.
  Frank: We’ve missed bonfire night.

  If you knew how many of their statements were true, then you could work out the date in November on which this conversation took place.

  What was that date?

  In Britain, Bonfire night is 5th November.

  [teaser2615]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  GeoffR, Lise Andreasen, Frits, and 1 other are discussing. Toggle Comments

   
  • 

    Jim Randell 8:05 am on 16 May 2024 Permalink | Reply

    A straightforward puzzle to solve, either manually or programatically.

    This Python program evaluates the statements on each of the 7 possible days, and looks for situations where the number of true statements uniquely identifies a single day.

    from enigma import (irange, group, seq2str, printf)
    
    # calculate statement values for date <d>
    def statements(d):
      # A: "It is the 5th today ..."
      A = (d == 5)
      # B: "The 5th is tomorrow ..."
      B = (d + 1 == 5)
      # C: "The 5th is the day after tomorrow ..."
      C = (d + 2 == 5)
      # D: "A, B, C are all wrong ..."
      D = not (A or B or C)
      # E: "Yesterday was not the 1st ..."
      E = (d - 1 != 1)
      # F: We have missed bonfire night (the 5th) ..."
      F = (d > 5)
      return [A, B, C, D, E, F]
    
    # group dates by the number of true statements
    g = group(irange(1, 7), by=(lambda d: statements(d).count(True)))
    
    # look for groups with a single member
    for (k, vs) in g.items():
      if len(vs) == 1:
        printf("{k} true -> {vs} November", vs=seq2str(vs, sort=1, enc=""))
    

    Solution: The conversation took place on 2nd November.

    There is only 1 true statement, and it is made by Dave.

    LikeLike

  • 

    Frits 10:31 am on 16 May 2024 Permalink | Reply

    # the number of correct statements 
    fn = lambda d: sum([d == 5, d == 4, d == 3, d < 3 or d > 5, d != 2, d > 5])
     
    seen, sols = set(), dict()
    # now find a count that is unique
    for d in range(1, 8):
      if (c := fn(d)) in seen:
        try:
          del sols[c]
        except KeyError:
          pass
      else:
        sols[c] = str(d)  
        seen.add(c)  
        
    print(f"answer: November {' or '.join(sols.values())}")
    

    LikeLike

  • 

    Lise Andreasen 7:06 pm on 16 May 2024 Permalink | Reply

    T = the date today.
    A: T = 5.
    B: T = 4.
    C: T = 3.
    D: T != 3, 4, 5.
    E: T != 2.
    F: T = 6 v T = 7.
    Of A, B, C and D, 1 is true, 3 are false.
    There can therefore be 1, 2 or 3 true statements.
    With 3 true statements, both E and F are true. T could be 6 or 7.
    With 2 true statements, either E or F is true. If E is true, T = 2. If F is true, T could be 1, 3, 4 or 5.
    With 1 true statement, both E and F are false. T = 2. This is the only option leading to 1 answer. Therefore there was 1 true statement and it’s 2nd November.

    LikeLike

  • 

    GeoffR 1:54 pm on 17 May 2024 Permalink | Reply

    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 1..7: T; % Date conversation took place
    
    % A - F statements
    constraint sum([T==5, T==4, T==3, T!=3 \/ T!=4 \/ T!=5,
    T!=2, T==6 \/ T==7]) == 1;
    
    solve satisfy;
    
    output [" T = " ++ show(T)];
    
    % T = 2;
    %---------
    %=========
    
    
    

    LikeLike

• 

  Jim Randell 10:16 am on 14 May 2024 Permalink | Reply
  Tags: by: B T Izzard ( 2 )   

  Brain-Teaser 950: Magic moments 

  From The Sunday Times, 5th October 1980 [link]

  Joe decided to utilise the garden see-saw to demonstrate the principles of balance, and of moments to, his family. Alf, Bert, Charlie, Doreen, Elsie and Fiona weighed 100, 80, 70, 60, 50 and 20 kilos respectively. The seesaw had three seats each side, positioned 1, 2 and 3 metres from the centre.

  They discovered many ways of balancing using some or all of the family.

  In one particular combination, with at most one person on each seat, one of the family not on the seesaw observed that the sum of the moments of all of the people on the seesaw was a perfect square.

  “That’s right”, said Joe, “but, as you can see, it doesn’t balance — and what’s more, there’s nowhere you can sit to make it balance”.

  “Wrong”, was the reply. “I could sit on someone’s lap”.

  “True,” said Joe, “but only if you sit at the end”.

  Which two would then be sitting together, and who else, if anyone, would be on the same side of the see-saw?

  [To find the moment due to each person, multiply their distance from the centre by their weight. The sum of the moments on one side should equal the sum of those on the other if balance is to be achieved].

  This puzzle is included in the book The Sunday Times Book of Brainteasers (1994).

  [teaser950]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Frits and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 10:16 am on 14 May 2024 Permalink | Reply

    Participants can be uniquely identified by their weights.

    This Python program finds possible seating arrangements on the see-saw.

    It runs in 72ms. (Internal runtime is 13ms).

    from enigma import (subsets, is_square, div, printf)
    
    # weights and positions
    weights = [100, 80, 70, 60, 50, 20]
    poss = [+1, +2, +3, -1, -2, -3]
    
    # there is at least one member not seated
    for ws in subsets(weights, min_size=2, max_size=len(weights) - 1, select='C'):
      # allocate positions (including +3)
      for ps in subsets(poss, size=len(ws), select='P'):
        if +3 not in ps: continue
        # find the total sum of the moments
        ms = sum(w * abs(p) for (w, p) in zip(ws, ps))
        if not is_square(ms): continue
        # weight required at +3 to balance the see-saw
        x = -sum(w * p for (w, p) in zip(ws, ps))
        w = div(x, +3)
        # is it the weight of a missing person?
        if not (w in weights and w not in ws): continue
        # output solution
        printf("ws={ws} ps={ps} ms={ms} x={x} w={w}")
    

    Solution: Doreen would join Fiona at the end of the see-saw. Elsie is also seated on the same side.

    The seating arrangement is as follows:

    

    Without D the moments are (kg.m):

    L = 70×3 + 80×1 = 290
    R = 20×3 + 50×1 = 110

    They don’t balance, but they do sum to 400 = 20^2.

    With D the moments on the right become:

    R = (20 + 60)×3 + 50×1 = 290

    and the see-saw balances.

    LikeLike

  • 

    Frits 2:26 pm on 14 May 2024 Permalink | Reply

      
    from enigma import express
    from itertools import product
     
    # weights and positions
    weights = [100, 80, 70, 60, 50, 20]
    names = ["Alf", "Bert", "Charlie", "Doreen", "Elsie", "Fiona"]
    
    # possible squares divisible by 10 
    for sq in [100, 400, 900]:
      # decompose square into weights
      for e in express(sq, weights, min_q=0, max_q=3):
        # someone is sitting at the end and one place is empty
        if all(x for x in e) or 3 not in e: continue
        # at most one person on each seat
        if any(e.count(i) > 2 for i in range(1, 4)): continue
       
        # one of the family not on the seesaw to sit at the end on someone's lap
        for i, seat in enumerate(e):
          if seat: continue # not an empty seat
          e1 = e[:i] + [3] + e[i + 1:] 
          
          # multiply elements by 1 or -1 times the weight and 
          # see if they sum to zero
          for prod in product([-1, 1], repeat=len([x for x in e1 if x])):
            if prod[0] > 0: continue    # avoid symmetric duplicates
            # weave in zeroes
            p = list(prod)
            p = [p.pop(0) if x else 0 for x in e1]
            
            # is the seesaw in balance?
            if sum([x * y * weights[i] 
                   for i, (x, y) in enumerate(zip(p, e1))]) != 0: continue
            # new persion must be sitting on someone's lap at the end
            someone = [j for j in range(6) if j != i and e1[j] == 3 and 
                                              p[j] == p[i]]
            if not someone: continue
            print(f"{names[i]} would join {names[someone[0]]}",
                  f"at the end ofthe see-saw.")
            oths = [j for j in range(6) if p[j] == p[i] and 
                                           j not in {i, someone[0]}]
            if not oths: continue
            ns = [names[o] for o in oths]
            oths = ns[0] + " is" if len(oths) == 1 else ' and '.join(ns) + " are"
            print(f"{oths} also seated on the same side.")   
    

    LikeLike

• 

  Jim Randell 4:34 pm on 10 May 2024 Permalink | Reply
  Tags: by: Susan Bricket ( 17 )   

  Teaser 3216: Quel carve-up! 

  From The Sunday Times, 12th May 2024 [link] [link]

  A French farmer’s estate is shaped like a right-angled triangle ABC on top of a square BCDE. The triangle’s hypotenuse is AB, and its shortest side, AC, has length 1 kilometre. Nearing retirement, the farmer decides to sell off the square of land and, obeying the Napoleonic law of succession, divide the triangle into three equal plots, one for each of his two children and a third for him and his wife in retirement. His surveyor discovers, surprisingly, that his remaining triangle of land can be divided neatly into three right-angled triangles, all identical in shape and size (allowing for reflections / rotations).

  How many hectares did the farmer sell?

  (1 hectare = area of 100m × 100m plot).

  [teaser3216]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell is discussing. Toggle Comments

   
  • 

    Jim Randell 5:05 pm on 10 May 2024 Permalink | Reply

    I found it easiest to start from the end:

    For the final dissection we need to find 3 identical right-angled triangles that can fit together to form a triangle.

    It is possible to do this such that the combined triangle is a larger version of the small triangles.

    We can fit three identical (30°, 60°, 90°) triangles together to form a larger (30°, 60°, 90°) triangle as shown.

    

    So this can serve as a dissection of the original triangular plot, and also the farmer’s allocated plot.

    The ratio of the sides in the (30°, 60°, 90°) triangle are 1 : √3 : 2.

    So, if the shortest side has length 1 km, the remaining non-hypotenuse side has length √3 km, and this is the same as the side of the square plot.

    Hence the square plot has an area of 3 km², and there are 100 hectares per square kilometre:

    Solution: The farmer sold 300 hectares.

    

    Although this is not the only possible arrangement.

    The first dissection only has to be into 3 equal area triangles (so they don’t have to be identical), so here is another possible arrangement (where the first dissection can be made by dividing BC into three equal parts):

    

    LikeLike

• 

  Jim Randell 7:33 pm on 9 May 2024 Permalink | Reply
  Tags: by: Robin Nayler ( 16 )   

  Teaser 2610: Odd ages 

  From The Sunday Times, 30th September 2012 [link] [link]

  Recently Alex, Bernard and Charles were comparing their ages in years. Alex’s age was an odd two-digit number and Bernard’s age was a whole number percentage more than that. On the other hand, Charles’s age was also an odd two-digit number but Bernard’s age was a whole number percentage less than that. They were surprised to find that the percentage was the same in both cases.

  What were their three ages?

  [teaser2610]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  GeoffR, Frits, and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 7:34 pm on 9 May 2024 Permalink | Reply

    Supposing the 3 are all different ages (so the percentage is non-zero).

    A’s age is an odd 2-digit number, and C’s age is a (larger) odd 2-digit number, and so B’s age is between them, hence also a 2-digit number.

    For percentage p we have:

    A (100 + p) / 100 = B
    C (100 − p) / 100 = B
    ⇒
    p = 100 (C − A) / (C + A)

    The following Python program runs in 67ms. (Internal runtime is 463µs).

    from enigma import (irange, subsets, div, printf)
    
    # ages for A and C (2-digit, odd)
    for (A, C) in subsets(irange(11, 99, step=2), 2):
      # calculate percentage
      p = div(100 * (C - A), C + A)
      if p is None: continue
      # calculate B
      B = div(A * (100 + p), 100)
      if B is None: continue
      # output solution
      printf("A={A} B={B} C={C} [p={p}%]")
    

    Solution: Alex is 15. Bernard is 21. Charles is 35.

    And the percentage in question is 40%:

    15 + 40% = 15 × (1 + 0.4) = 21
    35 − 40% = 35 × (1 − 0.4) = 21

    LikeLike

  • 

    Frits 10:06 am on 10 May 2024 Permalink | Reply

    for a in range(11, 100, 2):
      # determine valid percentages, maximum percentage = (99 - 12) / 99 = 0.87878
      for p in [p for p in range(2, 88, 2) if (p * a) % 100 == 0]:
        b = a + (p * a) // 100
        c, r = divmod(100 * b, 100 - p)
        if c > 99: break
        if r or c % 2 == 0: continue
        print("answer:", (a, b, c))     
    

    LikeLike

  • 

    GeoffR 10:35 am on 10 May 2024 Permalink | Reply

    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 11..99:A; var 11..99:B; var 11..99:C;
    var 1..95:p; % Percentage
    
    constraint all_different([A, B, C]);
    constraint sum([A mod 2 == 1, B mod 2 == 1, C mod 2 == 1]) == 3;
    constraint 100*A + p*A == 100*B;
    constraint 100*C - p*C == 100*B;
    
    solve satisfy;
    
    output["[Alex, Bernard, Charles] = " ++ show([A, B, C]) ];
     
    % [Alex, Bernard, Charles] = [15, 21, 35]
    % ----------
    % ==========
    
    
    

    LikeLike

• 

  Jim Randell 3:02 pm on 7 May 2024 Permalink | Reply
  Tags: by: Des MacHale ( 11 )   

  Teaser 2617: A case of ambiguity 

  From The Sunday Times, 18th November 2012 [link] [link]

  Every schoolchild knows that it is possible for two triangles to have two of their lengths-of-sides in common and one of their angles in common without the two triangles being identical or “congruent”.

  This can happen when the common angle is not included between the two common sides. I have found such a pair of non-congruent triangles with all the lengths of the sides being a whole number of centimetres and with the longest side of each triangle being 10cm in length.

  What are the lengths of the other two sides of the smaller triangle?

  [teaser2617]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  GeoffR, Jim Randell, and Frits are discussing. Toggle Comments

   
  • 

    Jim Randell 3:02 pm on 7 May 2024 Permalink | Reply

    Each triangle has a longest side of 10, so the remaining two sides must be 1 – 9, so there aren’t that many triangles to consider.

    This Python program considers the side lengths of possible triangles and uses the cosine rule to calculate the internal angles, and then looks for two different triangles that share an angle.

    It runs in 72ms. (Internal runtime is 664µs).

    from enigma import (fraction as Q, irange, intersect, call, cache, printf)
    
    # return values as cosines (using cosine rule)
    cosA = lambda x, y, z: Q(y*y + z*z - x*x, 2*y*z)
    
    # find the angles of a triangle with sides x, y, z
    @cache
    def _angles(x, y, z):
      # is it a valid triangle?
      if x + y > z:
        return {cosA(x, y, z), cosA(y, z, x), cosA(z, x, y)}
    angles = lambda *ss: call(_angles, sorted(ss))
    
    # choose the shared side a
    for a in irange(1, 9):
      # choose the shorter remaining side b
      for b in irange(1, 8):
        angles1 = angles(a, b, 10)
        if not angles1: continue
        # choose the longer remaining side c
        for c in irange(b + 1, 9):
          angles2 = angles(a, c, 10)
          if not angles2 : continue
          # check for a common angle
          if intersect([angles1, angles2]):
            # output solution
            printf("({a}, {b}, 10) -> {angles1}; ({a}, {c}, 10) -> {angles2}")
    

    Solution: The other two sides of the smaller triangle are: 4cm and 8cm.

    The triangles look like this:

    

    And the common angle α is acos(13/20) ≈ 49.46°.

    LikeLike

  • 

    Frits 5:46 pm on 7 May 2024 Permalink | Reply

    We also have 10^2 – 8^2 = 4 * 9.

    See (here).

    LikeLike

    • 

      Jim Randell 4:41 pm on 8 May 2024 Permalink | Reply

      This result follows directly from using the cosine rule on the shared angle of both triangles:

      Suppose the base of the triangle is d, and we can make two triangles with the same angle α using sides b, a and c, a.

      Then, using the cosine rule on both triangles:

      cos(α) = (d² + b² − a²)/2db = (d² + c² − a²)/2dc
      ⇒
      c(d² + b² − a²) = b(d² + c² − a²)
      (c − b)(d² − a²) − bc(c − b) = 0
      (c − b)(d² − a² − bc) = 0
      [b ≠ c] ⇒
      bc = d² − a² = (d − a)(d + a)

      Which gives a straightforward program:

      from enigma import (irange, divisors_pairs, printf)
      
      d = 10
      for a in irange(1, d - 1):
        for (b, c) in divisors_pairs(d*d - a*a):
          if b < c < d:
            printf("triangles = ({d}, {a}, {b}) ({d}, {a}, {c})")
      

      LikeLike

  • 

    GeoffR 6:37 pm on 8 May 2024 Permalink | Reply

    
    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 1..9:A; var 1..9:B; var 1..9:C;
    int: D == 10;  % Two triangles are ABD and ACD
    
    constraint B * C == D * D - A * A;
    constraint B < C /\ C < D;
    
    solve satisfy;
    output ["Two triangles are " ++ show([A,B,D]) ++ " and " ++ show([A,C,D]) ];
    
    % Two triangles are [8, 4, 10] and [8, 9, 10]
    % ----------
    % ==========
    
    

    LikeLike

• 

  Jim Randell 12:29 pm on 5 May 2024 Permalink | Reply
  Tags: by: G H Dickson ( 13 ), flawed ( 54 )   

  Brain-Teaser 748: [Cutting corners] 

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

  Young Bob had been given a carpentry set and with it a rectangular board (whose diagonal measured less than 1½ metres) on which to practise using his saw.

  With straight cuts of successively greater length and aggregating to an exact number of metres, he first proceeded to saw dissimilar triangular pieces off each corner of the board in turn, the remaining quadrilateral piece being put aside for another day.

  All the 12 sides of the sawn-off pieces measured exact and different numbers of centimetres.

  What were the length and width of the board? (in cms).

  As set this puzzle has multiple solutions, however if we interpret “less than 1½ meters” to mean “less than 150 cm, but more than 149 cm”, then we get a unique solution that is the same as that published in the newspaper.

  This puzzle was originally published with no title.

  [teaser748]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Hugo and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 12:30 pm on 5 May 2024 Permalink | Reply

    Perhaps the puzzle originally said “just less than 1½ metres”, but the “just” got lost somewhere.

    The following program assembles pairs of Pythagorean triangles point-to-point. This gives us candidate widths and heights for the board. We then find two pairs with the same width that fit together to make a rectangle as specified.

    By “dissimilar” triangles I am assuming that no pair of triangles is mathematically similar (i.e. none of them are multiples of the same primitive Pythagorean triangle).

    The program runs in 108ms. (Internal runtime is 40ms).

    from enigma import (
      defaultdict, pythagorean_triples, subsets, cproduct,
      seq_all_different, hypot, rev, ordered, ratio, cached, printf
    )
    
    # diagonal limit
    D = 150
    
    # possible triangles (x, y) -> z
    tris = dict(((x, y), z) for (x, y, z) in pythagorean_triples(D - 1))
    
    # primitive triangle
    primitive = cached(lambda t: ratio(*t))
    
    # assemble pairs of triangles: <combined-width> -> (<h1>, <h2>) -> (<w1>, <w2>)
    pairs = defaultdict(lambda: defaultdict(set))
    for (k1, k2) in subsets(tris.keys(), size=2):
      for ((w1, h1), (w2, h2)) in cproduct((k, rev(k)) for k in (k1, k2)):
        w = w1 + w2
        if w < D:
          (k, v) = ((h1, h2), (w1, w2)) if h1 < h2 else ((h2, h1), (w2, w1))
          pairs[w][k].add(v)
    
    # choose a width and height for the initial rectangle
    for (w, h) in subsets(pairs.keys(), size=2):
      z = hypot(w, h)
      if not (D - 1 < z < D): continue
    
      # choose a pair of triangles for the base
      for k1 in pairs[w]:
        (h1, h2) = k1
        # calculate the corresponding matched pair
        k2 = (h4, h3) = (h - h2, h - h1)
        if not (k2 > k1 and k2 in pairs[w]): continue
        for ((w1, w2), (w4, w3)) in cproduct(pairs[w][k] for k in (k1, k2)):
          # assemble the triangles
          (x1, y1, x2, y2, x3, y3, x4, y4) = (h1, w1, w2, h2, h4, w4, w3, h3)
          (z1, z2, z3, z4) = (tris[ordered(x, y)] for (x, y) in [(x1, y1), (x2, y2), (x3, y3), (x4, y4)])
          # sum of cuts is a multiple of 100
          T = z1 + z2 + z3 + z4
          if T % 100 != 0: continue
          # sides are all different
          ts = (t1, t2, t3, t4) = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4))
          if not seq_all_different(t1, t2, t3, t4): continue
          # triangle are dissimilar
          if not seq_all_different(primitive(ordered(*t)) for t in ts): continue
          # output solution
          printf("{w} x {h} -> {z:.2f}; {t1} {t2} {t3} {t4} T={T}")
    

    Solution: The board was: 28 cm × 147 cm.

    And here is how the triangles fit together:

    

    ---

    If we just look for any diagonal that is less than 150cm (which is a direct interpretation of the published puzzle text), then we find the following 23 solutions (ordered by length of diagonal):

    # Z = diagonal; T = total length of cuts
     28 × 147: Z=149.64 (12, 35, 37) (15, 112, 113) (16, 63, 65) (13, 84, 85) T=300
     51 × 140: Z=149.00 (15, 20, 25) (35, 120, 125) (36, 77, 85) (16, 63, 65) T=300
     87 × 120: Z=148.22 (7, 24, 25) (72, 96, 120) (80, 84, 116) (15, 36, 39) T=300
     48 × 140: Z=148.00 (15, 20, 25) (35, 120, 125) (33, 56, 65) (13, 84, 85) T=300
     60 × 135: Z=147.73 (9, 12, 15) (90, 48, 102) (126, 32, 130) (45, 28, 53) T=300
    103 × 105: Z=147.09 (5, 12, 13) (60, 91, 109) (100, 75, 125) (45, 28, 53) T=300
     95 × 112: Z=146.86 (20, 21, 29) (60, 91, 109) (75, 100, 125) (35, 12, 37) T=300
     83 × 120: Z=145.91 (18, 24, 30) (28, 96, 100) (65, 72, 97) (55, 48, 73) T=300
    100 × 105: Z=145.00 (9, 40, 41) (72, 65, 97) (91, 60, 109) (28, 45, 53) T=300
     90 × 112: Z=143.68 (20, 48, 52) (40, 42, 58) (92, 69, 115) (72, 21, 75) T=300
     60 × 129: Z=142.27 (3, 4, 5) (33, 56, 65) (126, 32, 130) (96, 28, 100) T=300
     69 × 124: Z=141.90 (9, 40, 41) (13, 84, 85) (60, 91, 109) (56, 33, 65) T=300
     85 × 111: Z=139.81 (5, 12, 13) (20, 99, 101) (80, 39, 89) (65, 72, 97) T=300
     93 × 104: Z=139.52 (20, 21, 29) (65, 72, 97) (84, 13, 85) (39, 80, 89) T=300
     92 × 104: Z=138.85 (5, 12, 13) (39, 80, 89) (99, 20, 101) (65, 72, 97) T=300
     59 × 124: Z=137.32 (7, 24, 25) (12, 35, 37) (117, 44, 125) (112, 15, 113) T=300
     76 × 114: Z=137.01 (15, 36, 39) (9, 40, 41) (99, 20, 101) (105, 56, 119) T=300
     80 × 111: Z=136.82 (5, 12, 13) (20, 99, 101) (75, 100, 125) (60, 11, 61) T=300
     84 × 108: Z=136.82 (3, 4, 5) (18, 80, 82) (105, 36, 111) (90, 48, 102) T=300
     95 ×  96: Z=135.06 (16, 63, 65) (60, 32, 68) (80, 18, 82) (36, 77, 85) T=300
     93 ×  95: Z=132.94 (11, 60, 61) (56, 33, 65) (84, 13, 85) (39, 80, 89) T=300
     67 ×  72: Z= 98.35 (9, 12, 15) (48, 55, 73) (63, 60, 87) (24, 7, 25) T=200
     56 ×  78: Z= 96.02 (8, 15, 17) (16, 63, 65) (48, 36, 60) (40, 42, 58) T=200
    

    and we see the published solution is the first of these (longest diagonal).

    LikeLike

  • 

    Hugo 3:36 pm on 5 May 2024 Permalink | Reply

    His saw cuts (each of which became the hypotenuse of a triangle) were progressively longer as he moved round the board to each corner in turn. Did you take that into account?

    LikeLike

    • 

      Jim Randell 4:45 pm on 5 May 2024 Permalink | Reply

      I didn’t check that the cut lengths can form an increasing sequence (going clockwise or anticlockwise around the board), as I decided he could just make the four cuts in ascending order, however they are arranged.

      But if you do require this there are still 9 different solutions with diagonals <150 cm (including the published one).

      LikeLike

  • 

    Hugo 7:43 am on 6 May 2024 Permalink | Reply

    I think we can reduce it to a single solution if we add the words
    “The board had the smallest possible area, consistent with what has been said.”

    LikeLike

• 

  Jim Randell 3:34 pm on 3 May 2024 Permalink | Reply
  Tags: by: Andrew Skidmore ( 87 )   

  Teaser 3215: Darts league 

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

  

  In our darts league, each team plays each other once. The result of each match is decided by the number of legs won, and each match involves the same number of legs. If both teams win the same number of legs, the match is drawn. The final league table shows the games won, drawn or lost, and the number of legs won for and against the team. The Dog suffered the most humiliating defeat, winning only one leg of that match. Curiously, no two matches had the same score.

  What was the score in the match between The Crown and The Eagle?

  [teaser3215]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Frits and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 4:30 pm on 3 May 2024 Permalink | Reply

    Each team plays 4 matches and 80 legs, so each match has 20 legs. A and B draw, so their match is 10-10.

    D has a 1-19 match, so the scores in the other matches are between 2 and 18 (excluding 10), which is 16 values distributed between 16 different slots, so each value appears exactly once.

    Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

    The following run file executes in 83ms. (Internal runtime is 4.4ms).

    #! python3 -m enigma -rr
    
    SubstitutedExpression
    
    # suppose the matches (X v Y) and scores for X are:
    #
    #  A v B = Q
    #  A v C = R
    #  A v D = S
    #  A v E = T
    #  B v C = U
    #  B v D = V
    #  B v E = W
    #  C v D = X
    #  C v E = Y
    #  D v F = Z
    
    --base=20 # allow scores of 1-19
    --digits="1-19"
    --code="v = lambda x: 20 - x" # opponent's score
    
    # scores for each match for each team
    --macro="@A = [Q, R, S, T]"
    --macro="@B = [v(Q), U, V, W]"
    --macro="@C = [v(R), v(U), X, Y]"
    --macro="@D = [v(S), v(V), v(X), Z]"
    --macro="@E = [v(T), v(W), v(Y), v(Z)]"
    
    # total legs for each team
    "sum(@A) == 55"  # A
    "sum(@B) == 43"  # B
    "sum(@C) == 37"  # C
    "sum(@D) == 41"  # D
    "sum(@E) == 24"  # E
    
    # A and B drew (10-10)
    --assign="Q,10"
    
    # all matches have different scores
    "seq_all_different(ordered(x, v(x)) for x in [Q, R, S, T, U, V, W, X, Y, Z])"
    
    # D won 1 leg in one game, and this was the worst score
    "1 in { v(S), v(V), v(X), Z }"
    --invalid="1|19,RTUWY"
    
    # won, drawn, lost
    --code="""
    def wdl(ss):
      vs = list(compare(s, 10) for s in ss)
      return (vs.count(1), vs.count(0), vs.count(-1))
    """
    
    "wdl(@A) == (2, 1, 1)"  # A
    "wdl(@B) == (1, 1, 2)"  # B
    "wdl(@C) == (2, 0, 2)"  # C
    "wdl(@D) == (3, 0, 1)"  # D
    "wdl(@E) == (1, 0, 3)"  # E
    
    # answer is the score in CE
    --answer="(Y, v(Y))"
    --template=""
    

    Solution: The score in the Crown vs Eagle match was 16-4.

    There are two possible sets of scores in the matches:

    A v B = 10-10
    A v C = 8-12 / 18-2
    A v D = 19-1
    A v E = 18-2 / 8-12
    B v C = 17-3 / 7-13
    B v D = 9-11
    B v E = 7-13 / 17-3
    C v D = 6-14
    C v E = 16-4
    D v E = 15-5

    LikeLike

    • 

      Frits 2:48 pm on 4 May 2024 Permalink | Reply

      Another idea would be to start the first variables Q, R, S and T with “D vs …” so we can use base=19 and digits=”1-18″.

      LikeLike

  • 

    Frits 7:40 pm on 3 May 2024 Permalink | Reply

     
    # decompose number <t> into <k> increasing numbers (between <mn> and <mx>)
    # so that sum(<k> numbers) equals <t> 
    def decompose(t, k=4, mn=2, mx=19, s=[]):
      if k == 1:
        if s[-1] < t <= mx:
          yield s + [t]
      else:
        for n in range(mn if not s else s[-1] + 1, mx + 1):
          if 2 * k * n + k * (k - 1) > 2 * t: break
          yield from decompose(t - n, k - 1, mn, mx, s + [n])
    
    # general checks
    def check(s, grp):
      s_ = set(s) - {10}
      # all matches have different scores (we have not won/lost from ourselves)
      if any(20 - x in s for x in s_) : return False
      # different scores (except draw)
      if any(s_.intersection(g) for g in grp): return False
      # we have not played more than once against the same opponent
      return all(sum(20 - x in g for x in s) < 2 for g in grp)
    
    sols = set()
    # points for The Dog (three victories)
    for D in decompose(41 - 1, 3, 11):
      D += [1]                       # winning only one leg of that match
      # points for The Anchor
      for A in decompose(55):
        if A[1] != 10: continue                             # A: 2W/1D/1L
        if not check(A, [D]): continue
        # points for Eddy
        for E in decompose(24):
          if 10 in E or E[2] > 10 or E[3] < 11: continue    # E: 1W/3L
          if not check(E, [D, A]): continue
          # points for The Crown
          for C in decompose(37):
            if 10 in C or C[1] > 10 or C[2] < 10: continue  # C: 2W/2L
            if not check(C, [D, A, E]): continue
            # now we know points for The Bull
            B = set(range(1, 20)).difference(D + A + E + C) | {10}
            if not check(B, [D, A, E, C]): continue          
           
            # collect score in the match between The Crown and The Eagle
            for c in C:
              if 20 - c in E:
                sols.add(c)
                
    for c in sols:
      print(f"answer: {c} vs {20 - c}")    
    

    LikeLike

  • 

    Frits 3:04 pm on 5 May 2024 Permalink | Reply

    More compact but less efficient.

     
    from itertools import permutations
    
    # wins/draws/losses
    wdl = lambda s: [w := 4 - (l := sum(x < 10 for x in s)) - (10 in s), 
                     4 - w - l, l]
    v = lambda x: 20 - x    # opponent's score      
    
    AB, AC, AD, AE, DB, DC, DE, EB, EC, BC = [0] * 10
    vars = lambda k: [AB, AC, AD, AE, DB, DC, DE, EB, EC, BC][:k]
    
    # general checks
    def check(t, v3, scores, vs): 
     # check wins/draws/losses
     if wdl([v := t - sum(v3)] + v3) != scores: return False   
     # all matches have different scores
     if (min(ms := set(tuple(sorted([x, 20 - x])) for x in vs + [v])) >= (1, 19)
         and len(set(ms)) == len(vs) + 1): return v
    
    sols = set()
    AB = 10
    for AC, AD in permutations(range(2, 20), 2):
      if not(AE := check(55, [AB, AC, AD], [2, 1, 1], vars(3))): continue
      for DB, DC in permutations(range(1, 19), 2):
        if not(DE := check(41, [v(AD), DB, DC], [3, 0, 1], vars(6))): continue
        if 1 not in {v(AD), DB, DC, DE}: continue   # winning only one leg ...      
        for EB in range(2, 19):
          if not(EC := check(24, [v(AE), v(DE), EB], [1, 0, 3], vars(8))): continue
          if not(check(43, [v(AB), v(DB), v(EB)], [1, 1, 2], vars(9))): continue
          sols.add(EC)
          
    for s in sols:
      print(f"C vs E: {v(s)} - {s}")
    

    LikeLike

• 

  Jim Randell 10:21 am on 2 May 2024 Permalink | Reply
  Tags: by: W A Thatcher ( 13 )   

  Brain-Teaser 553: Grand Vizier 

  From The Sunday Times, 6th February 1972 [link]

  Sever-Nek, the Grand Vizier, was suspicious of the influence which Azi-Muth. the Sultan’s wily tutor, was gaining over his young pupil, and had determined to have him removed, when chance played into his hands.

  The Sultan had a collection of nearly 2,000 small square tiles, all the same size in various colours, and one day to please his tutor had arranged some of them into a square with a pretty central design and a border. Then he announced that he had made two smaller equal squares using the same pieces. “But that is impossible, said Muth, “there must be some left over”.

  There was one over, and Sever-Nek, happening to pass by put his foot over it. “Surely not”, he said. “His Serene Highness has made a most interesting discovery. No doubt the same thing can be done again. Let us add some extra tiles from the box to those already used”. Nothing loath, the Sultan soon produced a larger square from which he almost made two smaller identical squares. This time he was one tile short.

  “Your Serene Highness must have dropped this one on the floor”, said the Grand Vizier, moving his foot. Allow me to complete the design”. The discomfiture of the outwitted tutor was no less complete than his disgrace.

  How many extra tiles were taken from the box to make the larger square?

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

  [teaser553]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  John Crabtree and Jim Randell are discussing. Toggle Comments

   
  • 

    Jim Randell 10:22 am on 2 May 2024 Permalink | Reply

    We can suppose the requirement for a “pretty central design” is to preclude very small squares. I assumed the initial square was at least 5×5.

    This Python program runs in 62ms. (Internal runtime is 399µs).

    from enigma import (irange, inf, sq, is_square, printf)
    
    # record (x, y) where x^2 = 2 y^2 + d for d in [+1, -1]
    ss = { +1: [], -1: [] }
    
    for j in irange(2, inf):
      n = sq(j)
      if n > 1000: break
    
      # look for deltas
      for d in ss.keys():
        i = is_square(2*n + d)
        if i:
          printf("[{d:+d}] {i}^2 = 2x {j}^2 {d:+d}")
          ss[d].append((i, j))
    
    # look for an initial +1, with a size at least 5
    for (x1, y1) in ss[+1]:
      if x1 < 5: continue
      # and a larger -1
      for (x2, y2) in ss[-1]:
        if not (x2 > x1): continue
        # calculate the number of extra tiles (remembering one is hidden)
        d = sq(x2) - sq(x1) + 1
        # output solution
        printf("{d} extra tiles [{x1}^2 = 2 {y1}^2 + 1 -> {x2}^2 = 2 {y2}^2 - 1]")
    

    Solution: 1393 extra tiles were taken to make the larger square.

    The initial square was 17×17 (= 289 tiles), which can be rearranged as two 12×12 squares (= 144 tiles each) with one tile left over (and hidden).

    With an extra 1393 tiles we get a total of 288 + 1393 = 1681 which can be arranged into a 41×41 square.

    The 1681 tiles can also be arranged into two 29×29 squares (= 841 tiles each), except one of them is one tile short, and completed by the hidden tile.

    ---

    If a small initial square is allowed then there is a further solution, starting with a 3×3 square (9 tiles), this is rearranged into two 2×2 squares (8 tiles each), with one tile left over. We can then add 41 extra tiles to make a 7×7 square which can split into two 5×5 squares, one of which requires the hidden tile. (Or an extra 1673 tiles could be added to make two 29×29 squares, as above).

    LikeLike

  • 

    John Crabtree 6:13 pm on 2 May 2024 Permalink | Reply

    The sides of the larger and smaller squares are given in the sequences
    https://oeis.org/A001333 Numerators of continued fraction convergents to sqrt(2), and
    https://oeis.org/A001329 Denominators of continued fraction convergents to sqrt(2).
    Then all one needs to do is to find the side of the biggest larger square < sqrt(2000), ie 41, and work from there.

    LikeLike