Updates from August, 2021 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 6:37 pm on 27 August 2021 Permalink | Reply
    Tags:   

    Teaser 3075: Prime cuts for dinner 

    From The Sunday Times, 29th August 2021 [link] [link]

    Tickets to the club dinner were sequentially numbered 1, 2, …, etc. and every ticket was sold. The number of guests for dinner was the highest common factor of three different two-figure numbers and the lowest common multiple of three different two-figure numbers. There were several dinner tables, each with the same number of seats, couples being seated with friends. The guests on each table added their ticket numbers together and obtained one of two prime numbers, both less than 150, but if I told you the larger prime number you would not be able to determine the other.

    What was the larger of the two prime numbers?

    [teaser3075]

     
    • Jim Randell's avatar

      Jim Randell 7:03 pm on 27 August 2021 Permalink | Reply

      This Python program looks for candidate solutions, but doesn’t show that the tickets can be assigned to tables in the required fashion. However there is only one possible answer, so this is not necessary. (However, it is possible to assign tickets in both cases – see [link]).

      It runs in 234ms.

      from enigma import (mgcd, mlcm, subsets, irange, intersect, divisors_pairs, tri, Primes, express, filter_unique, unpack, printf)
      
      # generate candidate solutions
      def generate():
      
        # primes less than 150
        primes = Primes(150)
      
        # look for gcds and lcms of 3 2-digit numbers
        (gcds, lcms) = (set(), set())
        for ns in subsets(irange(10, 99), size=3):
          gcds.add(mgcd(*ns))
          lcms.add(mlcm(*ns))
      
        # consider number of tickets, n
        for n in intersect([gcds, lcms]):
          # total sum of tickets
          t = tri(n)
          # consider k tables, with q people per table
          for (k, q) in divisors_pairs(n, every=1):
            if k < 3 or q < 3: continue
      
            # consider 2 primes, for the ticket sums
            for (p1, p2) in subsets(primes, size=2):
              # express the total using 2 of the primes
              for (q1, q2) in express(t, (p1, p2), min_q=1):
                if q1 + q2 == k:
                  yield (n, t, k, q, p1, p2, q1, q2)
      
      # look for candidate solutions, where p1 is ambiguous by p2
      ss = filter_unique(
        generate(),
        unpack(lambda n, t, k, q, p1, p2, q1, q2: p2),
        unpack(lambda n, t, k, q, p1, p2, q1, q2: p1),
      )
      
      for (n, t, k, q, p1, p2, q1, q2) in ss.non_unique:
        printf("n={n}: t={t}; {k} tables of {q} people; ({p1}, {p2}) -> ({q1}, {q2})")
      

      Solution: The larger of the two primes was 109.


      There are 30 tickets:

      gcd(30, 60, 90) = 30
      lcm(10, 15, 30) = 30

      And 30 is the only number that satisfies the conditions.

      So the sum of the ticket numbers is T(30) = 465.

      And the tickets can be arranged into 5 tables of 6 people, to give one of two prime sums for each table as follows:

      Table 1: 2, 3, 4, 5, 7, 8; sum = 29
      Table 2: 1, 9, 13, 27, 29, 30; sum 109
      Table 3: 6, 10, 14, 25, 26, 28; sum = 109
      Table 4: 11, 12, 17, 22, 23, 24; sum = 109
      Table 5: 15, 16, 18, 19, 20, 21; sum = 109

      Table 1: 1, 3, 7, 25, 26, 27; sum = 89
      Table 2: 5, 6, 9, 22, 23, 24; sum 89
      Table 3: 8, 10, 11, 19, 20, 21; sum = 89
      Table 4: 12, 13, 14, 15, 17, 18; sum = 89
      Table 5: 2, 4, 16, 28, 29, 30; sum = 109

      In each case the larger prime is 109.

      And there are many ways to achieve the same sums.

      Like

    • GeoffR's avatar

      GeoffR 9:30 am on 31 August 2021 Permalink | Reply

      I programmed this teaser in two stages, first re-using the few lines of Jim’s code to find the intersection of GCD/LCM values to give the number of guests.

      The next stage was to examine possible table arrangements and arrangements of two prime numbers to make up the sum of tickets.

      I also tested different prime number multipliers e.g 4/1 and 3/2 for the 5 table arrangement and 5/1 and 4/2 for the 6 table arrangement.

      
      from itertools import permutations
      from enigma import mgcd, mlcm, subsets, irange, Primes
       
      # primes less than 150
      primes = Primes(150)
       
      # look for 3 No. 2-digit numbers for gcd and lcm values
      gcds, lcms = set(), set()
      for ns in subsets(irange(10, 99), size=3):
        gcds.add(mgcd(*ns))
        lcms.add(mlcm(*ns))
      
      # Numbers of Guests (N)
      N = list(gcds.intersection(lcms))[0]
      print('No. of guests = ', N)   # N = 30
      
      # Ticket sum of numbers for N guests
      T = N * (N + 1)//2
      print('Sum of all ticket numbers = ', T) 
      
      # 30 people - possible table arrangements:
      # - 5 tables of 6 people or 6 tables of 5 people - two possibilities
      # - 2 tables of 15 people or 15 tables of 2 people - not viable
      # - 3 tables of 10 people or 10 tables of 3 people - not viable
      
      # try 5 tables of 6 people, using 2 primes to make sum of tickets
      # results were found for prime multipliers of 4 and 1 
      # no results from 2 and 3 prime multipliers were found
      print('Two possible prime values:')
      for p1, p2 in permutations(primes, 2):
          if 4 * p1 + p2 == T:
              print( (max(p1, p2), min(p1, p2)),  end = "  ")
      
      # (149, 79)  (109, 89)  (101, 61)  (103, 53)  (107, 37)  (109, 29)  (113, 13)
      # There is only maximum prime i.e. 109, where the other prime could not be known.
      # For maximum primes of 149, 101, 103, 107 and 113, the second prime is known.
      
      # try 6 tables of 5 people, using 2 primes make sum of tickets
      for p3, p4 in permutations(primes,2):
          if 5 * p3 + p4 == T:
              print(max(p3, p4), min(p3, p4))        
      # No solution
      
      # No. of guests =  30
      # Sum of all ticket numbers =  465
      # Two possible prime values:
      # (149, 79)  (109, 89)  (101, 61)  (103, 53)  (107, 37)  (109, 29)  (113, 13)
      
      

      This section of code find the two sets of three two digit numbers used by the setter for the HCF/LCM values in this teaser.

      There were 33 numbers in the GCD set of numbers and 25,608 numbers in the LCM set of numbers, with a minimum value of 30 and a maximum value of 941,094. The setter used the minimum LCM value.

      
      # The number of guests for dinner was the highest common
      # factor of three different two-figure numbers and the 
      # lowest common multiple of three different two-figure numbers.
      
      # Q. What were these two sets of three digit numbers?
      
      from itertools import combinations
      
      from math import gcd, lcm
      for x in combinations(range(10, 100), 3):
        a, b, c = x
        if gcd(a, b, c) == 30:
          print(f"Three 2-digit values for HCF = {a}, {b}, {c}")
      
      for x in combinations(range(10, 100), 3):
        d, e, f = x
        if lcm(d, e, f) == 30:
          print(f"Three 2-digit values for LCM = {d}, {e}, {f}")
      
      # Three 2-digit values for HCF = 30, 60, 90
      # Three 2-digit values for LCM = 10, 15, 30
      # Therefore, a value of 30 was used for number of guests.
      
      

      Like

  • Unknown's avatar

    Jim Randell 9:54 am on 26 August 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 840: Cake mix variations 

    From The Sunday Times, 21st August 1977 [link]

    A small party was held to promote a brand of Cake Mix. There were five varieties of cake, five beverages, and five sorts of savouries offered.

    I asked a sample group of five what they had chosen, and learned that each had had a different drink, a different slice of cake and two savouries.

    No one had picked the same two savouries as any other, and no more than two people had the same savoury.

    No one had cake of the same flavour as her beverage (tea being paired with plain sponge in this case).

    Dot told me that she had no coffee in any form, no cheese and no egg, but she did have a sausage roll and one thing with orange flavour.

    Eve had lemon drink, but no egg, and said that the one who had both egg and cheese did not drink coffee, but the tea drinker had cheese nibbles.

    Fran said the one who drank chocolate had lemon cake. Fran had shrimp vol-au-vent, and only one of the shrimp eaters had lemon in either form.

    Gill had a sausage roll and one orange item, and said that the one who had cheese had chocolate cake.

    Helen told me that the one who had coffee cake had a ham sandwich, but no cheese, and no one had stuffed egg as well as shrimp.

    Who had the ham sandwiches ?

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

    [teaser840]

     
    • Jim Randell's avatar

      Jim Randell 9:55 am on 26 August 2021 Permalink | Reply

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

      It runs in 81ms.

      #! python3 -m enigma -rr
      
      # assign values to the names:
      #   Dot = 1; Eve = 2; Fran = 3; Gill = 4; Helen = 5
      #
      # and then assign these values to the comestibles:
      #   cakes: sponge = A; coffee = B; orange = C; lemon = D; chocolate = E
      #   drinks: tea = F; coffee = G; orange = H; lemon = I; chocolate = J
      #   savouries: cheese = K & L; egg = M & N; s roll = P & Q; shrimp = R & S; ham s = T & U
      
      SubstitutedExpression
      
      --digits="1-5"
      --distinct="ABCDE,FGHIJ,KMPRT,LNQSU,AF,BG,CH,DI,EJ,KL,MN,PQ,RS,TU"
      
      # remove duplicate solutions
      "T < U"
      
      # "Dot has no coffee, no cheese, no egg"
      "B != 1"
      "G != 1"
      "K != 1"
      "L != 1"
      "M != 1"
      "N != 1"
      
      # "Dot has a sausage roll, and something orange"
      "P == 1 or Q == 1"
      "C == 1 or H == 1"
      
      # "Eve had lemon drink"
      "I == 2"
      
      # "Eve had no egg"
      "M != 2"
      "N != 2"
      
      # "someone had egg, cheese and not coffee"
      "((M == K or M == L) and G != M) or ((N == K or N == L) and G != N)"
      
      # "tea drinker had cheese"
      "F == K or F == L"
      
      # "hot chocolate had lemon cake"
      "J == D"
      
      # "Fran had shrimp"
      "R == 3 or S == 3"
      
      # "only one shrimp eater also had lemon"
      "(R == D or R == I) + (S == D or S == I) = 1"
      
      # "Gill had sausage roll and something orange"
      "P == 4 or Q == 4"
      "C == 4 or H == 4"
      
      # "someone had cheese and chocolate cake"
      "(K == E) or (L == E)"
      
      # "coffee cake had a ham sandwich, but no cheese"
      "B == T or B == U"
      "B != K and B != L"
      
      # "no-one had egg and shrimp"
      "is_disjoint(([M, N], [R, S]))"
      
      # mention A
      "A > 0"
      
      # [optional]
      --template="(A B C D E) (F G H I J) (K L) (M N) (P Q) (R S) (T U)"
      --solution=""
      --denest=-1  # apply fix for CPython
      

      Solution: Dot and Eve had the ham sandwiches.

      The full solution is:

      D: Sponge cake; orange juice; sausage roll + ham sandwich
      E: Coffee cake; lemon squash; shrimp + ham sandwich
      F: Chocolate cake; tea; cheese + shrimp
      G: Orange cake; coffee; egg + sausage roll
      H: Lemon cake; hot chocolate; cheese + egg

      Like

  • Unknown's avatar

    Jim Randell 12:00 pm on 24 August 2021 Permalink | Reply
    Tags:   

    Teaser 2813: Katy’s piggy banks 

    From The Sunday Times, 21st August 2016 [link] [link]

    Our granddaughter Katy has two piggy banks containing a mixture of 10p and 50p coins, making a grand total of 10 pounds. The first piggy bank contains less than the other, and in it the number of 50p coins is a multiple of the number of 10p coins.

    Katy chose a coin at random from the first piggy bank and then put it in the second. Then she chose a coin at random from the second and put it in the first. She ended up with the same amount of money in the first piggy bank as when she started. In fact there was a 50:50 chance of this happening.

    How much did she end up with in the first piggy bank?

    [teaser2813]

     
    • Jim Randell's avatar

      Jim Randell 12:01 pm on 24 August 2021 Permalink | Reply

      The following Python program all possible distributions of coins between the two piggy banks. It runs in 57ms.

      Run: [ @replit ]

      from enigma import (Rational, irange, express, div, printf)
      
      Q = Rational()
      
      # consider the amount in the first piggy bank (less than 5 pounds)
      for s1 in irange(0, 490, step=10):
        for (t1, f1) in express(s1, [10, 50]):
          # f1 is a (proper) multiple of t1
          d = div(f1, t1)
          if d is None or d < 2: continue
          n1 = f1 + t1
      
          # and the amount in the second piggy bank
          s2 = 1000 - s1
          for (t2, f2) in express(s2, [10, 50]):
            n2 = f2 + t2
      
            # probability of withdrawing a 50p from both banks
            p1 = Q(f1, n1) * Q(f2 + 1, n2 + 1)
      
            # probability of withdrawing a 10p from both banks
            p2 = Q(t1, n1) * Q(t2 + 1, n2 + 1)
      
            # together they should make 1/2
            if p1 + p2 == Q(1, 2):
              printf("s1={s1} ({f1}, {t1}), s2={s2} ({f2}, {t2}) [p1 = {p1}, p2 = {p2}]")
      

      Solution: Katy ended up with £3.20 in the first piggy bank.

      The first piggy bank had £3.20 in it (2× 10p + 6× 50p; and 6 is a proper multiple of 2).

      The second piggy bank had the £6.80 in it (13× 10p + 11× 50p).

      We assume the two denominations of coin are equally likely to be chosen.

      The same denomination must be chosen in both cases, so the probability of transferring a 50p from the first bank to the second is: 6/8 = 3/4.

      And there are now 12× 50p coins and 13× 50p coins in the second piggy bank, so the probability of transferring a 50p from the second bank back to the first is: 12/25.

      p1 = (3/4)(12/25) = 9/25

      Similarly the probability of moving a 10p back and forth is:

      p2 = (1/4)(14/25) = 7/50

      Adding these together gives the total probability of the same denomination coin moving back and forth:

      p1 + p2 = 9/25 + 7/50 = 1/2

      Like

    • John Crabtree's avatar

      John Crabtree 4:57 am on 27 August 2021 Permalink | Reply

      Let the total in the first bag = 10a + 50ma
      Let the total in the second bag = 10b + 50c
      The probability condition leads to (m – 1)(b – c – 1) = 2, and so m = 2 or 3, and b – c + m = 5
      This leads to c = 16 – ma + (a + 1)(m – 1)/6
      a < 5 and so m = 3 and a = 2.

      Like

    • Linda's avatar

      Linda 11:27 am on 27 January 2023 Permalink | Reply

      This is a brilliant problem

      Like

  • Unknown's avatar

    Jim Randell 9:23 am on 22 August 2021 Permalink | Reply
    Tags: by: R. Skeffington Quinn   

    Brain-Teaser 15: Bumper’s final ball 

    From The Sunday Times, 11th June 1961 [link]

    It is a lovely evening in August, and the final Test of the 1990 series has reached its climax. The rubber stands at two games each, the last ball of the last over of the match is now to come. Australia are batting and need six runs for victory. Whacker, their wicket-keeper, the last man in, has taken his stand. with his captain’s words ringing in his ears, “Six or bust!”.

    Bumper, the England bowler, has just taken the previous two wickets in succession, With a dim opinion of Whacker’s batting, he feels sure that a fast straight one will not only give England the Ashes, but will give him his hat-trick and his seventh wicket of the match.

    In a breathless hush he delivers a  fast straight one. Striding forward like a Titan, Whacker mows …

    The records of this match are scanty. The Australian total in two innings was 490. Except for one man run out in the first innings, their casualties fell to bowlers. The five England bowlers had averages of 14, 20, 25 (Bumper), 33, 43, each with a differing number of wickets.

    How many wickets did each take and who won the Ashes?

    This is another puzzle that I originally couldn’t find, but with a bit more searching of the archive I was able to unearth it.

    This puzzle completes the archive of Teaser puzzles from 1961 (when the first numbered puzzles appeared).

    This is the first of the numbered Teaser puzzles set by Charles Skeffington Quin (although it is credited to R. Skeffington Quinn), and was re-published as Brainteaser 1093 on 17th July 1983 to celebrate Mr Skeffington Quin’s 100th birthday.

    [teaser15]

     
    • Jim Randell's avatar

      Jim Randell 9:24 am on 22 August 2021 Permalink | Reply

      I think you need to something about cricket to solve this puzzle. Unfortunately I am not an expert in cricket, but here goes…

      We need to know the number of Australian batmen dismissed by the bowlers, in both innings. In the first innings, all 10 of the batsmen will have been dismissed, but one was run out, so only 9 were bowled. In the second innings, if Australia win, only 9 of the batsmen will have been dismissed (and Bumper will have taken 6 wickets), however if Bumper bowls out the last man all 10 of them will have been dismissed (and Bumper will have taken 7 wickets).

      So we are interested in the situation where either 18 wickets are taken (Australia win, and Bumper takes 6 wickets) or where 19 wickets are taken (England win, and Bumper takes 7 wickets).

      This Python program runs in 55ms.

      Run: [ @replit ]

      from enigma import (express, all_different, printf)
      
      # the averages (which happen to be an increasing sequence)
      avgs = (14, 20, 25, 33, 43)
      
      # how can a total of 490 be achieved using these averages?
      for (a, b, c, d, e) in express(490, avgs, min_q=1):
        # each bowler took a different number of wickets
        if not all_different(a, b, c, d, e): continue
        # we are interested in totals of 18 or 19
        t = a + b + c + d + e
        if t == 18 and c == 6:
          win = "Australia"
        elif t == 19 and c == 7:
          win = "England"
        else:
          continue
        # output solution
        (A, B, C, D, E) = (x * y for (x, y) in zip(avgs, (a, b, c, d, e)))
        printf("{a} for {A}, {b} for {B}, {c} for {C}, {d} for {D}, {e} for {E}; {win} win")
      

      Solution: The number of wickets taken by each bowler are: 5, 2, 7 (Bumper), 1, 4. England won.

      Like

  • Unknown's avatar

    Jim Randell 5:45 pm on 20 August 2021 Permalink | Reply
    Tags:   

    Teaser 3074: Timely overthrows 

    From The Sunday Times, 22nd August 2021 [link] [link]

    Without changing their size, Judith sews together one-foot squares of different colours that her mother has knitted, to make rectangular throws. These are usually all of the same dimensions using fewer than a hundred squares. She has observed that it takes her mother 20 per cent longer to knit each square than it takes her to sew two single squares together.

    As a one-off she has completed a square throw whose sides have the same number of squares as the longer side of her usual rectangular throws. The average time it took per square foot, both knitting and sewing, to complete the square throw was 2 per cent longer than that of the rectangular throws.

    What are the dimensions (in feet) of the rectangular throws?

    [teaser3074]

     
    • Jim Randell's avatar

      Jim Randell 6:19 pm on 20 August 2021 Permalink | Reply

      For a throw of dimensions (x, y) there are xy squares, each of which takes 6 units of time to knit.

      Each square has 4 edges, so there are 4xy edges, but the edges on the perimeter are not sewn together, so there are a total of 4xy − 2(x + y) edges that are sewn together, in pairs. And each pair take 5 units of time to sew together.

      Giving a total time for the throw of:

      time(x, y) = 6xy + 5(4xy − 2(x + y))/2
      time(x, y) = 6xy + 5(2xy − x − y)

      This Python program runs in 53ms.

      from enigma import (irange, divisors_pairs, printf)
      
      # total time for a throw measuring (x, y)
      time = lambda x, y: 6 * x * y + 5 * (2 * x * y - x - y)
      
      # consider the dimensions (x, y) of a "standard" throw (area < 100)
      for a in irange(1, 99):
        for (x, y) in divisors_pairs(a):
          if x == y: continue
          # total time involved
          t = time(x, y)
      
          # consider the time for a square (y, y) throw
          t2 = time(y, y)
          # the average time per square should be 2% longer
          # i.e. t2 / y^2 = 1.02(t / xy) => 100 x t2 = 102 y t
          if 100 * x * t2 == 102 * y * t:
            printf("a={a}; x={x} y={y} t={t}; t2={t2}")
      

      Solution: The standard throw is 5 ft × 7 ft.

      It has an area of 35 sq ft, and takes 500 time units to construct. i.e. 100/7 time units per square.

      A 7 ft × 7 ft throw has an area 49 sq ft, and takes 714 time units to construct. i.e. 102/7 time units per square.

      And we can easily see that this average is 1.02 times the average for a standard throw.

      Liked by 1 person

      • Jim Randell's avatar

        Jim Randell 6:39 pm on 20 August 2021 Permalink | Reply

        Solving the equation for the average time per square gives us:

        255y − 245x − 16xy = 0
        y = 245x / (255 − 16x)

        from enigma import (irange, div, printf)
        
        # calculate the dimension of a standard (x, y) throw
        for x in irange(1, 7):
          y = div(245 * x, 255 - 16 * x)
          if y is not None:
            printf("x={x} y={y}")
        

        Like

    • GeoffR's avatar

      GeoffR 11:45 am on 22 August 2021 Permalink | Reply

      I found one other answer, much larger than the puzzle answer, which satisfies Jim’s equation:
      255y – 245x – 16xy = 0.

      It is x = 15, y = 245.

      Like

      • Jim Randell's avatar

        Jim Randell 1:00 pm on 22 August 2021 Permalink | Reply

        And (5, 7), (15, 245) are the only (x, y) solutions in positive integers. (Although x = 7 is very close). At x ≥ 16, y becomes negative.

        Like

    • GeoffR's avatar

      GeoffR 2:41 pm on 23 August 2021 Permalink | Reply

      % A Solution in MiniZinc
      
      var 2..10:X;  % horizontal
      var 2..50:Y;  % vertical
      
      constraint Y > X;
      
      % Number of sewn edges = (Y - 1).X + (X - 1).Y
      % Area of rectangular throw = X * Y
      % Time to make throw and sew throw edges = 
      % 6.X.Y + 5.( (Y-1).X + (X-1).Y )
      
      % Square throw unit time = 51/50 * Rectangle throw unit time
      constraint (6*X*Y + 5*( (Y - 1)*X + (X - 1)*Y ) ) * 51 * Y * Y
      == (6*Y*Y + 10*Y*(Y - 1)) * 50 * X * Y;
      
      solve satisfy;
      
      output ["Throw dimensions (ft) are X = " ++ show(X) 
      ++ ", " ++ "Y = " ++ show(Y)];
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 1:45 pm on 17 August 2021 Permalink | Reply
    Tags:   

    Teaser 2811: Making arrangements 

    From The Sunday Times, 7th August 2016 [link] [link]

    Beth wrote down a three-figure number and she also listed the five other three-figure numbers that could be made using those same three digits. Then she added up the six numbers: it gave a total whose digits were all different, and none of those digits appeared in her original number.

    If you knew whether her original number was prime or not, and you knew whether the sum of the three digits of her original number was prime or not, then it would be possible to work out her number.

    What was it?

    [teaser2811]

     
    • Jim Randell's avatar

      Jim Randell 1:47 pm on 17 August 2021 Permalink | Reply

      If the number is ABC, then in order for the different orderings of (A, B, C) to make 6 different numbers A, B, C must all be distinct and non-zero. Then we have:

      ABC + ACB + BAC + BCA + CAB + CBA = PQRS
      ⇒ 222 × (A + B + C) = PQRS

      We can use two of the routines from the enigma.py library to solve this puzzle. [[ SubstitutedExpression() ]] to solve the alphametic problem, and [[ filter_unique() ]] to find the required unique solutions.

      The following Python program runs in 53ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, filter_unique, unpack, printf)
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        ["222 * (A + B + C) = PQRS"],
        d2i={ 0: 'ABCP' },
        answer="(ABC, is_prime(ABC), is_prime(A + B + C))",
      )
      
      # if you knew (f1, f2) you could deduce n
      rs = filter_unique(
        p.answers(verbose=0),
        unpack(lambda n, f1, f2: (f1, f2)),
        unpack(lambda n, f1, f2: n),
      ).unique
      
      # output solution
      for (n, f1, f2) in rs:
        printf("number = {n} (prime = {f1}; dsum prime = {f2})")
      

      Solution: Beth’s number was 257.

      The only values for (A, B, C) that work are (2, 5, 7) and (3, 7, 9). These can be assembled in any order to give an original number that works.

      Of these 257 is the only arrangement that gives a prime number, with a digit sum that is not prime.

      Like

    • GeoffR's avatar

      GeoffR 9:39 am on 18 August 2021 Permalink | Reply

      I used four lists for the two primality tests for each potential 3-digit answer. The list with a single entry was Beth’s number.

      from itertools import product
      from enigma import is_prime
      
      # Four lists for primality tests
      TT, FT, FF, TF = [], [], [], []
      
      # Form six 3-digit numbers - Beth's number was abc
      for a,b,c in product(range(1,10), repeat=3):
        abc, acb = 100*a + 10*b + c, 100*a + 10*c + b
        bac, bca = 100*b + 10*a + c, 100*b + 10*c + a
        cab, cba = 100*c + 10*a + b, 100*c + 10*b + a
        pqrs = abc + acb + bac + bca + cab + cba
        # find four digits of the sum of six numbers
        p, q = pqrs//1000, pqrs//100 % 10
        r, s = pqrs//10 % 10, pqrs % 10
        
        # all seven digits are different
        if len(set((a, b, c, p, q, r, s))) == 7:
          
          # check the primality of number abc
          # and primality of the sum of its digits
          if is_prime(abc) and is_prime(a+b+c):
            TT.append(abc)  # true/true
            
          if not(is_prime(abc)) and is_prime(a+b+c):
            FT.append(abc)  # false/true
            
          if not(is_prime(abc)) and not(is_prime(a+b+c)):
            FF.append(abc)  # false/false
            
          if is_prime(abc) and not(is_prime(a+b+c)):
            TF.append(abc)  # true/false
      
      # find a single number in the four lists
      for L in (TT, FT, FF, TF):
        if len(L) == 1:
          print(f"Beth's number was {L[0]}.")
          
      print("True/True numbers = ", TT)
      print("False/True numbers = ", FT)
      print("False/False numbers = ", FF)
      print("True/False numbers = ", TF)
          
      # Beth's number was 257.
      # True/True numbers =  [379, 397, 739, 937]
      # False/True numbers =  [793, 973]
      # False/False numbers =  [275, 527, 572, 725, 752]
      # True/False numbers =  [257]
      
      

      Like

    • Frits's avatar

      Frits 3:02 pm on 18 August 2021 Permalink | Reply

        
      from itertools import permutations as perm
      from functools import reduce
      from enigma import is_prime
      
      # convert digits sequence to number
      d2n = lambda s: reduce(lambda x, y: 10 * x + y, s)
      
      # decompose number <t> into <k> increasing numbers from <ns>
      # so that sum(<k> numbers) equals <t>
      def decompose(t, k, ns, s=[]):
        if k == 1:
          if t in ns and t > s[-1]:
            yield s + [t]
        else:
          for n in ns:
            if s and n <= s[-1]: continue
            yield from decompose(t - n, k - 1, ns, s + [n])
      
      # 5 < a + b + c < 25
      for sumabc in range(6, 25):
        # pqrs = abc + acb + bac + bca + cab + cba
        pqrs = str(222 * sumabc)   
        
        # skip if duplicate digits
        if len(set(pqrs)) != len(pqrs): continue
        
        # determine minimum and maximum for a, b, c
        mi = max(1, sumabc - 9 - 8)
        ma = min(9, sumabc - 1 - 2)
        
        # determine digits not used in sum (must be valid for a, b, c)
        missing = [x for x in range(1, 10) if str(x) not in pqrs and mi <= x <= ma]
        if len(missing) < 3: continue
        
        # check if 3 digits of missing sum to <sumabc>
        for d in decompose(sumabc, 3, missing):
          if not is_prime(sumabc): 
            # check which permutatons of a, b, c are prime
            primes = [n for p in perm(d) if is_prime(n := d2n(p))]
            if len(primes) == 1:
              print("answer:", primes[0])
          else:     # sumabc is prime    
            # check which permutatons of a, b, c are non-prime
            nprimes = [n for p in perm(d) if not is_prime(n := d2n(p))]
            if len(nprimes) == 1:
              print("answer:", nprimes[0]) 
      

      Like

    • GeoffR's avatar

      GeoffR 3:08 pm on 19 August 2021 Permalink | Reply

      An easy solution with standard MiniZinc, although the answer needs to be interpreted from multiple output configuration.

      % A Solution in MiniZinc 
      include "globals.mzn";
      
      var 1..9: A; var 1..9: B; var 1..9: C; 
      var 1..9: P; var 0..9: Q; var 0..9: R; var 0..9: S; 
      
      constraint all_different([A, B, C, P, Q, R, S]);
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: ACB = 100*A + 10*C + B;
      var 100..999: BAC = 100*B + 10*A + C;
      var 100..999: BCA = 100*B + 10*C + A;
      var 100..999: CAB = 100*C + 10*A + B;
      var 100..999: CBA = 100*C + 10*B + A;
      var 1000..9999: PQRS = 1000*P + 100*Q + 10*R + S;
      
      var 6..24: sum_ABC = A + B + C;
      
      constraint ABC + ACB + BAC + BCA + CAB + CBA == PQRS;
      
      solve satisfy;
      
      output [ "[ABC, sum_ABC] = " ++ 
      show([ABC, is_prime(ABC), sum_ABC, is_prime(sum_ABC) ]) ];
      
      % key: 0 = not prime, 1 = prime
      
      % [ABC, sum_ABC] = [752, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [572, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [973, 0, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [793, 0, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [725, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [275, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [527, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [937, 1, 19, 1]
      % ----------
      % *** unique prime/non-prime test for ABC ***
      % [ABC, sum_ABC] = [257, 1, 14, 0] <<<
      % ----------
      % [ABC, sum_ABC] = [397, 1, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [739, 1, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [379, 1, 19, 1]
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 6:02 pm on 15 August 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 835: Traffic light entertainment 

    From The Sunday Times, 17th July 1977 [link]

    Newtown High Street has a linked traffic light system which consists of six consecutive sections, each a multiple of one-eighth of a mile, and each terminating in a traffic light.

    The lights are synchronised such that a vehicle travelling at 30 mph will pass each light at the same point in its 26-second operating cycle.

    This cycle can be considered as 13 seconds “stop” (red) and 13 seconds “go”(green).

    Charlie had studied the system and reckoned he could drive much faster than 30 mph and still get through the system without crossing a red light.

    In an experiment Alf, Bert and Charlie entered the first section at the same instant, travelling at 30, 50 and 75 mph respectively, with the first light turning green three seconds later.

    Charlie got through the whole system in less than two minutes without being stopped.

    “I was lucky though”, said Charlie. “I arrived at the last light just as it changed”.

    “My luck was non-existent”, said Bert. “I ran out of petrol after the third light and in any case would have been stopped at the second light had I not lost 10 seconds due to a delay in the second section!”

    What were the lengths of each section in order from the first?

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

    [teaser835]

     
    • Jim Randell's avatar

      Jim Randell 6:03 pm on 15 August 2021 Permalink | Reply

      (See also: Enigma 198).

      Using distance units of eighths of a mile. We see that the final light must be less than 20 units away from the start, and the time to travel each unit is:

      A: 30mph = 1 unit in 15s
      B: 50mph = 1 unit in 9s
      C: 75mph = 1 unit in 6s

      And the following conditions hold at the lights:

      A: makes it through all lights at green (and at the same point in the 26s cycle)
      B: makes it through light 1; but is stopped at light 2, however …
      B + 10s: makes it through lights 2 and 3
      C: makes it through all lights at green, but hits light 6 as it is changing.

      The following Python 3 program runs in 50ms.

      Run: [ @replit ]

      from enigma import irange, printf
      
      # 0 - 13 = green, 14 - 25 = red
      def green(t, t0):
        return (t - t0) % 26 < 14
      
      # solve starting with light k
      # k = index of next light
      # ds = length of light controlled sections
      # ts = start time of light "go" period
      def solve(k, ds, ts, A=0, B=0, C=0):
        # calculate times at the current light
        d = ds[-1]
        t = ts[-1]
        A += d * 15
        B += d * 9
        C += d * 6
      
        # at all lights, A and C get green lights 
        if not(green(A, t) and green(C, t)): return
        # at the first light...
        if k == 1:
          # B made it through
          if not(green(B, t)): return
        # at the second light ...
        elif k == 2:
          # B would have been stopped ...
          if green(B, t): return
          # but he arrived 10s late
          if not green(B + 10, t): return
        # at the third light ...
        elif k == 3:
          # B passed at green, 10s late
          if not green(B + 10, t): return
        # at the sixth light ...
        elif k == 6:
          # C arrived just as they changed
          if (C - t) % 13 != 0: return
      
        # are we done?
        if k == 6:
          # return the distances
          yield ds
        else:
          # move on to the next light
          for x in irange(1, 14 + k - sum(ds)):
            for z in solve(k + 1, ds + [x], ts + [t + 15 * x], A, B, C): yield z
      
      # consider distance to light 1
      for d in irange(1, 14):
        # solve the puzzle (first light goes green at t=3)
        for ds in solve(1, [d], [3]):
          printf("distances = {ds}")
      

      Solution: The lengths of the sections (in miles) are: 1st = 1/8; 2nd = 1/4; 3rd = 3/8; 4th = 1/8; 5th = 1/4; 6th = 1/8.

      The total length of the sections is 10/8 miles (= 1.25 miles), so C completes the course in 60s (= 1m) and A in 150s (= 2m30s).

      Here is a diagram showing the progress of A, B and C:

      A arrives at each light just before it changes to red. And C ends his journey by heading towards a red light at 75mph, which (fortunately) changes to green just as he reaches it.

      Like

  • Unknown's avatar

    Jim Randell 4:45 pm on 13 August 2021 Permalink | Reply
    Tags:   

    Teaser 3073: Snookered 

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

    The playing surface of a snooker table is a twelve-foot by six-foot rectangle. A ball is placed at P on the bottom cushion (which is six feet wide) and hit so it bounces off the left cushion, right cushion and into the top-left pocket.

    Now the ball is replaced at P and hit so it bounces off the left cushion, top cushion and into the bottom right pocket, after travelling 30% further than the first shot took. The ball always comes away from the cushion at the same angle that it hits the cushion.

    How far did the ball travel on the second shot?

    [teaser3073]

     
    • Jim Randell's avatar

      Jim Randell 5:07 pm on 13 August 2021 Permalink | Reply

      (See also: Teaser 1917).

      With a suitable diagram this puzzle reduces to solving a quadratic equation.

      By reflecting the table along its sides we can convert the paths of the ball into straight lines, whose length can be easily calculated. (For the purposes of this puzzle the ball and the pockets can be considered to be points of negligible size).

      We see that the 1st distance A is given by:

      A² = (12)² + (12 + x)²

      And the second distance B by:

      B² = (24)² + (6 + x)²

      And they are related by:

      B = (13/10)A
      10B = 13A
      100B² = 169A²

      This gives us a quadratic equation in x, which we can solve to find the required answer (= B).

      from enigma import (quadratic, sq, hypot, printf)
      
      # dimensions of the table
      (X, Y) = (6, 12)
      
      # B = (P/Q) A
      # (P^2)(A^2) = (Q^2)(B^2)
      (P2, Q2) = (sq(13), sq(10))
      
      # calculate the coefficients of the quadratic: a.x^2 + b.x + c = 0
      a = P2 - Q2
      b = P2 * 2 * Y - Q2 * 2 * X
      c = P2 * 2 * sq(Y) - Q2 * (sq(2 * Y) + sq(X))
      printf("[({a:+d})x^2 ({b:+d})x ({c:+d})]")
      
      # and solve the equation to determine x
      for x in quadratic(a, b, c, domain='F'):
        if 0 < x < X:
          # calculate the paths
          A = hypot(12, 12 + x)
          B = hypot(24, 6 + x)
          printf("A={A:g} B={B:g} [x={x:g}]")
      

      Solution: On the second shot the ball travelled 26 feet.

      The required equation is:

      69x² + 2856x − 12528 = 0

      This factorises as:

      3(x − 4)(23x + 1044) = 0

      From which the value of x is obvious, and the value of B can then be calculated.

      We find:

      x = 4
      A = 20
      B = 26

      Like

      • Frits's avatar

        Frits 6:25 pm on 13 August 2021 Permalink | Reply

        @Jim, I verified your quadratic solution. It directly follows from the diagram.

        Like

      • Jim Randell's avatar

        Jim Randell 11:51 am on 16 August 2021 Permalink | Reply

        Or finding the answer numerically:

        from enigma import (hypot, fdiv, find_value, printf)
        
        # calculate paths A and B
        A = lambda x: hypot(12, 12 + x)
        B = lambda x: hypot(24, 6 + x)
        
        # find an x value that gives B/A = 1.3
        x = find_value((lambda x: fdiv(B(x), A(x))), 1.3, 0, 6).v
        printf("A={A:g} B={B:g} [x={x:g}]", A=A(x), B=B(x))
        

        Like

  • Unknown's avatar

    Jim Randell 10:35 am on 12 August 2021 Permalink | Reply
    Tags: by: James Fitzgibbon   

    Brain-Teaser 22: [Beauty competition] 

    From The Sunday Times, 20th August 1961 [link]

    Our beauty competition (said Alice) was rather a fiasco, as the judge failed to turn up. None of the other men would take on the job, so we decided to run it ourselves. Each of us was allowed twelve votes to share out among the competitors, including herself, and zeros were barred. In the result each of us got twelve votes, but that wasn’t the only oddity. The twelve votes were never made up the same way twice, whether given or received.

    I made the least difference between the competitors and, unlike the others, I did not put myself on top. I gave Beryl an odd number of votes, but Chloe gave four odd numbers. Beryl let only two other girls share top place with her, but Diana, the cat, gave herself the most possible votes.

    How did we vote?

    This puzzle was originally published with no title.

    I originally couldn’t find this puzzle in The Sunday Times digital archive, but I think that is because it is quite a poor scan. But it was possible to transcribe it, so here it is, almost exactly 60 years after it was originally published.

    [teaser22]

     
    • Jim Randell's avatar

      Jim Randell 10:37 am on 12 August 2021 Permalink | Reply

      We know there are (at least) 4 contestants. And we quite quickly find (by considering marks awarded by B) that exactly 4 contestants is not possible, so there must be at least one more we are not told about.

      If we suppose there are k contestants, and consider constructing a k × k table, where the rows give the marks awarded, and the columns the marks received. Then each row and column must be derived from a unique distribution of the 12 marks.

      The puzzle states that D gave herself the the highest possible marks. This would be achieved by giving everyone else a score of 1. However this seems to contradict the fact the the distribution of marks in the rows and columns are all different, as if D gave herself the highest possible mark, then the other entries in D’s row and column must all be 1’s, giving a row and a column with the same distribution.

      Instead I suggest we adopt: “The highest number of marks awarded were by D, to herself”.

      Now, if we consider the number of decompositions of 12 into k positive integers, then there must be a unique arrangement for each of the rows and columns, i.e. at least 2k decompositions. And since we can’t use the decomposition with (k − 1) 1’s, we need there to be at least (2k + 1) decompositions. For k = 6 it turns out there are only 11 decompositions, so k = 5 is the only possible number of contestants.

      With that in mind this Python 3 program is implemented to solve the k = 5 case (although it also shows other values are not possible). It runs in 406ms.

      Run: [ @replit ]

      from enigma import (irange, inf, cproduct, subsets, group, all_different, ordered, printf)
      
      # attempt to solve the puzzle for k contestants, decompositions = <ds>
      def solve(k, ds):
      
        # group the decompositions by span
        d = group(ds, by=(lambda s: max(s) - min(s)))
      
        # A's row has minimal span
        rAs = d[min(d.keys())]
      
        # B's has 3 sharing max marks
        rBs = list(s for s in ds if s.count(max(s)) == 3)
      
        # C's has exactly 4 odd numbers
        rCs = list(s for s in ds if sum(x % 2 for x in s) == 4)
      
        # choose rows (unordered) for A, B, C
        for (rA, rB, rC) in cproduct([rAs, rBs, rCs]):
          if not all_different(rA, rB, rC): continue
          # max points awarded (so far)
          (mA, mB, mC) = (max(r) for r in (rA, rB, rC))
      
          # D's row contains a (single) max value greater than mA, mB, mC
          mABC = max(mA, mB, mC)
          for rD in ds:
            if rD in (rA, rB, rC): continue
            mD = max(rD)
            if not (mD > mABC and rD.count(mD) == 1): continue
      
            # solve for the remaining rows
            if k == 5:
              solve5(ds, rA, rB, rC, rD, mA, mB, mC, mD)
            else:
              assert False, "Not reached"
      
      # use multiset permutations (to remove duplication)
      permutations = lambda s: subsets(s, size=len, select="mP")
      
      # solve for k = 5
      def solve5(ds, rA, rB, rC, rD, mA, mB, mC, mD):
        # choose an ordering for A, st A [0] is not max, and B [1] is odd
        for A in permutations(rA):
          if not (A[1] % 2 == 1 and A[0] < mA): continue
      
          # choose an ordering for B, st B [1] is max
          for B in permutations(rB):
            if not (B[1] == mB): continue
      
            # chose an ordering for C, st C [2] is max
            for C in permutations(rC):
              if not (C[2] == mC): continue
      
              # chose an ordering for D, st D [3] is max
              for D in permutations(rD):
                if not (D[3] == mD): continue
      
                # construct row E
                E = tuple(12 - sum(x) for x in zip(A, B, C, D))
                # all values are between 0 and mD (exclusive)
                if not all(0 < x < mD for x in E): continue
                # and E [4] is max
                if not (E[4] == max(E)): continue
                # check E is a valid decomposition
                rE = ordered(*E)
                if not (rE in ds and rE not in (rA, rB, rC, rD)): continue
      
                # calculate the column distributions
                cds = list(ordered(*x) for x in zip(A, B, C, D, E))
                # check all distributions are distinct
                if not all_different(rA, rB, rC, rD, rE, *cds): continue
      
                # output solution
                printf("k=5: A={A} B={B} C={C} D={D} E={E}")
      
      # decompose total <t> into <k> numbers, minimum <m>
      def decompose(t, k, m=1, ns=[]):
        if k == 1:
          if not (t < m):
            yield tuple(ns + [t])
        else:
          k_ = k - 1
          for n in irange(m, t - k_ * m):
            yield from decompose(t - n, k_, n, ns + [n])
      
      # try possible k values
      for k in irange(4, inf):
        # consider the number of decompositions for the rows/columns
        ds = list(ns for ns in decompose(12, k) if ns.count(1) < k - 1)
        printf("[k={k}: {n} decompostions]", n=len(ds))
        if len(ds) < 2 * k: break
        # solve the puzzle
        solve(k, ds)
      

      Solution: The marks awarded are as follows:

      Like

  • Unknown's avatar

    Jim Randell 9:54 am on 10 August 2021 Permalink | Reply
    Tags:   

    Teaser 2808: Hot stuff 

    From The Sunday Times, 17th July 2016 [link] [link]

    George and Martha are dabbling in the world of high temperature physics. George was measuring the temperature of a molten metal and wrote down the result. He thought this was in degrees Centigrade and so he converted it to Fahrenheit. However, Martha pointed out that the original result was already in degrees Fahrenheit and so George converted it to Centigrade. Martha wrote down the original result and each of George’s two calculated answers. She noted that they were all four-figure numbers and that their sum was palindromic.

    What was the original four-figure result?

    [teaser2808]

     
    • Jim Randell's avatar

      Jim Randell 9:57 am on 10 August 2021 Permalink | Reply

      This Python program considers possible 4-digit numbers for the first reading, and then looks for viable second and third numbers that give a palindromic sum. It runs in 55ms.

      Run: [ @replit ]

      from enigma import (div, irange, is_npalindrome, printf)
      
      # convert centigrade (celsius) to fahrenheit
      c2f = lambda n: div(9 * n + 160, 5)
      
      # convert fahrenheit to centigrade (celsius)
      f2c = lambda n: div(5 * n - 160, 9)
      
      # original number (a 4-digit number)
      for n1 in irange(1000, 9999):
      
        # second number
        n2 = c2f(n1)
        if n2 is None or n2 < 1000 or n2 > 9999: continue
      
        # third number
        n3 = f2c(n1)
        if n3 is None or n3 < 1000 or n3 > 9999: continue
      
        # look for a palindromic sum
        t = n1 + n2 + n3
        if is_npalindrome(t):
          # output solution
          printf("n1={n1} n2={n2} n3={n3} t={t}")
      

      Solution: The original reading was 3155.

      And:

      3155 °C = 5711 °F
      3155 °F = 1735 °C
      3155 + 5711 + 1735 = 10601


      With analysis we can restrict the numbers considered for n1, and simplify the calculations.

      We see n1 must be in the range [1832, 5537], and must be a multiple of 5, and must equal 5 (mod 9).

      Run: [ @replit ]

      from enigma import (irange, is_npalindrome, printf)
      
      # all three numbers have 4 digits
      for k in irange(41, 122):
        # original number
        n1 = 45 * k + 5
        # second number
        n2 = 81 * k + 41
        # third number
        n3 = 25 * k - 15
        # look for a palindromic sum
        t = n1 + n2 + n3
        if is_npalindrome(t):
          # output solution
          printf("n1={n1} n2={n2} n3={n3} t={t}")
      

      Like

    • GeoffR's avatar

      GeoffR 11:55 am on 10 August 2021 Permalink | Reply

      Checking for the palindromic sum was a bit lengthy in MiniZinc, as I could not be sure if this total was four or five digits long.

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      % T1 = original temperature, T2 in F, T3 in C
      var 1000..9999:T1; var 1000..9999:T2; var 1000..9999:T3;
      
      var 1000..99999: T4; % total of three temperatures
      
      constraint 5 * (T2 - 32) == 9 * T1;  % T2 = C to F from T1
      
      constraint 9 * T3 == 5 * (T1 - 32);  % T3 = F to C from T1
      
      constraint T4 == T1 + T2 + T3;
      
      % check for a 4-digit or 5-digit palindrome sum for T4
      var 1..9:a; var 0..9:b; var 0..9:c; var 0..9:d; var 0..9:e;
      
      constraint (T4 < 10000 /\ a == T4 div 1000 /\ b == T4 div 100 mod 10
      /\ c == T4 div 10 mod 10 /\ d == T4 mod 10 /\ a == d /\ b == c)
      \/
      (T4 > 10000 /\ a == T4 div 10000 /\ b == T4 div 1000 mod 10
      /\ c == T4 div 100 mod 10 /\ d == T4 div 10 mod 10 /\ e  == T4 mod 10
      /\ a == e /\ b == d);
      
      solve satisfy;
      
      output ["Original Temperature = " ++ show(T1) ++ "\n"
      ++ "Conversion Temperatures = " ++ show(T2) ++ ", " ++ show(T3)
      ++ "\n" ++ "Palindromic sum of three temperatures = " ++ show(T4) ];
      
      % Original Temperature = 3155
      % Conversion Temperatures = 5711, 1735
      % Palindromic sum of three temperatures = 10601
      % ----------
      % ==========
      
      

      Like

  • Unknown's avatar

    Jim Randell 5:23 pm on 6 August 2021 Permalink | Reply
    Tags:   

    Teaser 3072: Dial M for Marriage 

    From The Sunday Times, 8th August 2021 [link] [link]

    George and Martha work in a town where phone numbers have seven digits. “That’s rare!”, commented George. “If you look at your work number and mine, both exhibit only four digits of the possible ten (0-9 inclusive), each appearing at least once. Furthermore, the number of possible phone numbers with that property has just four single-digit prime number factors (each raised to a power where necessary) and those four numbers are the ones in our phone numbers”.

    “And that is not all!”, added Martha. “If you add up the digits in the two phone numbers you get a perfect number in both cases. Both have their highest digits first, working their way down to the lowest”.

    [A perfect number equals the sum of its factors, e.g., 6 = 1 + 2 + 3].

    What are two phone numbers?

    [teaser3072]

     
    • Jim Randell's avatar

      Jim Randell 5:43 pm on 6 August 2021 Permalink | Reply

      This puzzle sounds more complicated than it is.

      There are only 4 single digit primes (2, 3, 5, 7), so these must be digits of the phone numbers. And they must occur in the order 7*5*3*2*, where the * is zero or more repeats of the previous digit, to give 7 digits in total.

      This Python program considers the possible phone numbers composed of these digits, and finds those with a digit sum that is a perfect number.

      It runs in 51ms.

      Run: [ @replit ]

      from enigma import (irange, divisors, cache, join, printf)
      
      # decompose <t> into <k> positive integers
      def decompose(t, k, ns=[]):
        if k == 1:
          yield ns + [t]
        else:
          k_ = k - 1
          for n in irange(1, t - k_):
            yield from decompose(t - n, k_, ns + [n])
      
      # is a number perfect?
      @cache
      def is_perfect(n):
        return sum(divisors(n)) == 2 * n
      
      # find possible distributions of digits
      for (m7, m5, m3, m2) in decompose(7, 4):
        # the digits ...
        ds = [7] * m7 + [5] * m5 + [3] * m3 + [2] * m2
        # ... and their sum ...
        t = sum(ds)
        # ... is it perfect?
        if is_perfect(t):
          printf("{ds} -> {t}", ds=join(ds))
      

      Solution: The phone numbers are 7553332 and 7753222.

      Both numbers have a digit sum of 28, which is a perfect number (28 = 1 + 2 + 4 + 7 + 14).


      For completeness:

      There are 1764000 possible 7-digit phone numbers that consist of exactly 4 different digits. And we can factorise this as:

      1764000 = (2^5)(3^2)(5^3)(7^2)

      So it does indeed have a prime factorisation that consists of (positive) powers of the 4 single-digit prime numbers.

      But this is not needed to solve the puzzle.

      This number can be determined by calculation, or just counting (it takes a few seconds in PyPy):

      >>> icount(n for n in irange(0, 9999999) if len(set(nsplit(n, 7))) == 4)
      1764000
      

      But if you can’t wait that long (or you want to look at larger values) they can be calculated using a recurrence relation:

      from enigma import (cache, arg, printf)
      
      # how many n-digit phone numbers consisting of k different digits?
      @cache
      def N(n, k):
        if k == 0 or n < k: return 0
        if k == 1: return 10
        return k * N(n - 1, k) + (11 - k) * N(n - 1, k - 1)
      
      n = arg(7, 0, int)
      k = arg(4, 1, int)
      printf("N({n}, {k}) = {r}", r=N(n, k))
      

      I use this function in a “complete” solution, that calculates N(7, 4), and the single digit prime factors of it (and it ensures there are 4 of them), it then finds distributions of these prime digits that give a phone number with a perfect digit sum.

      from enigma import (decompose, divisors, prime_factor, flatten, join, cached, printf)
      
      # how many n-digit phone numbers consisting of k different digits?
      @cached
      def _N(n, k, b):
        if k == 0 or n < k: return 0
        if k == 1: return b
        return k * _N(n - 1, k, b) + (b + 1 - k) * _N(n - 1, k - 1, b)
      
      N = lambda n, k, base=10: _N(n, k, base)
      
      # is a number perfect?
      @cache
      def is_perfect(n):
        return sum(divisors(n)) == 2 * n
      
      # find number 7-digit phone numbers with 4 different digits
      n = N(7, 4)
      
      # determine the prime factorisation
      fs = list(prime_factor(n))
      printf("N(7, 4) = {n} -> {fs}")
      
      # look for single digit primes
      ps = list(p for (p, e) in fs if p < 10)
      printf("primes = {ps}")
      assert len(ps) == 4
      
      # find possible distribution of the prime digits
      for ns in decompose(7, 4, increasing=0, sep=0, min_v=1):
        # the digits of the phone number
        ds = flatten([d] * n for (d, n) in zip(ps, ns))
        # and their sum
        t = sum(ds)
        # is it perfect?
        if is_perfect(t):
          ds.reverse()
          printf("number = {ds} -> dsum = {t}", ds=join(ds))
      

      Like

      • Jim Randell's avatar

        Jim Randell 9:27 am on 7 August 2021 Permalink | Reply

        Here’s an alternative (shorter) program. It starts by looking for possible values of the sum (there is only one candidate that is a perfect number), and then uses the [[ express() ]] function from the enigma.py library to determine possible combinations of 7 digits to achieve the sum. It runs in 49ms.

        Run: [ @replit ]

        from enigma import irange, divisors, express, join, printf
        
        # is a number perfect?
        is_perfect = lambda n: sum(divisors(n)) == 2 * n
        
        # the smallest possible sum is (2+3+5+7)+(2+2+2) = 23
        # the largest  possible sum is (2+3+5+7)+(7+7+7) = 38
        for t in irange(23, 38):
          if not is_perfect(t): continue
        
          # make the sum from the amounts
          for ns in express(t, [2, 3, 5, 7], min_q=1):
            if sum(ns) != 7: continue
        
            # construct the phone number
            ds = join(d * n for (d, n) in zip("7532", reversed(ns)))
            printf("{ds} -> {t}")
        

        Liked by 2 people

        • GeoffR's avatar

          GeoffR 12:37 pm on 7 August 2021 Permalink | Reply

          Perfect numbers are 6, 28, 496, 8128, …
          Only possible perfect number for sum of seven digits is 28
          i.e. for seven digits containing 2, 3, 5 or 7.

          A shorter version using “express” from enigma.py

          
          from enigma import express
          
          # list of potential telephone numbers
          TN = list(express(28, [7, 5, 3, 2], min_q=1))
          
          for t in TN:
            if sum(t) == 7:
              a, b, c, d  = t[0], t[1], t[2], t[3]
              print('7'*a + '5'*b + '3'*c + '2'*d)
          
          
          

          Like

          • Jim Randell's avatar

            Jim Randell 2:22 pm on 7 August 2021 Permalink | Reply

            Or, as a single expression:

            >>> list('7' * d + '5' * c + '3' * b + '2' * a for (a, b, c, d) in express(28, [2, 3, 5, 7], min_q=1) if a + b + c + d == 7)
            ['7553332', '7753222']
            

            Like

          • Frits's avatar

            Frits 9:31 am on 8 August 2021 Permalink | Reply

            Or:

             
            >>> list('7' * (d + 1) + '5' * (c + 1) + '3' * (b + 1) + '2' * (a + 1) for (a, b, c, d) in express(11, [2, 3, 5, 7]) if a + b + c + d == 3)
            

            Like

    • GeoffR's avatar

      GeoffR 8:16 pm on 6 August 2021 Permalink | Reply

      
      from enigma import divisors, dsum, nsplit
      
      tel_list = []
      
      # Re-using Jim's function
      def is_perfect(n):
        return sum(divisors(n)) == 2 * n
      
      def is_descending(n):
        # 7-digit nos. only
        a, b, c, d, e, f, g = nsplit(n)
        if a >= b and b >= c and c >= d and d >= e \
           and e >= f and f >= g:
            return True
        return False
      
      # find 7-digit Tel. Nos. with specified digit pattern
      for n in range(7532222, 7777533):
          s = set(str(n))
          if s == {'7', '5', '3', '2'}:
            if is_descending(n) and is_perfect(dsum(n)):
              tel_list.append(n)
      
      if len(tel_list) == 2:
          print(f"Two tel. nos. are {tel_list[0]} and {tel_list[1]}.")
      
      
      

      Like

    • GeoffR's avatar

      GeoffR 4:26 pm on 7 August 2021 Permalink | Reply

      Setting the output to multiple configurations gives the two telephone numbers.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Both telephone numbers consist of four single digit primes
      set of int: pr = {2, 3, 5, 7};
      
      % 7 digits in telephone numbers
      var pr: A; var pr: B; var pr: C; var pr: D;
      var pr: E; var pr: F; var pr: G; 
      
      % Possible range of telephone numbers
      var 7532222..7777533: TelNum = 1000000*A + 100000*B + 10000*C
       + 1000*D + 100*E + 10*F + G;
      
      % Both telephone numbers include the digits 2, 3, 5 and 7
      constraint {A, B, C, D, E, F, G} == {2, 3, 5, 7};
      
      % 28 is only viable perfect number for the sum of seven digits
      constraint A + B + C + D + E + F + G == 28;
      
      % digits must not be in ascending order
      constraint A >= B /\ B >= C /\ C >= D /\ D >= E
      /\ E >= F /\ F >= G;
      
      solve satisfy;
      
      output ["Tel. No. = " ++ show(TelNum) ];
      
      
      

      Like

    • GeoffR's avatar

      GeoffR 7:28 pm on 8 August 2021 Permalink | Reply

      Module Module1
        ' A Solution in Visual Basic 2019
      
        Sub Main()
          For a As Integer = 1 To 4
            For b As Integer = 1 To 4
              For c As Integer = 1 To 4
                For d As Integer = 1 To 4
      
                  ' tel. no.is 7 digits long
                  If (a + b + c + d = 7) Then
                    ' tel digits sum to the perfect number 28
                    If (7 * a + 5 * b + 3 * c + 2 * d = 28) Then
                      ' form tel. no.
                      Dim TelNo As String
      
                      TelNo = StrDup(a, CStr(7)) + StrDup(b, CStr(5)) +
                              StrDup(c, CStr(3)) + StrDup(d, CStr(2))
                      Console.WriteLine("Tel. No. is {0}", TelNo)
                      Console.ReadLine()
                    End If
                  End If
      
                Next 'd Loop
              Next 'c Loop
            Next  'b loop
          Next   'a loop
      
        End Sub
      
      End Module
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 10:19 am on 5 August 2021 Permalink | Reply
    Tags:   

    Teaser 2809: This and that 

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

    I have written down a list of eleven numbers and then consistently replaced digits by letters, with different letters for different digits. In this way the list becomes:

    SO
    DO
    WHAT
    NOW
    ADD
    AND
    SEND
    IN
    THIS
    AND
    THAT

    The grand total of these eleven numbers is a four-figure number.

    Numerically, what is THIS + THAT?

    [teaser2809]

     
    • Jim Randell's avatar

      Jim Randell 10:19 am on 5 August 2021 Permalink | Reply

      We can find the answer using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in 893ms:

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      "SO + DO + WHAT + NOW + ADD + AND + SEND + IN + THIS + AND + THAT < 10000"
      
      --answer="THIS + THAT"
      

      Solution: THIS + THAT = 2123.

      The result of the sum is 9998.


      To gain a bit more speed we can use the technique implemented in [[ SubstitutedExpression.split_sum() ]], splitting the sum into separate columns with carries between. (See: Teaser 2792).

      Except here we may have to deal with multi digit carries (as there are 11 summands — although with a bit of analysis we can see that single digit carries would be sufficient in this case).

      The following run-file executes in 226ms.

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --symbols="ADEHINOSTWabcdewxyz"
      --distinct="ADEHINOSTW"
      --invalid="0,ADINSTWw"
      --invalid="2-9,ac"
      
      # "SO + DO + WHAT + NOW + ADD + AND + SEND + IN + THIS + AND + THAT = wxyz"
      
      "        W +             S +     T +     T + c + e = w"
      "        H + N + A + A + E +     H + A + H + a + d = ex"
      "S + D + A + O + D + N + N + I + I + N + A + b     = cdy"
      "O + O + T + W + D + D + D + N + S + D + T         =  abz"
      
      --template="(SO + DO + WHAT + NOW + ADD + AND + SEND + IN + THIS + AND + THAT = wxyz)"
      --answer="THIS + THAT"
      

      Like

      • Frits's avatar

        Frits 4:41 pm on 5 August 2021 Permalink | Reply

        To gain more speed in the first program you can also add:

        “W + S + 2 * T < 10"

        For more on this puzzle see:

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

        Like

      • Jim Randell's avatar

        Jim Randell 5:32 pm on 5 August 2021 Permalink | Reply

        Adding a second level of truncation (without worrying about the exact values of the carries) brings the run time down to 80ms. And there is no need for a third level.

        Run: [ @replit ]

        #! python3 -m enigma -rr
        
        SubstitutedExpression
        
        --invalid="0,ADINSTW"
        
        "W + S + T + T < 10"
        "WH + N + A + A + SE + TH + A + TH < 100"
        "SO + DO + WHAT + NOW + ADD + AND + SEND + IN + THIS + AND + THAT < 10000"
        
        --template="(SO + DO + WHAT + NOW + ADD + AND + SEND + IN + THIS + AND + THAT < 10000)"
        --answer="THIS + THAT"
        

        Like

    • GeoffR's avatar

      GeoffR 12:29 pm on 5 August 2021 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      % Digits in main 11 numbers
      var 0..9:S; var 0..9:O; var 0..9:D; var 0..9:W;var 0..9:H;
      var 0..9:A; var 0..9:T; var 0..9:E; var 0..9:N;var 0..9:I;
      
      % Carry digits for sum of 11 numbers
      var 1..7:c1; var 1..7:c2; var 1..7:c3;
      
      % Total of 11 numbers
      var 1..9: a; var 0..9: b; var 0..9: c; var 0..9: d;
      var 1000..9999: total == 1000*a + 100*b + 10*c + d;
      
      constraint S > 0 /\ D > 0 /\ W > 0 /\ N > 0 /\ A > 0 /\ I > 0 /\ T > 0;
      constraint all_different([S, O, D, W, H, A, T, E, N, I]);
      
      % Main sum
      %     S O
      %     D O
      % W H A T
      %   N O W
      %   A D D
      %   A N D
      % S E N D
      %     I N
      % T H I S
      %   A N D 
      % T H A T
      %--------
      % a b c d
      %--------
      
      % Adding 4 columns, with carry digits, starting at right hand column
      constraint c1 == (O + O + T + W + D + D + D + N + S + D + T) div 10
      /\ d == (O + O + T + W + D + D + D + N + S + D + T) mod 10;
      
      constraint c2 == (c1 + S + D + A + O + D + N + N + I + I + N + A) div 10
      /\ c == (c1 + S + D + A + O + D + N + N + I + I + N + A) mod 10;
      
      constraint c3 == (c2 + H + N + A + A + E + H + A + H) div 10
      /\ b == (c2 + H + N + A +A +  E + H + A + H) mod 10;
      
      constraint a == c3  + W + S + T + T;
      
      % Sum 2 -  THIS + THAT
      var 0..1:c4; var 0..2:c5; var 0..2:c6;
      var 1..9: e; var 0..9: f; var 0..9: g; var 0..9: h;
      var 1000..9999: efgh = 1000*e + 100*f + 10*g + h;
      
      %  T H I S
      %  T H A T
      %  -------
      %  e f g h
      %---------
      
      constraint c4 == (S + T) div 10 /\ h == (S + T ) mod 10;
      
      constraint c5 == (c4 + I + A) div 10 /\  g == (c4 + I + A) mod 10;
      
      constraint c6 == (c5 + H + H) div 10 /\ f == (c5 + H + H) mod 10;
      
      constraint e == c6 + T +  T;
      
      constraint efgh == 1000*e + 100*f + 10*g + h;
      
      solve satisfy;
      
      output ["Total of 11 numbers = " ++ show(total ) ++ "\n" 
      ++ "THIS + THAT = " ++ show(efgh) ];
      
      % Total of 11 numbers = 9998
      % THIS + THAT = 2123
      % ----------
      % ==========
      
      

      Like

  • Unknown's avatar

    Jim Randell 9:20 am on 3 August 2021 Permalink | Reply
    Tags:   

    Teaser 2807: Pentagons 

    From The Sunday Times, 10th July 2016 [link] [link]

    I have taken five identical straight rods and joined each to the next by a hinge to make a flexible ring. With this ring I can make lots of different pentagonal shapes, and in particular I can make lots of pentagons with area equal to a whole number of square centimetres. The largest whole-numbered area achievable is a two-figure number, and the smallest whole-numbered area achievable is another two-figure number. In fact these two numbers use the same two digits but in the reverse order.

    What is the largest whole-numbered area achievable?

    [teaser2807]

     
    • Jim Randell's avatar

      Jim Randell 9:21 am on 3 August 2021 Permalink | Reply

      The maximal area is achieved with a cyclic pentagon. If the sides have length x the area is given by:

      Amax(x) = (x² / 4) √(5(5 + 2√5))

      If this value is not an integer, the maximum integer-valued area will be achieved by a slight deformation of the pentagon to give the floor of this value.

      I believe the minimal area is achieved with a degenerate pentagon where two of the sides are collapsed to give an equilateral triangle with a protruding spike.

      Amin(x) = (x² / 4) √3

      Again, if this value is not an integer, the minimum integer-valued area will be achieved by opening up the collapsed spike slightly (to give an actual pentagon), and increase the area to the ceiling of this value.

      This Python program considers possible Amax and Amin values (each 2 digits, one the reverse of the other), and calculates the range of x values that would give these values. If there are any common values then we have a viable solution. It runs in 50ms.

      from enigma import (irange, nreverse, sqrt, fdiv, printf)
      
      # area multipliers
      maxA = fdiv(sqrt(5 * (5 + 2 * sqrt(5))), 4)
      minA = fdiv(sqrt(3), 4)
      
      # consider 2 digit maximal area
      for M in irange(10, 99):
        m = nreverse(M)
        if not (9 < m < M): continue
      
        # calculate range of x values based on M
        xmin1 = sqrt(M, maxA)
        xmax1 = sqrt(M + 1, maxA)
      
        # calculate range of x value based on m
        xmin2 = sqrt(m - 1, minA)
        xmax2 = sqrt(m, minA)
      
        # intersect the intervals
        xmin = max(xmin1, xmin2)
        xmax = min(xmax1, xmax2)
        if not (xmin < xmax): continue
        printf("Amax={M} Amin={m} -> x = [{xmin}, {xmax}]")
      

      Solution: The largest whole-number area achievable is 61 cm².

      And the smallest whole-number area achievable is 16 cm².

      The length of the rods is between 5.995 cm and 6.003 cm, so (although not mentioned in the puzzle) an integer length (of 6 cm) for the rods could be intended.

      For 6 cm rods we have:

      Amax ≈ 61.937 cm²
      Amin ≈ 15.588 cm²

      Like

    • Frits's avatar

      Frits 5:03 pm on 4 August 2021 Permalink | Reply

      Using Jim’s code as a base but avoiding square root calculations.
      The internal run time is 400 nanoseconds (with PyPy).

       
      # "x^2" related multipliers
      bigMult = 4 / (5 * (5 + 2 * 5**.5))**.5
      smallMult = 4 / 3**.5
      
      # consider 2 digit maximal area
      for t in range(2, 10):
        for u in range(1, t):
          M = 10 * t + u
          m = u * 10 + t
        
          # calculate range of x^2 values
          x2max1 = (M + 1) * bigMult
          x2min2 = (m - 1) * smallMult
      
          # leave inner loop if already a max is smaller than a min
          # as x2min2 grows faster than x2max1 for subsequent entries
          if x2max1 < x2min2: break
      
          x2min1 = x2max1 - bigMult
          x2max2 = x2min2 + smallMult
      
          # intersect the intervals
          x2min = max(x2min1, x2min2)
          x2max = min(x2max1, x2max2)
          if not(x2min < x2max): continue
          print(f"answer: {M} cm2")
      

      Like

  • Unknown's avatar

    Jim Randell 9:38 pm on 31 July 2021 Permalink | Reply
    Tags: by: Oliver Tailby   

    Teaser 3071: Three-cornered problem 

    From The Sunday Times, 1st August 2021 [link] [link]

    I have a set of equal-sized equilateral triangular tiles, white on one face and black on the back. On the white side of each tile I have written a number in each corner. Overall the numbers run from 1 to my age (which is less than thirty). If you picture any such tile then it occurs exactly once in my set (for example, there is just one tile containing the numbers 1, 1 and 2; but there are two tiles containing the numbers 1, 2 and 3).

    The number of tiles that contain at least one even number is even.

    The number of tiles that contain at least one odd number is odd.

    The number of tiles that contain at least one multiple of four is a multiple of four.

    How old am I?

    [teaser3071]

     
    • Jim Randell's avatar

      Jim Randell 10:01 pm on 31 July 2021 Permalink | Reply

      This Python program constructs the possible triangular tiles for increasing ages, and keeps count of the number that satisfy the given conditions. It runs in 73ms.

      from enigma import (irange, subsets, uniq, printf)
      
      # count triangles with ...
      evens = 0  # ... at least one even number
      odds = 0  # ... at least one odd number
      mul4s = 0  # ... at least one multiple of 4
      
      # canonical form (by rotation)
      def canonical(a, b, c):
        return min((a, b, c), (b, c, a), (c, a, b))
      
      # consider triangles with largest number n
      for n in irange(1, 29):
        # consider rotationally distinct triangles
        for tri in uniq(canonical(n, a, b) for (a, b) in subsets(irange(1, n), size=2, select="M")):
          # increase the counts
          if any(x % 2 == 0 for x in tri): evens += 1
          if any(x % 2 == 1 for x in tri): odds += 1
          if any(x % 4 == 0 for x in tri): mul4s += 1
      
        # output solution
        if evens % 2 == 0 and odds % 2 == 1 and mul4s % 4 == 0:
          printf("n={n} [evens={evens} odds={odds} mul4s={mul4s}]")
      

      Solution: Your age is 17.

      The total number of triangular tiles for any particular age is given by OEIS A006527 [link]:

      a(n) = n(n² + 2) / 3


      There is the possibility of a solution at age = 1. In this case there is only 1 tile in the set — (1, 1, 1). But the setter might be considering that the numbers of tiles in each category is non-zero (also 1 is a little young to be setting such a puzzle). In any case, we are told that there are two (1, 2, 3) tiles, so we know the age must be at least 3.

      In general we find solutions to the puzzle at ages of the form (16k + 1).

      Like

      • Frits's avatar

        Frits 1:23 pm on 2 August 2021 Permalink | Reply

        Similar.

         
        # consider rotationally distinct triangles containing number n
        def triangles(n):
          for x in range(n, 0, -1):
            for y in range(x, 0, -1): 
              yield [n, x, y]
          for x in range(n - 2, 0, -1):    
            for y in range(n - 1, x, -1): 
              yield [n, x, y]
         
        odds, evens, mul4s = 0, 0, 0
        
        print("age evens  odds mlt4s")
        for age in range(1, 30):
          for tri in triangles(age):
            
            if any(x % 2 == 0 for x in tri): evens += 1
            if any(x % 2 for x in tri): odds += 1
            if any(x % 4 == 0 for x in tri): mul4s += 1
          
          if mul4s % 4 == 0 and evens % 2 == 0 and odds % 2:
            print(f"{age:>3} {evens:>5} {odds:>5} {mul4s:>5}") 
        

        Like

  • Unknown's avatar

    Jim Randell 9:08 am on 29 July 2021 Permalink | Reply
    Tags:   

    Teaser 2806: Jack’s jigsaw 

    From The Sunday Times, 3rd July 2016 [link] [link]

    I made Jack a jigsaw. I started with a rectangle of card that I had cut from an A4 sheet and then I cut the rectangle into pieces. There were some square pieces of sizes (in centimetres) 1×1, 2×2, 3×3, … with the largest having side equal to Jack’s age. The remaining pieces were rectangles of sizes 1×2, 2×3, 3×4, … with the largest length amongst them again being Jack’s age. Then Jack succeeded in putting them together again to form a rectangle, but the perimeter of his rectangle was smaller than the perimeter of my original rectangle.

    What were the lengths of the sides of my original rectangle?

    [teaser2806]

     
    • Jim Randell's avatar

      Jim Randell 9:09 am on 29 July 2021 Permalink | Reply

      The original rectangle is cut from an A4 sheet of card (dimensions = 21.0cm × 29.7cm).

      The maximum square that we can make would be 21cm × 21cm, which puts an upper limit on Jack’s age. However the area of an A4 sheet places a smaller upper limit on Jack’s age, as the sum of the area of the pieces for age 10 would be 715cm² – larger than the area of a single A4 sheet.

      This Python program considers possible ages, and calculates the total area of the rectangular pieces. It then looks for possible dimensions and perimeters for packed rectangles. And looks for two of these that could be the setters and Jack’s rectangles. It then uses the rectpack.py library (see: Enigma 1491, Teaser 2650, Teaser 3069) to attempt to pack the pieces into the required rectangle.

      It runs in 1.94s.

      Run: [ @replit ]

      from enigma import irange, divisors_pairs, cached, printf
      from rectpack import pack_tight, output_grid, by_area
      
      # how to pack a set of rectangles
      pack = lambda x, y, rs: pack_tight(x, y, by_area(rs))
      
      # look for a packing
      @cached
      def check(n, x, y):
        # collect the pieces
        ps = list((k, k) for k in irange(1, n))
        ps += list((k - 1, k) for k in irange(2, n))
      
        # attempt a packing
        printf("[n = {n} -> pack {x} x {y} ...]")
        for s in pack(x, y, ps):
          output_grid(x, y, s)
          return True
        printf("[-> no packing]")
        return False
      
      # total area
      t = 0
      for n in irange(1, 21):
        t += n * (2 * n - 1)
        if t > 624: break
      
        printf("[n={n}; t={t}]")
      
        # find possible dimensions and perimeter for the packed rectangles
        rs = dict(((a, b), 2 * (a + b)) for (a, b) in divisors_pairs(t) if not(n > a))
      
        # consider the setter's rectangle
        for ((a1, b1), p1) in rs.items():
          # it must fit on an A4 sheet
          if a1 > 21 or b1 > 29: continue
      
          # and look for another rectangle, with a smaller perimeter
          for ((a2, b2), p2) in rs.items():
            if not(p2 < p1): continue
      
            # check packing is possible
            if check(n, a1, b1) and check(n, a2, b2):
              # output solution
              printf("n={n}: {a1}x{b1} (p={p1}) -> {a2}x{b2} (p={p2}) [*** SOLUTION ***]")
      

      Solution: The original rectangle measured 12cm × 21cm.

      Here is a diagram of the two packings (12×21 → 14×18):

      There will be many more different packings, as any sub-rectangle consisting of two (or more) pieces can be flipped round. (In fact there are 5156 different packings for the 12×21 rectangle, and 1307 for the 14×18 rectangle).


      The program assumes that the original rectangle was cut parallel to the sides of the A4 sheet, so the smaller side must be no more than 21cm and the longer side no more than 29cm. But rectangles with a dimension larger than these could potentially be made by cutting a rectangle not aligned with the sides. (e.g. We could cut a 7×30 rectangle obliquely from a sheet of A4).

      So there are potentially two possible ages, listed here along with possible rectangles (and perimeters):

      n=7: 7×36 (86), 9×28 (74), 12×21 (66), 14×18 (64)
      n=9: 15×35 (100), 21×25 (92)

      It is not possible to pack the 7×36 or 9×28 rectangles, so there are only 2 viable solutions:

      n=7: 12×21 (66) → 14×18 (64)
      n=9: 15×35 (100) → 21×25 (92)

      In the n=7 case the 12×21 rectangle can easily be cut from an A4 sheet (with a single cut), so this is a viable solution. (Note that as it is possible to cut the 9×28 rectangle from an A4 sheet, we need to show that it cannot be packed in order to rule out multiple solutions).

      In the n=9 case the 15×35 rectangle cannot be cut from an A4 sheet (even obliquely), so this is not a viable solution. (Although the 21×25 rectangle could be cut from an A4 sheet (again with a single cut), the puzzle requires that the rectangle with the larger perimeter be cut out from the A4 sheet).

      Like

      • Frits's avatar

        Frits 2:48 pm on 30 July 2021 Permalink | Reply

        @Jim,

        Checking combination 9 x 28 takes a long time.

        Running time will be under half a second (with CPython) if you add the following to function check (or incorporate it in rectpack.py):

         
        # skip if stacked wide pieces exceed height
        if sum(min(a, b) for a, b in ps if 2 * min(a, b) > x) > y: 
          return False
        

        Like

        • Jim Randell's avatar

          Jim Randell 11:42 am on 31 July 2021 Permalink | Reply

          @Frits: Thanks for the suggestion.

          I’ve added a [[ pack() ]] function to rectpack.py that does a couple of quick checks before starting the packing.

          (And I also added [[ pack_uniq() ]] which generates solutions that are symmetrically distinct, see: Teaser 3069).

          Like

  • Unknown's avatar

    Jim Randell 9:14 am on 27 July 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 817: Fish in the swim 

    From The Sunday Times, 20th March 1977 [link]

    The goldfish and the shubunkin swim in straight lines and at the same speed, and they always make right-angled turns when they do turn.

    From a point on the edge of the Round Lake (a perfect circle, of course) the goldfish swam due north and the shubunkin swam in a direction somewhere between north and east.

    After an hour the goldfish reached the edge of the lake and turned right; simultaneously the shubunkin turned right.

    Half an hour later the shubunkin reached the edge of the lake, and 15 minutes after that the goldfish again reached a point on the edge of the lake.

    The shubunkin, having rested for 15 minutes, wants the longest possible swim now without reaching a point on the edge of the lake.

    What course should the fish steer?

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

    [teaser817]

     
    • Jim Randell's avatar

      Jim Randell 9:14 am on 27 July 2021 Permalink | Reply

      The goldfish starts at A, swims due north to B (in 60 minutes), and then due east to C (in 45 minutes).

      If we use units of distance corresponding to how far a fish can travel in 15 minutes we get AB = 4, BC = 3.

      So, ABC is a (3, 4, 5) triangle, hence AC is a diameter of lake, and so the lake has radius 5/2.

      In 60 minutes, the shubunkin swam from A to X (AX = 4), and in 30 minutes swam from X to Y (XY = 2).

      The subunkin then wishes to make the longest possible straight line journey, which is the diameter of the lake YZ.

      We need to determine the direction of YZ (which is the same as the direction OZ).

      Labelling the angle BAC as φ and COZ as θ then the direction OZ (amount west of north) is given by:

      d = θ − φ

      From triangle ABC we have:

      cos(φ) = 4/5

      And using the cosine rule in triangle AOY to determine the angle AOY = θ, we have:

      4² + 2² = 2(5/2)² − 2(5/2)(5/2)cos(θ)
      cos(θ) = −3/5

      Hence the direction OZ is:

      d = acos(−3/5) − acos(4/5)

      And:

      d = acos(−3/5) − acos(4/5)
      d = asin(3/5) + asin(4/5)
      d = φ + (90° − φ)
      d = 90°

      Solution: The shubunkin should head due west.

      So a more accurate representation of the situation is:

      Where OXY is a (3/2, 4/2, 5/2) triangle.

      Like

  • Unknown's avatar

    Jim Randell 8:46 am on 25 July 2021 Permalink | Reply
    Tags: by: C. Chittock   

    Brain-Teaser 41: Selecting a team 

    From The Sunday Times, 31st December 1961 [link]

    The Cricket Selection Committee of the State of Bonga have chosen 13 players — six batsman, five bowlers, an all-rounder and a wicketkeeper — for their Test Match against Donga, the final choice on the day of the match being left to the captain.

    The captain decides that the two to be omitted must be a batsman and a bowler, a batsman and the all-rounder, or a bowler and the all-rounder: but, distrusting his judgment of individuals, he consults the Chief Magician, who surprisingly assures him that if the ages of the eleven total 282, the team will be invincible.

    A check of the players’ ages shows that three (two bowlers and the all-rounder) are aged 24: the ages of the remainder are all different, ranging from 21 to 31, the captain, aged 31, being the oldest. The ages of the three remaining bowlers total 83.

    The captain discovers that there is only one possible choice which will comply with the Magician’s advice, and is relieved to find that he is not under the necessity of standing down himself.

    What is the wicketkeeper’s age?

    [teaser41]

     
    • Jim Randell's avatar

      Jim Randell 8:47 am on 25 July 2021 Permalink | Reply

      There are 3 players who are 24, and 1 of each of the other ages from 21 to 31.

      So, the total for all 13 players being 334.

      We are looking to select 11 players with a total of 282. So we need to discard 2 players, whose ages sum to 52.

      This Python program runs in 51ms.

      Run: [ @replit ]

      from itertools import product
      from enigma import irange, diff, subsets, join, printf
      
      # the squad is:
      #  [A] 1 all-rounder (24)
      #  [BCDEF] 5 bowlers, 2 @ (24), remaining 3 have combined age of 83
      #  [GHIJKL] 6 batsmen
      #  [W] 1 wicket keeper
      allrs = 'A'
      bowls = 'BCDEF'
      bats = 'GHIJKL'
      
      # unallocated ages = 21 - 31, except 24
      ages = diff(irange(21, 31), [24])
      
      # choose the ages of the 3 bowlers that sum to 83
      for bs in subsets(ages, size=3, fn=list):
        if sum(bs) != 83: continue
      
        # choose the age of the wicket keeper
        for wk in ages:
          if wk in bs: continue
      
          # map names to ages
          m = dict(A=24, B=24, C=24, W=wk)
          m.update(zip(diff(bowls, m.keys()), bs)) # remaining bowlers
          m.update(zip(bats, diff(ages, bs + [wk]))) # batsmen
      
          # look for excluded combinations that add up to 334 - 282 = 52
          exclude = lambda xs, ys: list((x, y) for (x, y) in product(xs, ys) if m[x] + m[y] == 52)
          xs = exclude(bats, bowls) + exclude(bats, allrs) + exclude(bowls, allrs)
      
          # there is only one possible set of excluded players
          if len(xs) == 1:
            xs = xs[0]
            # and they don't include the captain (age = 31)
            if any(m[x] == 31 for x in xs): continue
      
            # output solution
            printf("wk = {wk} [excluded = {xs}]", xs=join(sorted(xs), sep=" "))
      

      Solution: The wicket-keeper is 23.

      A bowler (28) and the all-rounder (24) are dropped from the team.

      The ages of squad are:

      all-rounder: (24)
      bowlers: 24, 24, 26, (28), 29
      batsmen: 21, 22, 25, 27, 30, 31
      wicket-keeper: 23

      Like

  • Unknown's avatar

    Jim Randell 4:59 pm on 23 July 2021 Permalink | Reply
    Tags:   

    Teaser 3070: Film binge 

    From The Sunday Times, 25th July 2021 [link] [link]

    I’m going to have a day binge-watching films. My shortlist is:

    Quaver, starring Amerton, Dunino, Emstrey, Fairwater and Joyford;
    Rathripe, starring Amerton, Codrington, Fairwater, Glanton and Ingleby;
    Statecraft, starring Amerton, Codrington, Dunino, Hendy and Ingleby;
    Transponder, starring Codrington, Dunino, Emstrey, Hendy and Ingleby;
    Underpassion, starring Blankney, Emstrey, Fairwater, Hendy and Ingleby;
    Vexatious, starring Amerton, Blankney, Dunino, Emstrey and Joyford;
    Wergild, starring Blankney, Fairwater, Glanton, Hendy and Joyford;
    X-axis, starring Blankney, Codrington, Fairwater, Glanton and Ingleby;
    Yarborough, starring Blankney, Dunino, Glanton, Hendy and Joyford;
    Zeuxis, starring Amerton, Codrington, Emstrey, Glanton and Joyford.

    I dislike Ingleby and Joyford, so I don’t want either of them in more than two films; but I want to see each of the others in at least two films.

    Which are the films I should watch?

    [teaser3070]

     
    • Jim Randell's avatar

      Jim Randell 5:17 pm on 23 July 2021 Permalink | Reply

      A directed search would let us prune away subsets with too much I and J in, but on a problem of this size we can just examine all possible subsets of films to see which collections meet the criteria.

      The following Python program runs in 67ms.

      Run: [ @replit ]

      from enigma import subsets, union, multiset, join, printf
      
      # the films and the stars
      films = {
        'Q': 'ADEFJ', 'R': 'ACFGI', 'S': 'ACDHI', 'T': 'CDEHI', 'U': 'BEFHI',
        'V': 'ABDEJ', 'W': 'BFGHJ', 'X': 'BCFGI', 'Y': 'BDGHJ', 'Z': 'ACEGJ',
      }
      stars = union(films.values())
      
      # selection criteria:
      # I, J in no more than 2 films, otherwise in at least 2 films
      fn = lambda k, n: (n <= 2 if k in 'IJ' else n >= 2)
      
      # choose films
      for ks in subsets(films.keys(), min_size=2):
        # collect the stars
        ss = multiset.from_seq(*(films[k] for k in ks))
        # perform the check
        if all(fn(k, ss.count(k)) for k in stars):
          printf("films = {ks}", ks=join(ks, sep=' '))
      

      Solution: The chosen films are: Rathripe, Transponder, Vexatious, Wergild.

      For this collection, each of the stars (including I and J) are in exactly 2 of the films. And this is the only collection that meets the required condition.

      Like

      • Jim Randell's avatar

        Jim Randell 1:04 pm on 26 July 2021 Permalink | Reply

        The particular set of films used in the puzzle allow us to make some shortcuts:

        As exactly one of I or J is in each of the films, we can see that we can be looking for no more than 4 films (2 with I and 2 with J). And each of the films has exactly 4 of the other stars in.

        So to see at least 2 films involving each of the other stars we are going to need to see at least 8×2/4 = 4 films. So of the 20 stars involved in each of the 4 films, each must appear twice.

        Hence we need to look for exactly 4 films, so we could just pass [[ size=4 ]] at line 15 of my original program. Or, more efficiently, we could consider combinations of 2 films involving I and 2 films involving J.

        from enigma import subsets, join, printf
        
        # the films and the stars
        filmsI = {
          #     ABCDEFGHIJ
          'R':  1010011010,
          'S':  1011000110,
          'T':    11100110,
          'U':   100110110,
          'X':   110011010,
        }
        
        filmsJ = {
          #     ABCDEFGHIJ
          'Q':  1001110001,
          'V':  1101100001,
          'W':   100011101,
          'Y':   101001101,
          'Z':  1010101001,
        }
        
        # collect sums for pairs of films for I and J
        pairs = lambda d: dict((d[x] + d[y], (x, y)) for (x, y) in subsets(d.keys(), size=2))
        (psI, psJ) = (pairs(filmsI), pairs(filmsJ))
        
        # consider a pair of films for I ...
        target = 2222222222
        for (sI, fsI) in psI.items():
          # ... with a corresponding value for J
          fsJ = psJ.get(target - sI, None)
          if fsJ is not None:
            printf("films = {fs}", fs=join(sorted(fsI + fsJ), sep=' '))
        

        Technically this program will find a solution, but the selection of films in this particular puzzle have been chosen so there is a unique subset that give the required answer.

        Note: Placing leading zeroes in the film values does not work in Python 3 ([[ 0011100110 ]] is not a valid integer literal, although [[ int('0011100110') ]] does work). In Python 2.7 [[ 0011100110 ]] is a valid integer literal, but is interpreted as an octal (base 8) number, so although the program does run, it will not give the correct answer. (Which is presumably why this was made an error in Python 3).

        To allow leading zeroes we could do everything in octal, by prefixing with 0o (or in hexadecimal, using the 0x prefix – there is no corresponding 0d prefix for decimal), including the target value 2222222222.

        Like

  • Unknown's avatar

    Jim Randell 6:42 am on 22 July 2021 Permalink | Reply
    Tags:   

    Teaser 2805: Greek urns 

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

    I have three Greek urns. I took some balls (consisting of an odd number of red balls and some black balls) and I placed one or more ball in the first urn, one or more in the second, and the rest in the third. If you chose an urn at random and then a ball at random from that urn, then overall there would be a 50 per cent chance of getting a red ball.

    Then I moved some black balls from one of the urns to another. In this new situation, if you chose an urn and then a ball there was a 75 per cent chance of getting a red. In fact, with this set of balls and urns it would be impossible to get a higher percentage than that.

    How many red balls and how many black balls were there?

    [teaser2805]

     
    • Jim Randell's avatar

      Jim Randell 6:43 am on 22 July 2021 Permalink | Reply

      The following Python program runs in 126ms.

      Run: [ @replit ]

      from enigma import Rational, irange, inf, printf
      
      Q = Rational()
      
      # return ((r1, b1), (r2, b2), (r3, b3)) from R red, B black balls
      # as (P1, P2) where
      # P1 = configuration with P = 1/2
      # P2 = configuration with P = 3/4
      def solve(R, B):
        # record probabilities: P1 = 1/2, P2 = 3/4, P3 > 3/4
        (P1, P2) = (list(), list())
      
        # place n1 balls in urn 1
        T = R + B
        for n1 in irange(1, T - 2):
          # how many are red?
          for r1 in irange(0, min(R, n1)):
            # and the rest are black
            b1 = n1 - r1
            # probability of choosing a red ball from urn 1
            p1 = Q(r1, n1)
      
            # place n2 balls in urn 2 (n2 <= n1)
            for n2 in irange(1, min(n1, T - n1)):
              # how many are red?
              for r2 in irange(0, min(R - r1, n2)):
                # and the rest are black
                b2 = n2 - r2
                # probability of choosing a red ball from urn 2
                p2 = Q(r2, n2)
      
                # and urn 3 (n3 <= n2)
                n3 = T - n1 - n2
                if n3 > n2: continue
                r3 = R - r1 - r2
                b3 = n3 - r3
                if b3 < 0: continue
                p3 = (0 if n3 == 0 else Q(r3, n3))
      
                # total probability of drawing a red ball
                p = Q(p1 + p2 + p3, 3)
                if p == Q(1, 2):
                  P1.append(((r1, b1), (r2, b2), (r3, b3)))
                elif p == Q(3, 4):
                  P2.append(((r1, b1), (r2, b2), (r3, b3)))
                elif p > Q(3, 4):
                  return
      
        # look for a viable pair from P1 x P2
        for ((r1, b1), (r2, b2), (r3, b3)) in P1:
          for ((r1_, b1_), (r2_, b2_), (r3_, b3_)) in P2:
            # the number of red balls in each urn must be the same
            if not(r1_ == r1 and r2_ == r2 and r3 == r3_): continue
            # and one of the sets of blacks is the same
            if not(b1 == b1_ or b2 == b2_ or b3 == b3_): continue
            # viable configuration
            yield (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_)))
      
      # find the first viable red/black configuration
      def run():
        # total number of balls
        for T in irange(2, inf):
          # number of red balls is odd
          for R in irange(1, T - 1, step=2):
            # and the rest are black
            B = T - R
      
            # look for solutions with R reds, B blacks
            n = 0
            for (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_))) in solve(R, B):
              printf("({r1}r + {b1}b) ({r2}r + {b2}b) ({r3}r + {b3}b) -> ({r1_}r + {b1_}b) ({r2_}r + {b2_}b) ({r3_}r + {b3_}b)")
              n += 1
      
            if n > 0:
              printf("R={R} B={B} [T={T}; {n} configurations]")
              return
      
      run()
      

      Solution: There were 7 red balls, and 15 black balls.

      Possible configurations are:

      A: (5r + 10b) → P(red) = 1/3
      B: (1r + 5b) → P(red) = 1/6
      C: (1r + 0b) → P(red) = 1
      Total P(red) = (1/3 + 1/6 + 1) / 3 = 1/2

      Move 5b from B to A:

      A: (5r + 15b) → P(red) = 1/4
      B: (1r + 0b) → P(red) = 1
      C: (1r + 0b) → P(red) = 1
      Total P(red) = (1/4 + 1 + 1) / 3 = 3/4

      A: (5r + 9b) → P(red) = 5/14
      B: (1r + 6b) → P(red) = 1/7
      C: (1r + 0b) → P(red) = 1
      Total P(red) = (5/14 + 1/7 + 1) / 3 = 1/2

      Move 6b from B to A:

      A: (5r + 15b) → P(red) = 1/4
      B: (1r + 0b) → P(red) = 1
      C: (1r + 0b) → P(red) = 1
      Total P(red) = (1/4 + 1 + 1) / 3 = 3/4


      The program stops after the first red/black configuration it finds, but we can let it look for further solutions, but it gets a bit slow for T > 100 (and doesn’t find any further solutions).

      Assuming the maximum probability of choosing a red ball for R red balls and B black balls is given by the following configuration:

      ((R − 2)r + (B)b) (1r + 0b) (1r + 0b)

      (so we require R ≥ 2).

      Then for the overall probability of choosing a red to be 3/4 we have:

      (1/3)(((R − 2) / (R + B − 2)) + (1/1) + (1/1)) = 3/4
      (R − 2) / (R + B − 2) = 1/4
      4R − 8 = R + B − 2
      B = 3R − 6

      Which means for any R value, there is only one corresponding B value.

      So the final configuration is:

      ((R − 2)r + (3R − 6)b) (1r + 0b) (1r + 0b)

      All the black balls are in one urn, so we can suppose x of them were moved from an urn containing (1r + xb), making the original configuration:

      ((R − 2)r + (3R − 6 − x)b) (1r + xb) (1r + 0b)

      And the overall probability of choosing a red is 1/2, so:

      (1/3)(((R − 2) / (4R − 8 − x)) + (1 / (1 + x)) + 1) = 1/2
      ((R − 2) / (4R − 8 − x)) + (1 / (1 + x)) = 1/2
      (2R − 4)(1 + x) + 2(4R − 8 − x) = (1 + x)(4R − 8 − x)
      10R − 6x + 2Rx − 20 = 4R − 8 − x + 4Rx − 8x − x²
      x² + (3 − 2R)x + (6R − 12) = 0

      So for any R value, there are at most 2 viable x values.

      This allows us to quickly check for higher solutions (but we don’t find any):

      from enigma import irange, quadratic, printf
      
      for R in irange(3, 1000, step=2):
        B = 3 * R - 6
        # look for x values
        for x in quadratic(1, 3 - 2 * R, 6 * R - 12, domain="Z"):
          if x > 0:
            printf("R={R} B={B}; x={x}")
      

      Continuing with the analysis, we can show there are no higher solutions.

      R is an odd integer, say R = 2k + 3, for some non-negative integer k. Then:

      x² + (3 − 2(2k + 3))x + (6(2k + 3) − 12) = 0
      x² − (4k + 3)x + (12k + 6) = 0

      And using the quadratic formula, we see this has solutions:

      2x = (4k + 3) ± sqrt((4k − 3)² − 24)

      Both sides are integers, so: (4k − 3)² − 24 must be an odd perfect square, say (2z + 1)²:

      (4k − 3)² − 24 = (2z + 1)²
      (4k − 3)² − (2z + 1)² = 24
      (4k + 2z − 2)(4k − 2z − 4) = 24

      The LHS is the product of 2 integers, (a, b) that give 24.

      4k + 2z − 2 = a
      4k − 2z − 4 = b
      ⇒ k = (a + b + 6) / 8

      So by looking at the finite set of pairs of integers whose product is 24, we can determine all possible values of k, and hence of R, B, x, and verify that the solutions found above are the only possible solutions.

      from enigma import divisors_pairs, div, quadratic, printf
      
      # find sum of integer pairs that multiply to x
      def pairs(n):
        for (a, b) in divisors_pairs(n):
          s = a + b
          yield s
          yield -s
      
      # find possible values for k
      for s in pairs(24):
        k = div(s + 6, 8)
        if k is None or k < 0: continue
        R = 2 * k + 3
        B = 3 * R - 6
        # and corresponding values for x
        for x in quadratic(1, 3 - 2 * R, 6 * R - 12, domain="Z"):
          if x > 0:
            printf("R={R} B={B}; x={x} [k={k} s={s}]")
      

      Like

      • Frits's avatar

        Frits 11:02 am on 22 July 2021 Permalink | Reply

        @Jim, Interesting.

        We can speed up the general program by (among others):

         
        1 - do the n3 checks earlier (lines 32-34)
        2 - demand n3 > 0 and all r1, r2, r3 > 0 as otherwise a 75 per cent chance is impossible by moving black balls.
        3 - let T start from 6 as (1, 3), (1, 0), (1, 0) is the first viable option to get chance 75 per cent.
        

        Like

        • Jim Randell's avatar

          Jim Randell 3:03 pm on 22 July 2021 Permalink | Reply

          Yes. It’s more efficient to use a [[ decompose() ]] type function to distribute the balls.

          The following Python program only take 75ms, and can check up to T = 128 in a few minutes.

          Run: [ @replit ]

          from enigma import Rational, irange, inf, printf
          
          Q = Rational()
          
          # decompose t into k ascending numbers
          def decompose(t, k, m=1, ns=[]):
            if k == 1:
              if not(t < m):
                yield ns + [t]
            else:
              k_ = k - 1
              for n in irange(m, t - k_ * m):
                yield from decompose(t - n, k_, n, ns + [n])
          
          # return ((r1, b1), (r2, b2), (r3, b3)) from R red, B black balls as (P1, P2) where
          # P1 = configurations with P = 1/2
          # P2 = configurations with P = 3/4
          def solve(R, B):
            # record probabilities: P1 = 1/2, P2 = 3/4, P3 > 3/4
            (P1, P2) = (list(), list())
          
            # choose a distribution for the number of balls in each urn
            for (n3, n2, n1) in decompose(R + B, 3):
              # how many red balls in urn1?
              for r1 in irange(0, min(R, n1)):
                # and the rest are black
                b1 = n1 - r1
                # probability of choosing a red ball from urn 1
                p1 = Q(r1, n1)
          
                # how many red balls in urn2?
                for r2 in irange(0, min(R - r1, n2)):
                  # and the rest are black
                  b2 = n2 - r2
                  # and urn 3 (n3 <= n2)
                  r3 = R - r1 - r2
                  b3 = B - b1 - b2
                  if b3 < 0: continue
                  # probabilities of choosing a red ball from urn 2 and urn 3
                  p2 = Q(r2, n2)
                  p3 = (0 if n3 == 0 else Q(r3, n3))
          
                  # total probability of drawing a red ball
                  p = Q(p1 + p2 + p3, 3)
                  if p == Q(1, 2):
                    P1.append(((r1, b1), (r2, b2), (r3, b3)))
                  elif p == Q(3, 4):
                    P2.append(((r1, b1), (r2, b2), (r3, b3)))
                  elif p > Q(3, 4):
                    return
          
            # look for a viable pair from P1 x P2
            for ((r1, b1), (r2, b2), (r3, b3)) in P1:
              for ((r1_, b1_), (r2_, b2_), (r3_, b3_)) in P2:
                # the number of red balls in each urn must be the same
                if not(r1_ == r1 and r2_ == r2 and r3 == r3_): continue
                # and one of the sets of blacks is the same
                if not(b1 == b1_ or b2 == b2_ or b3 == b3_): continue
                # viable configuration
                yield (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_)))
          
          # find the first viable red/black configuration
          def run():
            # total number of balls
            for T in irange(2, inf):
              for R in irange(1, T - 1, step=2):
                # and the rest are black
                B = T - R
          
                # look for solutions with R reds, B blacks
                n = 0
                for (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_))) in solve(R, B):
                  printf("({r1}r + {b1}b) ({r2}r + {b2}b) ({r3}r + {b3}b) -> ({r1_}r + {b1_}b) ({r2_}r + {b2_}b) ({r3_}r + {b3_}b)")
                  n += 1
          
                if n > 0:
                  printf("R={R} B={B} [T={T}; {n} configurations]")
                  return
          
          run()
          

          Like

    • Frits's avatar

      Frits 5:21 pm on 22 July 2021 Permalink | Reply

      The following Python program runs in 1 second for numbers 0-19 and 100ms for numbers 0-9 (with PyPy).

      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [# (red, black) balls: (AB, GH), (CD, IJ), (EF, KL))
         
         # (AB / (AB + GH) + CD / (CD + IJ) + EF / (EF + KL)) / 3 = 0.50
         #
         "2 * (AB * (CD + IJ) * (EF + KL) + \
               CD * (AB + GH) * (EF + KL) + \
               EF * (AB + GH) * (CD + IJ)) == 3 * (AB + GH) * (CD + IJ) * (EF + KL)",
        
         "AB > 0",
         "CD > 0",
         "EF > 0",
         # odd number of red balls
         "(AB + CD + EF) % 2",
         # force only one red if there are no blacks
         "KL > 0 or EF == 1",
         
         # (AB / (AB + GH - XY) + CD / (CD + IJ + XY) + EF / (EF + KL)) / 3 = 0.75  
         # move XY black balls form one urn to another
         "0 < XY <= GH",
         "4 * (AB * (CD + IJ + XY) * (EF + KL) + \
               CD * (AB + GH - XY) * (EF + KL) + \
               EF * (AB + GH - XY) * (CD + IJ + XY)) == \
               9 * (AB + GH - XY) * (CD + IJ + XY) * (EF + KL)",
         # no higher chance than 0.75    
         "not any(4 * (AB * (CD + IJ + x) * (EF + KL) + \
                  CD * (AB + GH - x) * (EF + KL) + \
                  EF * (AB + GH - x) * (CD + IJ + x)) > \
                  9 * (AB + GH - x) * (CD + IJ + x) * (EF + KL) \
                  for x in range(1, GH + 1))",      
        ],
      
        answer="AB + CD + EF + GH + IJ + KL, AB + CD + EF, \
        ((AB, GH), (CD, IJ), (EF, KL)), ((AB, GH - XY), (CD, IJ + XY), (EF, KL))",
        accumulate=min,
        verbose=0,
        # checks numbers 0-19
        d2i=dict([(k, "ACEGIKX") for k in range(2, 10)]),
        distinct="",   # allow variables with same values
      )
      
      
      # solve the puzzle
      r = p.run()
      
      # print answer
      ans = list(r.accumulate)
      print(f"smallest solution: {ans[1]} red balls and "
            f"{ans[0] - ans[1]} black balls")
      

      Like

  • Unknown's avatar

    Jim Randell 10:08 am on 20 July 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 811: When rules were rules … 

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

    No organisation can be efficient without clear-cut rules setting out exactly the rewards and the responsibilities of those who have the honour to be members of the team.

    I came across the other day a copy of the rules which, as the Managing Director of Our Factory, I had put on the Society’s Notice Board for all to see and understand. But this was many years ago when the pound was worth something, and when Rules were obeyed.

    There were five employees in the Factory then, and their names were Alf, Bert, Charlie, Duggie and Ernie. Their jobs, not necessarily respectively, were those of Door-Opener, Door-Shutter, Door-Knob-Polisher, Bottle-Washer and Welfare Officer. The notice which I put up read as follows:

    RULES:
    1. Charlie is to get 10% more than the worst paid of you all.
    2. Alf is to be paid more than Duggie.
    3. The Bottle-Washer is to get 5% more than 10% less than Bert.
    4. Duggie is to get either £1 more or £1 less than Ernie.
    5. The Door-Opener’s wages are to be an odd multiple of 10p.
    6. Ernie is to get 20% more than £1 less than the Door-Knob-Polisher.
    7. The Door-Shutter is to be the best paid of you all.
    8. Your wages are all to be different and each one is to be a multiple of 10p.
    9. No one is to get more than £20 or less than £10 per week.

    What were their weekly wages?

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

    [teaser811]

     
    • Jim Randell's avatar

      Jim Randell 10:09 am on 20 July 2021 Permalink | Reply

      Working in units of 10p means the wages are in the range 100 – 200.

      This Python program runs in 54ms.

      Run: [ @replit ]

      from enigma import irange, div, subsets, int2base, printf
      
      # possible values
      values = irange(100, 200)
      
      # find possible (x, f(x)) pairs
      def pairs(f):
        for x in values:
          y = f(x)
          if y is not None and y in values:
            yield (x, y)
      
      # consider BW/B pairs (BW = 1.05 * 0.9 * B)
      for (BW, B) in pairs(lambda x: div(200 * x, 21 * 9)):
      
        # consider DKP/E pairs (E = 1.2 * (DKP - 10))
        for (DKP, E) in pairs(lambda x: div(6 * (x - 10), 5)):
      
          # consider D values
          for D in (E - 10, E + 10):
            if D not in values: continue
      
            # consider A values (A > D)
            for A in values:
              if not(A > D): continue
              C = div(11 * min(B, D, E), 10)
              if C is None or C not in values: continue
              # the set of wages
              ws = set([A, B, C, D, E])
              if len(ws) != 5: continue
              # remaining jobs
              js = ws.difference([BW, DKP])
              if len(js) != 3: continue
              for (DS, DO, WO) in subsets(js, size=len, select="P"):
                # check DS, DO values
                if not(DO % 2 == 1 and DS == max([A, B, C, D, E])): continue
                # jobs: map: wage -> job
                jobs = dict(zip([BW, DKP, DS, DO, WO], "BW DKP DS DO WO".split()))
      
                # output solution
                fmt = lambda x: int2base(x * 10, group=2, sep='.')
                printf("A={A} ({j})", A=fmt(A), j=jobs[A])
                printf("B={B} ({j})", B=fmt(B), j=jobs[B])
                printf("C={C} ({j})", C=fmt(C), j=jobs[C])
                printf("D={D} ({j})", D=fmt(D), j=jobs[D])
                printf("E={E} ({j})", E=fmt(E), j=jobs[E])
                printf()
      

      Solution: The wages per week are: Alf = £18.90; Bert = £20.00; Charlie = £12.10; Duggie = £11.00; Ernie = £12.00.

      And their jobs:

      Alf = Bottle-Washer
      Bert = Door-Shutter
      Charlie = Door-Opener
      Duggie = Door-Knob-Polisher
      Ernie = Welfare Officer

      Like

    • Frits's avatar

      Frits 4:00 pm on 21 July 2021 Permalink | Reply

      Manual solution.

      # Consider amounts in 10p.
      
      # Ernie = 1.2 * (Door-Knob-Polisher - 10)                              (rule 6)
      # Ernie = 108 + 6 * YZ,     YZ  less than 16  
      # Ernie must be even so also Duggie must be even                       (rule 4)
      
      # Bottle-Washer = 1.05 * 0.9 * Bert, 189 * Bert = 200 * Bottle-Washer  (rule 3)
      # 189 and 200 are coprime so Bottle-Washer = 189, Bert = 200
      # Bottle-Washer is odd so not Bert, Duggie or Ernie
      # Charlie has to be a multiple of 11                                  (rule 11)
      # so --- Bottle-Washer must be Alf ---, Alf = 189
      # so --- Door-Shutter must be Bert ---                                 (rule 7)
      
      # Door-Opener's wages are to be an odd multiple of 10p                 (rule 5)
      # Alf and Bert have diffeent jobs, Duggie and Ernie are even
      # so --- Charlie is the Door-Opener ---
      
      # Ernie is to get 20% more than £1 less than the Door-Knob-Polisher    (rule 6)
      # three jobs already have been assigned
      # so --- Duggie is the Door-Knob-Polisher ---
      # so --- Ernie is the Welfare Officer ---
      # Ernie is paid more than Door-Knob-Polisher
      # so worst paid has to be Duggie 
      # so Ernie = Duggie + 10                                               (rule 4)
      # Door-Knob-Polisher = Ernie / 1.2 + 10 = 5 / 6 * (108 + 6 * YZ) + 10 =
      # 5 * YZ + 100 so YZ must be even (as Duggie is even)
      
      # Charlie = 1.1 * Duggie = 1.1 * (Ernie - 10)                    (rule 1 and 4)
      # so Ernie must be a multiple of 10
      # so YZ must be 2 or 12    (Ernie = 108 + 6 * YZ and YZ is even)
      # so (Charlie, Duggie, Ernie) must be resp. (121, 110, 120) or (187, 170, 180)
      # only in first case rule 6 is obeyed
      
      # so Alf = £18.90, Bert = £20, Charlie = £12.10, Duggie = £11 and Ernie = £12
      

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started