Tagged: by: Victor Bryant Toggle Comment Threads | Keyboard Shortcuts

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

    Teaser 3009: Head count 

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

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

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

    [teaser3009]

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

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

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

      The following Python 3 program runs in 320ms.

      Run: [ @repl.it ]

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

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

      The full description of the rounds is:

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

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


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

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

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

      Like

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

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

      Like

  • Jim Randell 12:59 pm on 21 May 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2864: Sequence of squares 

    From The Sunday Times, 13th August 2017 [link]

    I started with a rectangle of paper. With one straight cut I divided it into a square and a rectangle. I put the square to one side and started again with the remaining rectangle. With one straight cut I divided it into a square and a rectangle. I put the square (which was smaller than the previous one) to one side and started again with the remaining rectangle. I kept repeating this process (discarding a smaller square each time) until eventually the remaining rectangle was itself a square and it had sides of length one centimetre. So overall I had divided the original piece of paper into squares. The average area of the squares was a two-figure number of square centimetres.

    What were the dimensions of the original rectangle?

    [teaser2864]

     
    • Jim Randell 1:00 pm on 21 May 2020 Permalink | Reply

      If we start with the 1×1 cm square and replace the removed squares, we find the sequence of sizes of squares is:

      1, 1, 2, 3, 5, 8, 13, 21, …

      i.e. a Fibonacci sequence. [ @Wikipedia ]

      So we can start with the two 1×1 cm squares and build up the original rectangle square by square, until find one where the mean area of the squares is a two digit integer as required.

      This Python program runs in 82ms.

      Run: [ @repl.it ]

      from enigma import printf
      
      # initial a x b rectangle, n = number of squares, A = total Area
      (a, b, n, A) = (1, 1, 2, 2)
      while True:
        # calculate the mean area of the squares
        (m, r) = divmod(A, n)
        if m > 99: break
        # construct the rectangle
        (a, b) = (b, a + b)
        if r == 0 and m > 9:
          # output solution, when m is a 2 digit integer
          printf("[n={n}] rectangle = {a} x {b}, mean area = {m}")
        # move on to the next square
        A += b * b
        n += 1
      

      Solution: The original rectangle was 13 cm × 21 cm.

      So in total 6 cuts were made, producing 7 squares.

      The total area of the 7 squares is 273 sq cm, so the mean area is 39 sq cm.


      Manually:

      If:

      F(n) = nth Fibonacci number
      S(n) = sum of squares of F(n) = F(n) F(n + 1)
      M(n) = mean of squares of F(n) = F(n) F(n + 1) / n

      Then we can calculate:

       n  F(n)  S(n)  M(n)
       1    1     1    1
       2    1     2    1
       3    2     6    2
       4    3    15    3.75  
       5    5    40    8
       6    8   104   17.3...
       7   13   273   39
       8   21   714   89.25
       9   34  1870  207.7...
      10   55  ...
      

      And the answer is apparent.

      If we draw a quarter circle through each square we can make a Fibonacci Spiral:

      Like

  • Jim Randell 12:02 pm on 16 April 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Brainteaser 1808: Next choice 

    From The Sunday Times, 11th May 1997 [link]

    Much nonsense is written about the lottery. It is true that there are about 14 million different choices of six numbers from 1 to 49, but often surprise is expressed when the winning six include at least two consecutive numbers. In common with a lot of people, when I choose my numbers I make sure that they are well spread out, thus fitting in with the usual conception that it is unlikely that consecutive numbers will be drawn.

    This set me thinking about what proportion of the 14 million possible choices of 6 numbers actually contained no two consecutive numbers. The answer is surprising and neat. So, in percentages, to the nearest whole number, what proportion of the choices include no consecutive numbers?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1808]

     
    • Jim Randell 12:02 pm on 16 April 2020 Permalink | Reply

      We have already tackled a very similar puzzle with Enigma 1029 (also set by Victor Bryant under the pseudonym Susan Denham).

      The number of ways to choose 6 numbers from 49 is: C(49, 6) = 49! / (6! (49 – 6)!) = 13,983,816.

      The number of ways to choose 6 non-consecutive numbers from 49 is: C(49 – 5, 6) = 44! / (6! (44 – 6)!) = 7,059,052.

      This is approximately 50.48% of the total number of choices. So there are slightly more non-consecutive choices than consecutive choices.

      Solution: Approximately 50% of choices are non-consecutive.

      Like

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

    Teaser 3002: Short-cut 

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

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

    How long was the cut?

    [teaser3002]

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

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

      Brainteaser 1798 is a puzzle with a similar theme.

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

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

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

      From triangle Z:

      b² = 16² – 8² = 192

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

      And from triangle X:

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

      Solution: The length of the cut is 32 cm.

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

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

      Like

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

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

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

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

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

        Like

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

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

      Like

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

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

        Like

  • Jim Randell 5:22 pm on 21 February 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2996: Piece it together 

    From The Sunday Times, 23rd February 2020 [link]

    I have some jigsaw-type pieces each consisting of one, two, three or four 1cm-by-1cm squares joined together without overlapping. The pieces are black on one side and white on the other, and they are all different. I have used all my pieces to simultaneously make some different-sized white squares in jigsaw fashion, with each square using more than one piece. Even if you knew what all my pieces were like, you would not be able to determine the sizes of my squares.

    How many pieces do I have?

    [teaser2996]

     
    • Jim Randell 8:55 pm on 21 February 2020 Permalink | Reply

      (See also: Enigma 321).

      There are only a limited number of 1-sided, 1-, 2-, 3-, 4-onimoes, and as the pieces are all different this gives us an upper limit to the total area of the squares.

      It is fairly straightforward to narrow the required answer down to one of two values on the back of an envelope. But it is fun to make a constructive solution from scratch, so here goes…

      The following program looks for possible total areas that can be made into multiple different squares.

      We then select pieces with the appropriate area and attempt to construct the different sets of squares.

      This Python 3 program is adapted from my initial solution to Enigma 321. It’s not hugely fast, but it does find the solution in 50s.

      from itertools import product
      from copy import deepcopy
      from enigma import irange, inf, subsets, diff, first, printf
      
      # possible pieces in all possible orientations
      pieces = [
      
        # 1 square - 1x1 block ["O1"]
        (
          [(0, 0)],
        ),
      
        # 2 squares - 2x1 block ["I2"]
        (
          [(0, 0), (1, 0)],
          [(0, 0), (0, 1)],
        ),
      
        # 3 squares - linear, 3x1 block ["I3"]
        (
          [(0, 0), (1, 0), (2, 0)],
          [(0, 0), (0, 1), (0, 2)],
        ),
      
        # 3 squares - L shape ["V3"]
        (
          [(0, 0), (1, 0), (1, 1)],
          [(1, 0), (0, 1), (1, 1)],
          [(0, 0), (1, 0), (0, 1)],
          [(0, 0), (0, 1), (1, 1)],
        ),
      
        # 4 squares - 4x1 block, ["I4"]
        (
          [(0, 0), (1, 0), (2, 0), (3, 0)],
          [(0, 0), (0, 1), (0, 2), (0, 3)],
        ),
      
        # 4 squares - square, 2x2 block ["O4"]
        (
          [(0, 0), (1, 0), (0, 1), (1, 1)],
        ),
      
        # 4 squares - T shape ["T4"]
        (
          [(1, 0), (0, 1), (1, 1), (2, 1)],
          [(0, 0), (0, 1), (1, 1), (0, 2)],
          [(0, 0), (1, 0), (2, 0), (1, 1)],
          [(1, 0), (0, 1), (1, 1), (1, 2)],
        ),
      
        # and now the chiral ones
      
        # 4 squares - Z shape ["Z4"]
        (
          [(0, 1), (1, 1), (1, 0), (2, 0)],
          [(0, 0), (0, 1), (1, 1), (1, 2)],
        ),
      
        # 4 squares - S shape ["Z4'", "S4"]
        (
          [(0, 0), (1, 0), (1, 1), (2, 1)],
          [(1, 0), (1, 1), (0, 1), (0, 2)],
        ),
      
        # 4 squares - L shape ["L4"]
        (
          [(0, 0), (0, 1), (0, 2), (1, 2)],
          [(0, 0), (1, 0), (2, 0), (2, 1)],
          [(1, 0), (1, 1), (1, 2), (0, 2)],
          [(0, 0), (0, 1), (1, 1), (2, 1)],
        ),
      
        # 4 squares - L shape ["L4'", "R4"]
        (
          [(0, 0), (1, 0), (1, 1), (2, 1)],
          [(0, 1), (1, 1), (2, 1), (2, 0)],
          [(0, 0), (0, 1), (0, 2), (1, 2)],
          [(0, 0), (0, 1), (1, 0), (2, 0)],
        ),
      ]
      
      # try to place piece <p> at <x>, <y> in grid <grid> of dimensions <a>, <b>
      # using label <n>
      def place(p, y, x, n, grid, a, b):
        g = deepcopy(grid)
        for (dy, dx) in p:
          (py, px) = (y + dy, x + dx)
          try:
            q = g[py][px]
          except IndexError:
            return None
          if q is not None:
            return None
          g[py][px] = n
        return g
      
      # try to fit pieces <ps> into grid <grid> of dimensions <a>, <b>
      def fit(ps, n, grid, a, b):
        if not ps:
          yield grid
        else:
          # choose a piece
          for p in ps[0]:
            # try to place the piece at x, y
            for (y, x) in product(irange(0, a - 1), irange(0, b - 1)):
              g = place(p, y, x, n, grid, a, b)
              if g is not None:
                yield from fit(ps[1:], n + 1, g, a, b)
      
      # select at least <n> pieces from <ps> with a total area of <k>
      def select(ps, k, n):
        for i in irange(n, len(ps)):
          f = 0
          for s in subsets(ps, size=i):
            t = sum(len(p[0]) for p in s) 
            if t == k:
              yield s
            if not(t > k):
              f += 1
          if f == 0: break
      
      # fit the pieces <ps> into squares with sides <squares>
      def fit_squares(ps, squares, ss=[]):
        # are we done?
        if not ps:
          yield ss
        else:
          # try to fill the next square
          s = squares[0]
          # choose pieces with the right area
          for fs in select(ps, s * s, 2):
            # create an s x s empty grid and assemble the pieces in it
            grid = list([None] * s for _ in irange(1, s))
            for g in fit(fs, 1, grid, s, s):
              # fit the remaining squares
              yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])
      
      # find an example fit of the pieces <ps> into each of the list of squares <ss>
      def solve(ps, ss):
        fs = list()
        for s in ss:
          f = first(fit_squares(ps, s))
          if not f: return
          fs.extend(f)
        return fs
      
      
      # express n as a sum of increasing squares (minimum: m)
      def sum_of_squares(n, m=1, s=[]):
        if n == 0:
          if len(s) > 1:
            yield s
        else:
          for i in irange(m, inf):
            i2 = i * i
            if i2 > n: break
            yield from sum_of_squares(n - i2, i + 1, s + [i])
      
      # consider increasing total area of the squares
      T = sum(len(p[0]) for p in pieces)
      for n in irange(4 + 9, T):
        sqs = list(sum_of_squares(n, 2))
        if len(sqs) < 2: continue
        printf("total area = {n} -> squares = {sqs}")
      
        # choose some of the squares
        for ss in subsets(sqs, min_size=2):
      
          # make a set of polyominoes with the appropriate total area
          for ps in select(pieces, n, 2 * max(len(s) for s in ss)):
      
            # try and fit them into the squares
            fs = solve(ps, ss)
            if fs is None: continue
      
            # output solution (number of pieces), and constructed squares
            printf("  {m} pieces", m=len(ps))
            for (s, f) in zip(ss, fs):
              printf("  {s} -> {f}")
            printf()
      

      There is only a single candidate area that can be expressed as the sum of different, non-unit squares in multiple ways.

      There are two sets of pieces that can be assembled into the required squares, but they both have the same number of pieces (one set is a mirror image of the other), and so this gives the answer.

      Solution: There are 9 jigsaw pieces.

      The 9 pieces have a total area of 29, and can be assembled into a set of (2×2, 3×3, 4×4) squares, or a set of (2×2, 5×5) squares.

      Here is a solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4.

      Note that we can’t turn the pieces over, so L4 and its mirror image (L4′) are different pieces (you cannot rotate one of them to give the same shape as the other), as are Z4 and its mirror image (Z4′).

      And here is another solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4′.

      The second set uses Z4′ instead of Z4. These pieces are mirror images of each other, so any solution for the first set also gives a solution for the second set, by reflecting it.

      There are no further solutions, even if we were are allowed to have squares that are the same size.

      It occurred to me that the squares are the same sizes as the collection of Rubik’s cubes I have available to me, so here are the diagrams made with cubes:

      (I’ve only got one 2×2×2 cube, so it has to be shared between the sets of squares).

      Like

      • Jim Randell 10:55 am on 23 February 2020 Permalink | Reply

        I encapsulated the code that deals with polyominoes into a separate file [[ polyominoes.py ]] that can be used to solve this puzzle (and Enigma 321), and I switched to using Knuth’s Algorithm X, rather than the simplistic [[ fit() ]].

        So the following program runs in a more reasonable 1.1s.

        Run: [ @repl.it ]

        import polyominoes
        from enigma import irange, inf, subsets, diff, first, printf
        
        # select at least <n> pieces from <ps> with a total area of <k>
        def select(ps, k, n):
          for i in irange(n, len(ps)):
            f = 0
            for s in subsets(ps, size=i):
              t = sum(len(p[0]) for p in s) 
              if t == k:
                yield s
              if not(t > k):
                f += 1
            if f == 0: break
        
        # fit the pieces <ps> into squares with sides <squares>
        def fit_squares(ps, squares, ss=[]):
          # are we done?
          if not ps:
            yield ss
          else:
            # try to fill the next square
            s = squares[0]
            # choose pieces with the right area
            for fs in select(ps, s * s, 2):
              # create an s x s empty grid and assemble the pieces in it
              for g in polyominoes.fit(fs, s, s):
                # fit the remaining squares
                yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])
        
        # find an example fit of the pieces <ps> into each of the list of squares <ss>
        def solve(ps, ss):
          fs = list()
          for s in ss:
            f = first(fit_squares(ps, s))
            if not f: return
            fs.extend(f)
          return fs
        
        
        # express n as a sum of increasing squares (minimum: m)
        def sum_of_squares(n, m=1, s=[]):
          if n == 0:
            if len(s) > 1:
              yield s
          else:
            for i in irange(m, inf):
              i2 = i * i
              if i2 > n: break
              yield from sum_of_squares(n - i2, i + 1, s + [i])
        
        # available pieces, and total area
        pieces = polyominoes.shapes("O1 I2 I3 V3 O4 I4 T4 Z4 Z4' L4 L4'", "ONE_SIDED")
        
        # consider increasing total area of the squares
        T = sum(len(p[0]) for p in pieces)
        for n in irange(4 + 9, T):
          sqs = list(sum_of_squares(n, 2))
          if len(sqs) < 2: continue
          printf("total area = {n} -> squares = {sqs}")
        
          # choose some of the squares
          for ss in subsets(sqs, min_size=2):
        
            # make a set of polyominoes with the appropriate total area
            for ps in select(pieces, n, 2 * max(len(s) for s in ss)):
        
              # try and fit them into the squares
              fs = solve(ps, ss)
              if fs is None: continue
        
              # output solution (number of pieces), and constructed squares
              printf("  {m} pieces", m=len(ps))
              for (s, f) in zip(ss, fs):
                printf("  {s} -> {f}")
              printf()
        

        Like

    • Robert Brown 12:57 pm on 25 February 2020 Permalink | Reply

      This teaser reminds me of enigma 1491 (not on your site?) from 2008. Box of tiles 1×3, 2×4, 3×5 etc. Takes tiles out in order, one at a time, and tries to make a rectangle. Required to find a) smallest possible rectangle & b) next largest. Everyone could all do a) by hand, but b) needed a fairly complex program. Ongoing discussions gradually simplified the program algorithm, and ultimately we got it down to a series of steps that could be followed manually – could be done in about 10 minutes. It’s all on the newenigma site, but you need a user name & password to log in!

      Like

    • Robert Brown 1:03 pm on 25 February 2020 Permalink | Reply

      Sorry, I misquoted that slightly – should say ‘required to find how many tiles for smallest rectangle’ (which of course has no gaps or overlaps)

      Like

      • Jim Randell 2:20 pm on 25 February 2020 Permalink | Reply

        I remember Enigma 1491. It was a fun puzzle. My notes for it are here [ @enigmaticcode ].

        When it was originally published in 2008 I wrote a Perl program to solve it, but that took 50 minutes to run. So while it was running I coded up the same algorithm in C, and that ran in 11 seconds.

        When I came to add the puzzle to the Enigmatic Code site in 2012 I wrote a Python program using a slightly different approach, and found that it ran in 9.2s. Now the same program runs in just 2.5s (probably due to improvements in the PyPy environment — I’m still using the same laptop I was using in 2012).

        Like

  • Jim Randell 8:49 am on 26 December 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2882: Snow White 

    From The Sunday Times, 17th December 2017 [link]

    Snow White placed three balls in a hat (“Oh yes she did!”): written on each ball was a different non-zero digit. She asked one of her little helpers to draw out the three in some order and to use them in that order to make a three-figure number. She knew that this number would be divisible by three but not by seven. She asked the helpers to share out that number of sweets equally amongst the seven of them as far as possible and to give her the remainder. She knew that on seeing the remaining sweets she would be able to work out the order in which the three digits had been drawn out.

    What (in increasing order) were the three digits?

    [teaser2882]

     
    • Jim Randell 8:51 am on 26 December 2019 Permalink | Reply

      This Python program runs in 73ms.

      Run: [ @repl.it ]

      from collections import defaultdict
      from enigma import irange, subsets, nconcat, printf
      
      # available digits
      digits = irange(1, 9)
      
      # choose 3 digits
      for ds in subsets(digits, size=3, select="C"):
        # any permutation must be divisible by 3
        if sum(ds) % 3 != 0: continue
        # compute the residues of the permutations mod 7
        r = defaultdict(list)
        for s in subsets(ds, size=len, select="P"):
          n = nconcat(s)
          r[n % 7].append(n)
        # there can be no permutations exactly divisible by 7
        if r[0]: continue
        # there can be no non-zero residue that is ambiguous
        if any(len(v) > 1 for (k, v) in r.items() if k != 0): continue
        printf("digits = {ds} [{r}]", r=dict(r))
      

      Solution: The three digits were: 4, 8, 9.

      They can be assembled into the following 3-digit numbers (and residues modulo 7):

      489 (6)
      498 (1)
      849 (2)
      894 (5)
      948 (3)
      984 (4)

      Each permutation of the digits is uniquely identified by the residue.

      Like

    • GeoffR 4:31 pm on 26 December 2019 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Three single digits
      var 1..9:A; var 1..9:B; var 1..9:C;
      constraint all_different([A, B, C]);
      
      % Residues modulus 7 
      var 1..6:a; var 1..6:b; var 1..6:c;
      var 1..6:d; var 1..6:e; var 1..6:f;
      constraint all_different([a, b, c, d, e, f]);
      
      % Three digit numbers 
      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;
      
      % All three digit numbers divisible by three
      constraint ABC mod 3 == 0 /\ ACB mod 3 == 0 
      /\ BAC mod 3 == 0 /\ BCA mod 3 == 0 
      /\ CAB mod 3 == 0 /\ CBA mod 3 == 0;
      
      % All three digit numbers were not divisible by seven
      constraint ABC mod 7 == a /\ ACB mod 7 == b
      /\ BAC mod 7 == c /\ BCA mod 7 == d
      /\ CAB mod 7 == e /\ CBA mod 7 == f; 
      
      constraint increasing([A, B, C]);
      
      solve satisfy;
      
      output[ "The three digits were " ++ show(A) ++ ", " 
      ++ show(B) ++ ", " ++ show(C)];
      
      % The three digits were 4, 8, 9
      % % time elapsed: 0.03 s
      % ----------
      % ==========
      
      
      
      

      Like

  • Jim Randell 4:48 pm on 29 November 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2984: Shuffle the cards 

    From The Sunday Times, 1st December 2019 [link]

    In the classroom I have a box containing ten cards each with a different digit on it. I asked a child to choose three cards and to pin them up to make a multiplication sum of a one-figure number times a two-figure number. Then I asked the class to do the calculation.

    During the exercise the cards fell on the floor and a child pinned them up again, but in a different order. Luckily the new multiplication sum gave the same answer as the first and I was able to display the answer using three of the remaining cards from my box.

    What was the displayed answer?

    [teaser2984]

     
    • Jim Randell 5:05 pm on 29 November 2019 Permalink | Reply

      If the original sum is A × BC, then none of the digits in the second sum can be in their original positions, so the second sum is one of: B × CA or C × AB.

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

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      # initial sum
      "A * BC = DEF"
      
      # but it also works in a different order
      "DEF in (B * CA, C * AB)"
      
      # required answer
      --answer="DEF"
      

      Solution: The result of the two multiplications is 130.

      The two sums are: 2×65 and 5×26, but we don’t know which was the original one.

      Like

      • Jim Randell 9:42 pm on 2 December 2019 Permalink | Reply

        If we consider the two possible pairs of sums:

        A × BC = DEF ∧ B × CA = DEF
        A × BC = DEF ∧ C × AB = DEF

        Rewriting the first with A = X, B = Y, C = Z and the second with A = Y, B = Z, C = X, we get:

        X × YZ = DEF ∧ Y × ZX = DEF
        Y × ZX = DEF ∧ X × YZ = DEF

        Which are the same, so we can solve the puzzle with an even simpler one liner:

        % python -m enigma SubstitutedExpression "X * YZ = DEF" "Y * ZX = DEF" --answer="DEF"
        (X * YZ = DEF) (Y * ZX = DEF) (DEF)
        (5 * 26 = 130) (2 * 65 = 130) (130) / D=1 E=3 F=0 X=5 Y=2 Z=6
        DEF = 130 [1 solution]
        

        Like

    • GeoffR 7:41 pm on 4 December 2019 Permalink | Reply

      
      from time import perf_counter_ns
      start = perf_counter_ns()
      
      from itertools import permutations
      
      for p in permutations((1,2,3,4,5,6,7,8,9),3):
          a, b, c = p    # choose 3 positive digits
      
          # Original displayed answer
          s = a * (10 * b + c)
          
          # 1st alternative position for digits to give same product
          if s == b * (10 * c + a):
              if len (set((a, b, c, s//100, s//10%10, s%10))) == 6:
                print(f"1.Original displayed answer = {s} ({a}*{10*b+c})")
                print(f"2nd displayed answer = {s} ({b}*{10*c+a})")
                print(f"1st digit={a}, 2nd digit={b}, 3rd digit={c}")
                print(f"{(perf_counter_ns() - start) / 1e6:.3f} milliseconds")
      
          # 2nd alternative positions for digits to give same product
          if s == c * (10 * a + b):
              if len (set((a, b, c, s//100, s//10%10, s%10))) == 6:
                print(f"2.Original displayed answer = {s} ({a}*{10*b+c})")
                print(f"2nd displayed answer = {s} ({c}*{10*a+b})")
                print(f"1st digit={a}, 2nd digit={b}, 3rd digit={c}")
                print(f"{(perf_counter_ns() - start) / 1e6:.3f} milliseconds")
      
      # 2.Original displayed answer = 130 (2*65)
      # 2nd displayed answer = 130 (5*26)
      # 1st digit=2, 2nd digit=6, 3rd digit=5
      # 49.703 milliseconds
      #
      # 1.Original displayed answer = 130 (5*26)
      # 2nd displayed answer = 130 (2*65)
      # 1st digit=5, 2nd digit=2, 3rd digit=6
      # 88.180 milliseconds
      
      
      

      Like

    • GeoffR 4:54 pm on 5 December 2019 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9: A; var 1..9: B; var 1..9: C; var 1..9: D;
      var 0..9: E; var 0..9: F;
      
      constraint all_different([A, B, C, D, E, F]);
      
      var 10..99: BC = 10*B + C;
      var 10..99: CA = 10*C + A;
      var 10..99: AB = 10*A + B;
      var 100..999: DEF = 100*D + 10*E + F;
      
      % Original sum
      constraint A * BC == DEF;
      
      % Sums with digits in a different order
      constraint B * CA == DEF \/ C * AB == DEF;
      
      solve satisfy;
      
      output ["Displayed Sum is " ++ show(A) ++ " X " ++ show(BC)
      ++ " = " ++ show(DEF) ];
      
      % Displayed Sum is 2 X 65 = 130
      % Displayed Sum is 5 X 26 = 130
      % ==========
      
      
      
      

      Like

  • Jim Randell 9:06 am on 17 November 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Brainteaser 1747: Lottery charges 

    From The Sunday Times, 10th March 1996 [link]

    Chargealot are having a new set of lottery balls made. They are going to be painted with numbers from 1 (not 01) to 49. The painter decides that this is one chance to make a fortune from the lottery and so he charges accordingly. He divides the digits into two types and charges a certain whole number of pounds for painting each digit of one type (each time it occurs) and a different whole number of pounds for all the other digits (each time they occur). Both charges are more than £50 but less than £100.

    To make the cost sound reasonable, instead of quoting a price for the whole set he quoted the average price per ball. Of course some balls cost less than average, and some balls cost more, but just one ball’s price was equal to the average.

    What were his two charges per digit?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1747]

     
    • Jim Randell 9:07 am on 17 November 2019 Permalink | Reply

      We can divide the digits from 0-9 into two sets, “type A” and “type B” with associated costs a and b.

      There are 9 single digit numbers and 40 2-digit numbers, so the 49 numbers use 89 digits in total.

      If, in total, there are nA type A digits and nB type B digits then we have:

      nA + nB = 89
      T = a × nA + b × nB = 49 × m

      where T is the total cost and m is the average cost per ball, and only one of the balls can cost the average amount.

      This Python program runs in 158ms.

      Run: [ @repl.it ]

      from collections import defaultdict
      from enigma import subsets, diff, irange, nsplit, div, printf
      
      # place 0 in set A and choose some other digits to go in set B
      for B in subsets(irange(1, 9), min_size=1):
        A = diff(irange(0, 9), B)
      
        # group the numbers by (A, B) usage
        d = defaultdict(list)
        nA = 0
        for n in irange(1, 49):
          # count the A and B digits
          k = [0, 0]
          for x in nsplit(n):
            k[x in B] += 1
          d[tuple(k)].append(n)
          nA += k[0]
        nB = 89 - nA
      
        # find a number in a class by itself
        for ((i, j), vs) in d.items():
          if len(vs) != 1: continue
      
          # find costs for the digits in A and B
          for a in irange(51, 99):
            b = div(a * (49 * i - nA), nB - 49 * j)
            if b is None or b < 51 or b > 99: continue
      
            # check none of the other groups cost the same as the mean
            m = a * i + b * j
            if any(a * x + b * y == m for (x, y) in d.keys() if not(x == i and y == j)): continue
      
            # output solution
            printf("cost = ({a}, {b}), digits = ({A}, {B}); mean = {m}, number = {vs[0]}")
      

      Solution: Each digit costs £ 74 or £ 83.

      The ball that costs the mean amount is one of the repeated digit balls, i.e. 11, 22, 33, 44. It costs £ 148 (i.e. 2× £ 74).

      The digit used twice on the mean ball is the only digit that costs £ 74, all the other digits cost £ 83.

      The total cost for all the balls is therefore £ 7252.

      Like

  • Jim Randell 1:45 pm on 10 November 2019 Permalink | Reply
    Tags: , by: Victor Bryant   

    Brainteaser 1742: Not-so-safe deposit 

    From The Sunday Times, 4th February 1996 [link]

    The safe deposit boxes at our bank are arranged in a huge pyramid, the top of which is illustrated:

    When the were first opened the top box had a quantity of gold coins placed in it and the rest were empty. One night a burglar broke into that box, emptied it, and (cleverly, he thought) instead of running off with the coins, he found the two empty boxes in the row below and put some of his haul in one and the rest in the other.

    Word spread through the underworld about the bank’s lax security, and a sequence of burglaries took place. Each burglar broke into one box containing some coins, emptied it, found two empty boxes in the row below, placed some of his haul in one of these boxes and the rest in the other.

    Ages later the manager of the bank opened up the top box and was horrified to find it empty. So he tried the boxes in the next row and found them empty too. He carried on like this until he found some coins in one particular row. In fact, no matter how many burglaries had taken place, there could not have been more empty rows at the top of the pyramid. And indeed if any fewer burglaries had taken place all those rows could not have been empty.

    (a) How many empty rows at the top were there?
    (b) How many burglaries were there?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1742]

     
    • Jim Randell 1:45 pm on 10 November 2019 Permalink | Reply

      We can try to empty the uppermost rows as quickly as possible.

      Initially, in the top row there is 1 box, initially containing the complete amount:

      [0] 1/1 = 1

      The first burglar breaks in, and splits the amount between the two boxes in the second row. So each of the 2 boxes contains 1/2 of the complete amount:

      [1] 0/1 + 2/2 = 1

      The second burglar breaks in and splits the amount from one of the boxes in the second row between 2 (of the 3) boxes in the third row:

      [2] 0/1 + 1/2 + 2/4 = 1

      The third burglar can’t burgle the remaining box in the second row, as there aren’t enough empty boxes in the third row to hide the spoils. So he splits the amount from one of the boxes in the third row into 2 (of the 4) boxes in the fourth row:

      [3] 0/1 + 1/2 + 1/4 + 2/8 = 1

      The fourth burglar can burgle the box in the second row, as there are now 2 empty boxes in the third row:

      [4] 0/1 + 0/2 + 3/4 + 2/8 = 1

      And so the process continues:

      [5] 0/1 + 0/2 + 2/4 + 4/8 = 1
      [6] 0/1 + 0/2 + 2/4 + 3/8 + 2/16 = 1
      [7] 0/1 + 0/2 + 2/4 + 2/8 + 4/16 = 1
      [8] 0/1 + 0/2 + 1/4 + 4/8 + 4/16 = 1
      [9] 0/1 + 0/2 + 1/4 + 4/8 + 3/16 + 2/32 = 1
      [10] 0/1 + 0/2 + 1/4 + 3/8 + 5/16 + 2/32 = 1
      [11] 0/1 + 0/2 + 1/4 + 3/8 + 4/16 + 4/32 = 1
      [12] 0/1 + 0/2 + 1/4 + 3/8 + 3/16 + 6/32 = 1
      [13] 0/1 + 0/2 + 1/4 + 2/8 + 5/16 + 6/32 = 1
      [14] 0/1 + 0/2 + 0/4 + 4/8 + 5/16 + 6/32 = 1

      So we’ve managed to empty the first 3 rows (in 14 burglaries).

      Can we empty the fourth row?

      What if every row below it was full? We would have:

      S = 5/16 + 6/32 + 7/64 + 8/128 + …
      S = (1/16 + 4/16) + (1/32 + 5/32) + (1/64 + 6/64) + (1/128 + 7/128) + …
      S = (1/16 + 1/32 + 1/64 + 1/128 + …) + (4/16) + (5/32 + 6/64 + 7/128 + …)
      S = (1/8)(1/2 + 1/4 + 1/8 + 1/16 + …) + (1/4) + S/2
      S = (1/8) + (1/4) + S/2
      S/2 = 3/8
      S = 3/4

      We can check this by calculating the sum the first few terms:

      >>> sum(fdiv(n + 1, 2**n) for n in irange(4, 100))
      0.75
      

      So there is not enough room to hide the entire amount using just rows 5 onwards, hence we can never empty row 4.

      Solution: (a) The first 3 rows were empty.

      The number of burglaries required to achieve any situation is one less than the number of occupied boxes.

      And as the fractions of the original collection decrease as we move down the rows we want to occupy the minimal number of boxes possible. If the first 3 rows are empty this minimal number is 4 on the 4th row, 5 on the 5th row, 6 on the 6th row (4/8 + 5/16 + 6/32 = 1), which required 4 + 5 + 6 – 1 = 14 burglaries.

      Solution: (b) There were 14 burglaries.

      Like

      • John Crabtree 9:50 pm on 13 November 2019 Permalink | Reply

        While experimenting with this, I found that one box in row 2 could be replaced by:
        i) a pyramid with one box full in row 4, two in row 5, three in row 6 etc
        or ii) one box full in row 4, and three in all lower rows
        Add the two together, and the grid would be full with two boxes full in row 4, and all all boxes in lower rows. It does not matter if this pattern can actually be reached. Row 4 cannot be empty. it is quite easy to check if the first three rows can be emptied.

        Like

  • Jim Randell 9:15 pm on 30 October 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2817: Our secret 

    From The Sunday Times, 18th September 2016 [link]

    Eight friends joined a very secret society and each was given a different membership number between 70 and 100. The friends are Bec, Cal, Doc, Ian, Jon, Luv, Rev and one other – and I am not willing to divulge his common three-letter name. But I can tell you that his membership number is 84. Also, Bec’s membership number is the highest of the eight. The friends noticed that, for any pair of them, their names had at least one letter in common if and only if their membership numbers had a common prime factor.

    (a) What was Ian’s membership number?
    (b) What was the name of the eighth friend?

    [teaser2817]

     
    • Jim Randell 9:17 pm on 30 October 2019 Permalink | Reply

      The following recursive Python 3 program finds two sets of three letters that may be combined to form a “common three-letter” name. But only one of them really works.

      It runs in 433ms.

      Run: [ @repl.it ]

      from enigma import irange, factor, join, update, subsets, cached, printf
      
      factor = cached(factor)
      
      # membership numbers are allocated such that membership numbers share
      # factors exactly when the corresponding members names share letters
      
      # number for the mystery man
      xxx = 84
      
      # check if <name>, <number> can be added to members in dict <d>
      def check(name, number, d):
        ls = set(name)
        fs = set(factor(number))
        return all(bool(ls.intersection(k)) == bool(fs.intersection(factor(v))) for (k, v) in d.items())
      
      # allocate numbers from <numbers> to the names in <names>
      # (the assignment is stored in dictionary <d>)
      def allocate(names, numbers, d):
        # are we done?
        if not names:
          yield d
        else:
          # consider the next name
          for (i, n) in enumerate(numbers):
            # check names share letters only when they share factors
            if check(names[0], n, d):
              yield from allocate(names[1:], numbers[:i] + numbers[i + 1:], update(d, [(names[0], n)]))
      
      # choose a number for Bec (the highest number)
      for b in irange(85, 100):
      
        # remaining allowable numbers
        ns = list(irange(70, b - 1))
        ns.remove(xxx)
      
        # allocate numbers for the remaining names
        for d in allocate(['cal', 'doc', 'ian', 'jon', 'luv', 'rev'], ns, { 'bec': b }):
      
          # output the allocations
          printf("{d}", d=join((join((k, '=', v)) for (k, v) in sorted(d.items(), key=lambda x: x[::-1])), sep=' '))
      
          # find (up to) three letters that form xxx's name
          for ls in subsets(set(join(d.keys())), min_size=1, max_size=3):
            if check(ls, xxx, d):
              ls = join(sorted(ls)).ljust(3, '?')
              names = set(join(s) for s in subsets(ls, size=len, select="mP"))
              printf("letters = {ls} -> names = {names}", names=join(sorted(names), sep=', '))
      

      Solution: (a) Ian’s membership number is 76. (b) The eighth friend is named Vic.

      The solutions found by the program are “civ” and “acv”. The only rearrangement that gives a common three-letter name is “Vic” (which as the setter is Victor Bryant, is probably what is wanted as the answer). Although one could argue that “Cav” or “Vac” are no worse than the names used for other members.

      So the membership numbers are:

      Doc = 75
      Ian = 76
      Rev = 77
      Cal = 78
      Vic = 84
      Luv = 91
      Jon = 95
      Bec = 99

      Shared letters and factors are (each pair only shown once):

      Doc with: Cal (C, 3); Vic (C, 3); Jon (O, 5); Bec (C, 3)
      Ian with: Cal (A, 2); Vic (I, 4); Jon (N, 19)
      Rev with: Vic (V, 7); Luv (V, 7); Bec (E, 11)
      Cal with: Vic (C, 6); Luv (L, 13); Bec (C, 3)
      Vic with: Luv (V, 7); Bec (C, 3)

      However if we were to use “Vac” (or “Cav”) instead of Vic, we would have the following pairings for Vac:

      Vac with: Doc (C, 3); Ian (A, 4); Rev (V, 7); Cal (AC, 6); Luv (V, 7); Bec (C, 3)

      Vac and Cal give us the only pairing that shares more than 1 letter, so if this had been disallowed we would know for certain that the three letters that make up the name of the eighth friend were “civ”.


      This posting completes my notes for all Sunday Times Teaser puzzles that I have previously posted to repl.it [ @repl.it ].

      I do however have more code for puzzles that I didn’t post, so there may well be more to come.

      Like

  • Jim Randell 9:41 am on 16 October 2019 Permalink | Reply
    Tags: by: Victor Bryant,   

    Teaser 2825: Twin sets 

    From The Sunday Times, 13th November 2016 [link]

    The twins Wunce and Repete each made a list of positive perfect squares. In Wunce’s list each of the digits 0 to 9 was used exactly once, whereas in Repete’s list each of the digits was used at least once.

    Wunce commented that the sum of his squares equalled their year of birth, and Repete responded by saying that the sum of his squares was less than the square of their age.

    What is the sum of Wunce’s squares, and what is the sum of Repete’s?

    As stated there are multiple potential solutions to the puzzle. In the comments I give some additional conditions that allow a unique solution to be found (which is the same as the published solution).

    [teaser2825]

     
    • Jim Randell 9:42 am on 16 October 2019 Permalink | Reply

      As originally stated there are multiple solutions to this puzzle.

      I made the following additional suppositions in order to allow a unique solution to be arrived at.

      1. the puzzle is set on/after the twins birthday in 2018;
      2. the lists do not contain repeats;
      3. the squares are greater than 1.

      The following Python program then finds the unique solution in 281ms.

      Run: [ @repl.it ]

      from enigma import irange, isqrt, filter2, is_duplicate, arg, printf
      
      # Y = year the puzzle is set (which apparently should be 2018)
      Y = arg(2018, 0, int)
      # m = minimum allowable square (the root of the square is used)
      m = arg(2, 1, int)
      printf("[Y = {Y}, m={m}]")
      
      # squares (as strings, without repeated digits)
      (_, squares) = filter2(is_duplicate, (str(i * i) for i in irange(m, isqrt(Y))))
      
      # for Wunce find a pan-digital subset (without repeated digits)
      # ss = squares to consider
      # s = squares used so far
      # ds = digits used so far
      def solve1(ss, s=[], ds=set()):
        # are we done?
        if len(ds) == 10:
          yield list(int(x) for x in s)
        else:
          # chose the next element
          for (i, x) in enumerate(ss):
            if ds.intersection(x): continue
            yield from solve1(ss[i + 1:], s + [x], ds.union(x))
      
      # for Repete find a pan-digital set of squares (allowing repeated digits)
      # below a given total
      # n = largest square to consider
      # t = sum of squares must be less than this
      # s = squares used so far
      # ds = digits used so far
      def solve2(n, t, s=[], ds=set()):
        # are we done?
        if len(ds) == 10:
          yield s
        # choose the next element
        for i in irange(n, m, step=-1):
          i2 = i * i
          if i2 < t:
            yield from solve2(i - 1, t - i2, s + [i2], ds.union(str(i2)))
      
      # find sequences for Wunce
      for s1 in solve1(squares):
        t1 = sum(s1)
        printf("Wunce: total = {t1}, squares = {s1}")
      
        # calculate the age
        age = Y - t1
        age2 = age * age
        printf("age = {age}, age^2 = {age2}")
      
        # find sequences for Repete
        for s2 in solve2(age - 1, age2):
          t2 = sum(s2)
          printf("Repete: total = {t2}, squares = {s2}")
      

      Solution: The sum of Wunce’s squares is 1989. The sum of Repete’s squares is 831.

      Wunce’s list of squares is (324, 576, 1089) = (18², 24², 33²).

      The sum of which is 1989. So in 2018 the twins would be 29.

      Repete’s list of squares is (4, 9, 25, 36, 81, 100, 576) = (2², 3², 5², 6², 9², 10², 24²).

      The sum of which is 831. Which is less than 841 = 29².

      If we allow 1 in the list of squares then the sum of Repete’s list could be 832. And there are further possibilities if squares in the list are allowed to be repeated.

      Like

  • Jim Randell 9:52 am on 4 October 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2840: Signs of the times 

    From The Sunday Times, 26th February 2017 [link]

    I was taking a gentle morning drive along the straight road to Secombe that passes through Firsk. Before reaching Firsk I passed three signposts, each giving the distances to Firsk and to Secombe (to the nearest mile). All six distances displayed were different and, amazingly, all were perfect squares [less than 100].

    What were the two distances given on the first signpost (furthest from Firsk)?

    I have added the “less than 100” condition to reduce ambiguity in the puzzle.

    [teaser2840]

     
    • Jim Randell 9:54 am on 4 October 2019 Permalink | Reply

      When this puzzle was first published there was some confusion over the correct interpretation. I have added the condition to require the squares to be less than 100 to eliminate multiple solutions.

      The distances on the signposts are rounded to the nearest mile. This Python program uses intervals to find viable solutions. It runs in 47ms.

      Run: [ @repl.it ]

      from enigma import irange, isqrt, subsets, arg, printf
      
      # limit to numbers on signs
      M = arg(100, 0, int)
      printf("[M={M}]")
      
      # possible squares that can appear on the signs
      squares = list(i * i for i in irange(1, isqrt(M - 1)))
      
      # possible distances for three signs (in order)
      signs = subsets(squares, size=3)
      
      # combine lower/upper bounds into an interval
      def interval(v, *vs):
        (l, u) = v
        for (l1, u1) in vs:
          (l, u) = (max(l, l1), min(u, u1))
        return (l, u)
      
      # choose the distances to F and S on the signs
      for ((f1, f2, f3), (s1, s2, s3)) in subsets(signs, size=2):
      
        # check the distances are all different
        if len(set((f1, f2, f3, s1, s2, s3))) < 6: continue
      
        # calculate the position of S
        (sl, su) = interval(
          (s1 - f1 - 1, s1 - f1 + 1),
          (s2 - f2 - 1, s2 - f2 + 1),
          (s3 - f3 - 1, s3 - f3 + 1),
        )
      
        # is it feasible?
        if 0 < sl < su:
          printf("signs = ({f1} {s1}) ({f2} {s2}) ({f3} {s3}), F -> S = ({sl}, {su})")
      

      Solution: The distances on the first signpost encountered were 49 miles (to Firsk) and 64 miles (to Secombe).

      The distance between F and S is between 15 and 16 miles.

      So if, for example, the distance between F and S was 15.2 miles, and the signposts are at distances of 1.2 miles, 9.4 miles and 48.6 miles from F, then they would read:

      1.2 miles from F, 16.4 miles from S: “F 1, S 16”
      9.4 miles from F, 24.6 miles from S: “F 9, S 25”
      48.6 miles from F, 63.8 miles from S: “F 49, S 64”

      Without the restriction on the squares there are further solutions that use distances of 100 and 121 (and higher values):

      signs = (4, 25) (16, 36) (100, 121); F to S = 20 – 21 miles
      signs = (9, 49) (25, 64) (81, 121); F to S = 39 – 40 miles

      And with even higher values we can solve the puzzle using exact distances:

      signs = (1, 49) (16, 64) (121, 169); F to S = 48 miles

      Like

  • Jim Randell 8:46 am on 24 September 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2848: Coffee breaks 

    From The Sunday Times, 23rd April 2017 [link]

    The roads on our estate form a grid consisting of three roads running west-to-east with a number of other roads running south-to-north from the bottom road across the middle road to the top road. I live at the south-west corner of the grid and I work at the north-east corner. Each day I walk to work by one of the various shortest possible routes along the roads: there is a two-figure number of such routes. One quarter of my possible routes pass Caffee Claudius, and one quarter of my routes pass Spenda Coffee (which are on different roads).

    How many of my routes pass both the coffee shops?

    [teaser2848]

     
    • Jim Randell 8:47 am on 24 September 2019 Permalink | Reply

      I considered coffee shops that are located somewhere on the roads between the intersection points of the grid. (If we consider coffee shops at the intersections there are no solutions where the two shops are not on the same road).

      This Python 3 program constructively generates the possible paths in a grid, and then looks for segments of the paths that appear in exactly one quarter of a possible paths. We then select two of these segments for the positions of the coffee shops and count how many paths include both the segments. It runs in 76ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, div, multiset, tuples, subsets, contains, seq_all_same, printf
      
      # generate paths from (0, 0) to (x, y)
      def paths(x, y, s=[]):
        if x == y == 0:
          yield [(0, 0)] + s
        else:
          if x > 0: yield from paths(x - 1, y, [(x, y)] + s)
          if y > 0: yield from paths(x, y - 1, [(x, y)] + s)
      
      y = 2
      for x in irange(1, inf):
      
        # the total number of different routes
        ps = list(paths(x, y))
        t = len(ps) # t = C(x + y, y)
        if t < 10: continue
        if t > 99: break
      
        q = div(t, 4)
        if q is None: continue
      
        printf("[x={x} y={y}] t={t}, q={q}")
      
        # count the number of paths that use each of the line segments on the grid
        segs = multiset.from_seq(*(tuples(p, 2) for p in ps))
      
        # find segments that appear q times
        qs = list(k for (k, v) in segs.items() if v == q)
        printf("-> qs={qs}")
      
        # choose two of them
        for (q1, q2) in subsets(qs, size=2):
          # that don't lie on the same road
          if any(seq_all_same(x) for x in zip(*(q1 + q2))): continue
          # and count the paths that include both segments
          n = sum((contains(p, q1) != -1 and contains(p, q2) != -1) for p in ps)
          printf("-> n={n} [q1={q1} q2={q2}] (*** SOLUTION ***)")
      

      Solution: Only one route passes both coffee shops.

      There are 7 N-S roads.

      (The coffee shops are indicated by stars. The single route is shown in red).

      The number of routes on an x by y grid is given by: C(x + y, x), or C(x + y, y).

      In this case y = 2, so x must be in the the range 3 … 12 in order for the number of routes to be a 2-digit number.

      For the number of routes to be exactly divisible by 4 we must have x = 6 or 7.

      If x = 7 the number of routes is 36, and there are no segments that are used in exactly 36/4 = 9 shortest routes.

      If x = 6 the number of routes is 28, and only the two vertical segments shown in red on the diagram have 28/4 = 7 shortest routes using them. So these give the locations of the coffee shops, and there is only one shortest route that uses both of them together.

      If we require the coffee shops to be at intersections, then we find the only possible positions are shops at (0, 1) and (6, 1), but these both lie on the y = 1 road, so does not provide a viable solution. Although potentially it does allow a solution where one of the coffee shops is at one of these intersections, and the other one is on a segment between intersections, but it doesn’t change the answer to the puzzle.

      The restriction on there being a 2-digit number of shortest paths limits the range of x to a small number of values, but even without this restriction I didn’t find any further candidate solutions (with segments lying on one quarter of the total number of paths) for x up to 5000.

      However there are further candidate locations if the coffee shops are allowed on the intersections. For example with x = 47 we could have shops at (6, 1), (41, 1), and with x = 286 we could have shops at (41, 1), (245, 1), and with x = 1679 we could have shops at (245, 1), (1434, 1). However when choosing 2 shops these all fall foul of the condition that that the shops be on different roads, so don’t provide viable solutions.

      Like

      • Jim Randell 4:49 pm on 24 September 2019 Permalink | Reply

        Here is a modified version of the program that allows the coffee shops to be on the segments between intersections or at the intersections themselves. Instead of constructing the paths it uses the formula C(x + y, x) to count the number of paths. The answer to the puzzle is the same, however.

        Run: [ @repl.it ]

        from itertools import product
        from enigma import multiply, C, irange, inf, div, subsets, seq_all_same, printf
        
        # count the number of paths along a sequence of segments
        paths = lambda *ps: multiply(C(x + y, x) for (x, y) in ps)
        
        # grid segment between two points
        def seg(p, q):
          ((px, py), (qx, qy)) = (p, q)
          return (qx - px, qy - py)
        
        y = 2
        for x in irange(1, inf):
        
          # the total number of different routes
          t = paths((x, y))
          if t < 10: continue
          if t > 99: break
        
          q = div(t, 4)
          if q is None: continue
        
          printf("[x={x} y={y}] t={t}, q={q}")
        
          # count the number of paths that use each of the line segments and nodes on the grid
          qs = list()
          for (i, j) in product(irange(0, x), irange(0, 2)):
            # line segment N
            if j < 2 and paths((i, j), seg((i, j + 1), (x, y))) == q:
              qs.append(((i, j), (i, j + 1)))
            # line segment E
            if i < x and paths((i, j), seg((i + 1, j), (x, y))) == q:
              qs.append(((i, j), (i + 1, j)))
            # node
            if paths((i, j), seg((i, j), (x, y))) == q:
              qs.append(((i, j),))
        
          printf("-> qs={qs}")
        
          # choose two of them
          for (q1, q2) in subsets(qs, size=2):
            # that don't lie on the same road
            if any(seq_all_same(x) for x in zip(*(q1 + q2))): continue
            # and count the paths that include both segments
            n = paths(q1[0], seg(q1[-1], q2[0]), seg(q2[-1], (x, y)))
            printf("-> n={n} [q1={q1} q2={q2}] (*** SOLUTION ***)")
        

        One shop is on the line (0, 0) – (0, 1) and the other is on the line (6, 1) – (6, 2), all locations are acceptable apart from (0, 1) together with (6, 1), as then the shops are both on the y = 1 road.

        Like

  • Jim Randell 3:58 pm on 13 September 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2973: Something in common 

    From The Sunday Times, 15th September 2019 [link]

    I have written down four different numbers. The third number is the highest common factor of the first two (i.e. it is the largest number that divides exactly into both of them). The fourth number is the lowest common multiple of the first two (i.e. it is the smallest number that both of them divide exactly into).

    I can consistently replace digits by letters in my numbers so that the highest common factor is HCF and the lowest common multiple is LCM.

    What are the first two numbers?

    [teaser2973]

     
    • Jim Randell 4:06 pm on 13 September 2019 Permalink | Reply

      The two mystery numbers have a common divisor that is 3 digits, and also the have a common multiple that is 3 digits, so they are both 3 digit numbers themselves.

      Denoting the numbers UVW and XYZ we can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to give a direct interpretation of the the puzzle.

      This run file executes in 989ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      --distinct="CFHLM"
      --answer="(UVW, XYZ)"
      
      "gcd(UVW, XYZ) = HCF"
      "lcm(UVW, XYZ) = LCM"
      
      "all_different(UVW, XYZ, HCF, LCM)"
      
      "UVW < XYZ"
      

      Solution: The first two numbers are 278 and 417.

      hcf(278, 417) = 139
      lcm(278, 417) = 834

      Like

      • Jim Randell 5:14 pm on 13 September 2019 Permalink | Reply

        Here’s an alternative approach that uses a bit of analysis:

        Each of the mystery numbers must be some small (proper) multiple of HCF, say, A × HCF and B × HCF. And A and B must be co-prime.

        We can then use the fact that:

        hcf(p, q) × lcm(p, q) = p × q

        to give a faster alphametic approach.

        The following run file executes in 173ms.

        Run: [ @repl.it ]

        #!/usr/bin/env python -m enigma -r
        
        SubstitutedExpression
        
        --distinct="CFHLM"
        --answer="(A * HCF, B * HCF)"
        
        "1 < A < B"
        "gcd(A, B) = 1"
        
        "A * B * HCF = LCM"
        

        Actually it is clear that A × B < 10, so the only options are A = 2, B = 3, giving rise to the following one-line solution:

        % python -m enigma SubstitutedExpression "6 * HCF = LCM" --answer="(2 * HCF, 3 * HCF)"
        (6 * HCF = LCM) ((2 * HCF, 3 * HCF))
        (6 * 139 = 834) ((2 * 139, 3 * 139)) / C=3 F=9 H=1 L=8 M=4
        (2 * HCF, 3 * HCF) = (278, 417) [1 solution]
        

        Like

    • GeoffR 10:09 am on 17 September 2019 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:H; var 0..9:C; var 0..9:F;
      var 1..9:L; var 0..9:M;
      
      var 100..999:N1; var 100..999:N2;
      var 100..999:HCF = 100*H + 10*C + F;
      var 100..999:LCM = 100*L + 10*C + M;
      
      constraint all_different( [N1, N2, HCF, LCM] );
      constraint all_different( [H, C, F, L, M] );
      
      constraint LCM * HCF == N1 * N2;
      
      constraint N1 mod HCF == 0 /\ N2 mod HCF == 0;
      
      solve maximize(HCF);
      
      output [ " First number = " ++ show(N1) ++ "\n"
      ++ " Second number = " ++ show(N2) ++ "\n"
      ++ " Highest common factor = " ++ show(HCF) ++ "\n"
      ++ " Lowest common multiple = " ++ show(LCM) ]; 
      
      

      Like

  • Jim Randell 4:31 pm on 19 August 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2884: Farewell 

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

    Today I am retiring after editing this column for 40 very pleasurable years. My heartfelt thanks go out to all the setters and solvers of puzzles with whom I have corresponded.

    To celebrate the 40 years I threw a party for the puzzle-setters. At the party we assigned a different whole number from 1 to 26 to each letter of the alphabet; for example, we had A=13 and Z=3. We did this in such a way that, for each person present (including me), the values of the letters of their Christian name added to 40.

    Bob, Graham, Hugh, Nick and Richard were there, as were two of Andrew, Angela, Danny, Des, Ian, John, Mike, Peter, Robin, Steve and Tom.

    Which two?

    Victor Bryant also contributed many Enigma puzzles for New Scientist under the pseudonym Susan Denham.

    [teaser2884]

     
    • Jim Randell 4:32 pm on 19 August 2019 Permalink | Reply

      I treated this puzzle as a pair of linked alphametic problems in base 27 (so the symbols have values from 1 to 26), using the [[ SubstitutedExpression() ]] solver from the enigma.py library. It’s not especially quick, but it is moderately succinct. It runs in 2.60s.

      Run: [ @repl.it ]

      from enigma import SubstitutedExpression, irange, join, subsets, printf
      
      # initial words
      ws0 = [ "VICTOR", "BOB", "GRAHAM", "HUGH", "NICK", "RICHARD" ]
      
      # additional words
      ws1 = [ "ANDREW", "ANGELA", "DANNY", "DES", "IAN", "JOHN", "MIKE", "PETER", "ROBIN", "STEVE", "TOM" ]
      
      # make a puzzle where words in <ws> add to <n>
      def puzzle(ws, n, **args):
        kw = dict(base=27, digits=irange(1, 26), verbose=0) # default args
        kw.update(args)
        return SubstitutedExpression(list((join(w, sep=' + '), n) for w in ws), **kw)
      
      # format a puzzle solution <s>
      fmt = lambda s: join((join((k, "=", s[k])) for k in sorted(s.keys())), sep=" ")
      
      # make a puzzle with where words in <ws0> add up to 40, with initial conditions
      p0 = puzzle(ws0, 40, s2d=dict(A=13, Z=3))
      
      # find solutions to the first puzzle
      for s0 in p0.solve():
      
        # choose 2 words from <ws1>
        for ws2 in subsets(ws1, size=2):
      
          # make a puzzle where words in <ws2> add to 40, using the letters to numbers assignment in <s0>
          p2 = puzzle(ws2, 40, s2d=s0)
      
          # find a solution to the second puzzle
          for s2 in p2.solve(first=1):
            # output the solution <s2>
            printf("+ {ws2} [{s2}]", ws2=join(ws2, sep=", "), s2=fmt(s2))
      

      Solution: DES and MIKE also add up to 40.

      There are four ways the letters can be assigned to make the required set of names add up to 40.

      The following letters are fixed:

      A=13 Z=3
      B=16 D=10 E=18 G=7 H=4 M=2 O=8 R=1 S=12 U=25

      Then C, I, K, N, T, V have one of the following assignments:

      C=5 I=6 K=14 N=15 T=9 V=11
      C=5 I=6 K=14 N=15 T=11 V=9
      C=6 I=5 K=15 N=14 T=9 V=11
      C=6 I=5 K=15 N=14 T=11 V=9

      The remaining letters: J, L, P, W, Y (and the unused letters: F, Q, X) take on the remaining values: 17, 19, 20, 21, 22, 23, 24, 26 (in any order).

      Like

    • GeoffR 7:38 pm on 19 August 2019 Permalink | Reply

      I had to change to the Chuffed Solver after the Geocode solver froze – this has happened previously.

      I found multiple solutions, all with MIKE and DES adding up to 40.
      I noticed the names which seemed to vary most in value were ANGELA, JOHN and PETER.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..26:A;   var 1..26:B;   var 1..26:C;   var 1..26:D;
      var 1..26:E;   var 1..26:F;   var 1..26:G;   var 1..26:H;   
      var 1..26:I;   var 1..26:J;   var 1..26:K;   var 1..26:L;
      var 1..26:M;   var 1..26:N;   var 1..26: O;  var 1..26:P;   
      var 1..26:Q;   var 1..26:R;   var 1..26:S;   var 1..26:T;   
      var 1..26:U;   var 1..26:V;   var 1..26:W;   var 1..26:X;   
      var 1..26:Y;   var 1..26:Z;
      
      constraint A == 13 /\ Z == 3;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,
      P,Q,R,S,T,U,V,W,X,Y,Z]);
      
      % Bob, Graham, Hugh, Nick and Richard were there, plus Victor
      % - all have letters adding up to 40
      constraint B+O+B == 40 /\ G+R+A+H+A+M == 40 /\ H+U+G+H == 40
      /\ N+I+C+K == 40 /\ R+I+C+H+A+R+D == 40 /\ V+I+C+T+O+R == 40;
      
      % Two of Andrew, Angela, Danny, Des, Ian, John, Mike, 
      % Peter, Robin, Steve and Tom have letters summing to 40
      constraint sum( [A+N+D+R+E+W == 40, A+N+G+E+L+A == 40, 
      D+A+N+N+Y == 40, D+E+S == 40, I+A+N == 40, J+O+H+N == 40, 
      M+I+K+E == 40, P+E+T+E+R == 40, R+O+B+I+N == 40, 
      S+T+E+V+E == 40, T+O+M == 40]) == 2;  
      
      solve satisfy;
      
      output [ 
          "ANDREW = " ++ show (A+N+D+R+E+W) 
      ++ " ANGELA = " ++ show(A+N+G+E+L+A)
      ++ " DANNY = " ++ show(D+A+N+N+Y) 
      ++ "\nDES = " ++ show(D+E+S)
      ++ " IAN = " ++ show(I+A+N)
      ++ " JOHN = " ++ show(J+O+H+N)
      ++ "\nMIKE = " ++ show(M+I+K+E)
      ++ " PETER = " ++ show(P+E+T+E+R)
      ++ " ROBIN = " ++ show(R+O+B+I+N)
      ++ "\nSTEVE = " ++ show(S+T+E+V+E)
      ++ " TOM = " ++ show(T+O+M) ];
      
      % Multiple solutions found
      % DES = 40 and MIKE = 40 (20 solutions checked)
      
      % Typical solution
      % ANDREW = 81 ANGELA = 87 DANNY = 79
      % DES = 40 IAN = 34 JOHN = 46
      % MIKE = 40 PETER = 68 ROBIN = 46
      % STEVE = 68 TOM = 19
      % ----------
      % Finished in 396msec
      

      Like

  • Jim Randell 8:42 am on 5 August 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2893: Win some, lose some 

    From The Sunday Times, 4th March 2018 [link]

    The six teams in our local league play each other once in the season. Last season no two teams tied on points.

    Above is part of the table from the end of that season, with the teams in alphabetical order.

    However, digits have been consistently replaced by letters.

    Find the value of the number of LEMONS.

    [teaser2893]

     
    • Jim Randell 8:43 am on 5 August 2019 Permalink | Reply

      When I first looked at this puzzle I assumed the scoring regime was “2 points for a win, 1 point to each side for a draw” (which is a common scenario in Enigma puzzles [ link ]), but that gave me two possible solutions (the values for L and N are interchangeable). But using “3 points for a win, 1 point to each side for a draw” give a unique solution, and is probably what the setter had in mind. (This was later confirmed).

      I derived a set of constraints from the table and then used the general alphametic solver [[ SubstitutedExpression() ]] from the enigma.py library to solve the puzzle.

      The following run file executes in 122ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      --answer="LEMONS"
      
      # each team has played 5 matches
      "W = 5"
      
      # won + lost + drawn = 5
      "O + N <= 5"
      "S + O + M = 5"
      "L + O <= 5"
      "S <= 5"
      
      # goals for >= won, goals against >= lost
      "E >= S"
      "S >= 5 - L - O"
      "T >= L"
      "O >= (E - S) // 3" "(E - S) % 3 = 0"
      
      # points (= 3 * won + drawn) are all different
      --code="pts = lambda w, d: 3 * w + d"
      "all_different(pts(O, 5 - O - N), pts(S, M), pts(5 - L - O, O), E)"
      

      Solution: LEMONS = 370124.

      We could provide additional constraints in the run file (e.g. assign W=5; and L, M, N, O, S are 0, 1, 2, 3, 4 (in some order)) but it doesn’t make much difference to the run time if we do:

      # [optional] w, l, d can only contain digits 0-5 (and W is 5)
      --assign="W,5"
      --invalid="6|7|8|9,LMNOS"
      

      We can change the definition of [[ pts() ]] to use the “2 points for a win …” scenario, and we find there is an additional solution of:

      LEMONS = 270134

      Like

  • Jim Randell 6:21 pm on 19 July 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2965: Knock, knock! 

    From The Sunday Times, 21st July 2019 [link]

    Last year a two-figure number of teams entered our football competition. With that number, it was impossible to have a straightforward knockout competition (where half the teams are knocked out in each round), so we divided the teams into equal-sized groups, each pair of teams within a group played each other once, and the overall winner from each group went forward to the second stage consisting of a knockout competition. Unfortunately our local team was knocked out in the quarter-finals of that stage.

    This year a higher number of teams entered (but not twice as many). Again a straightforward knockout competition was impossible so we copied last year’s model but with smaller groups and more of them. By coincidence the total number of games played this year equalled the number played last year.

    How many teams entered last year and how many this year?

    [teaser2965]

     
    • Jim Randell 7:01 pm on 19 July 2019 Permalink | Reply

      In order to have a knockout tournament (without using byes) the number of teams needs to be a power of 2 (half the teams are knocked out at each stage).

      So the numbers of teams we are dealing with cannot be powers of two. But we can divide the numbers into groups where the winners of the groups can have a knockout tournament, so the number of groups must be a power of 2. Hence the total number of teams has to have a divisor that is a power of 2.

      Within a group of size m, the number of matches where each team plays each other team is T(m − 1).

      This Python program looks for 2-digit values for the number of teams last year, works out the total number of matches played in the tournament, and then finds a scenario for this year which has the same total number of matches. It runs in 91ms.

      Run: [ @repl.it ]

      from enigma import irange, div, T, bit_permutations as powers2, printf
      
      # check a positive integer is a power of 2
      is_power2 = lambda n: not(n & (n - 1))
      
      # number of teams last year (a 2-digit number)
      for n in irange(24, 99, step=8):
        # skip numbers that are powers of 2
        if is_power2(n): continue
      
        # divide n into k groups of m (k is a power of 2)
        # a team was knocked out in the quarter finals, so k > 7
        for k in powers2(8):
          m = div(n, k)
          if m is None: break
          # calculate the total number of games played
          t = k * T(m - 1) + (k - 1)
      
          # now look for possible values with the same total, but with smaller groups
          for m2 in irange(3, m - 1):
            # and m2 must not be a power of 2
            if is_power2(m2): continue
            # calculate the number of groups
            k2 = div(t + 1, T(m2 - 1) + 1)
            if k2 is None: continue
            # there must be more groups
            if not(k2 > k): continue
            # k2 must be a power of 2
            if not is_power2(k2): continue
            # the total number of teams this year
            n2 = k2 * m2
            # and n2 greater than n, but not twice n
            if not(n2 > n and n2 != n * 2): continue
      
            printf("t={t}: last year = {n} teams ({k} groups of {m}), this year = {n2} teams ({k2} groups of {m2})")
      

      Solution: 56 teams entered last year. 80 teams entered this year.

      Last year the 56 teams were formed into 8 groups of 7. Each group would play 21 matches, and then the 8 winners of the groups would play 4 quarter-finals, 2 semi-finals and 1 final to give 175 matches in total.

      This year the 80 teams were formed into 16 groups of 5. Each group would play 10 matches, and then the 16 winners of the groups would play 8 eighth-finals, 4 quarter-finals, 2 semi-finals and 1 final to also give 175 matches in total.


      As a team was knocked out in the quarter-finals last year, the number of groups must have been at least 8, and we can consider multiples of 8 (that are not exact powers of 2). So there are only 8 candidate numbers for the number of teams last year: 24, 40, 48, 56, 72, 80, 88, 96.

      There are two “near miss” scenarios:

      48 teams last year (8 groups of 6), and 96 teams this year (32 groups of 3). Both have 127 matches.
      96 teams last year (16 groups of 6), and 192 teams this year (64 groups of 3). Both have 255 matches.

      But both are eliminated by the requirement that the number of teams this year is not twice the number of teams last year.

      When I initially read the puzzle I took “not twice as many” to mean “fewer than twice as many”, but in my program I relaxed this condition to “not exactly twice as many”, and the single solution remains.

      There is also the question of whether, in the knockout tournament, there is a match to decide 3rd and 4th places. It doesn’t matter if there is or not, as long as both tournaments use the same format. If there is a match for the semi-final losers then the total numbers of matches will be increased by 1.

      Like

      • Robert Brown 8:30 pm on 19 July 2019 Permalink | Reply

        Doesn’t need a program . . .

        Like

    • Jim Randell 12:52 pm on 22 July 2019 Permalink | Reply

      Here is a MiniZinc model for the puzzle. It executes in 66ms.

      %#! minizinc -a
      
      % powers of 2
      set of int: pow2 = { pow(2, i) | i in 1..9 };
      
      
      % last year: n teams, k groups of m
      var 10..99: n; % n is a 2 digit number
      var 3..33: k;
      var 5..99: m;
      
      % n can be divided into k groups of m;
      % n is not a power of 2
      % k is a power of 2
      % m is not a power of 2
      constraint k * m = n;
      constraint not(n in pow2);
      constraint k in pow2;
      constraint not(m in pow2);
      
      % k is at least 8
      constraint not(k < 8);
      
      
      % this year: n1 teams, k1 groups of m1
      var 11..1000: n1;
      var 4..334: k1;
      var 3..98: m1;
      
      constraint n1 = k1 * m1;
      constraint not(n1 in pow2);
      constraint k1 in pow2;
      constraint not(m1 in pow2);
      
      % more teams, but not twice as many
      constraint n1 > n;
      constraint n1 != 2 * n;
      
      % smaller groups, but more of them
      constraint m1 < m;
      constraint k1 > k;
      
      % total number of matches is the same
      constraint k * (m * (m - 1) + 2) = k1 * (m1 * (m1 - 1) + 2);
      
      solve satisfy;
      

      I wasn’t sure how use the neat trick to test for powers of 2 in MiniZinc, so I assumed an upper bound of 1,000 teams, and just made a set of powers of 2 less than this.

      Like

  • Jim Randell 5:20 pm on 11 May 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2913: Return tickets 

    From The Sunday Times, 22nd July 2018 [link]

    In our tombola the tickets were numbered consecutively from 1 upwards and were printed in books of 20. A local airline donated the prizes – a number of tickets to Paris and back. We decided to split the prizes into single-journey tickets and award them in an unusual way. If any ticket number had all different digits which were in increasing order then it won an outward flight to Paris: if it had all different digits which were in decreasing order then it won a flight back from Paris. So, for example, number 145 won an outward flight, number 30 won a flight back, and single-figure numbers were lucky enough to win tickets there and back. Luckily we had exactly the right number of tickets for all the prizes to be awarded.

    How many tickets did we print?

    [teaser2913]

     
    • Jim Randell 5:21 pm on 11 May 2019 Permalink | Reply

      I originally wrote a program that just considers increasing ticket numbers until it finds a solution, but the Python program below finds all possible answers for a specified number of tickets per book (which can be given as a command line argument).

      It does this by collecting increasing and decreasing numbers, and then considering them in order. It runs in 87ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, nconcat, arg, printf
      
      # k tickets per book
      k = arg(20, 0, int)
      printf("[{k} tickets per book]")
      
      # collect increasing and decreasing numbers (actually, we only need max_size=4)
      incs = set(nconcat(s) for s in subsets(irange(0, 9), min_size=1, max_size=9) if s[0] != 0)
      decs = set(nconcat(s) for s in subsets(irange(9, 0, step=-1), min_size=1, max_size=9) if s != (0,))
      
      # find when the increasing and decreasing totals are the same
      ninc = ndec = 0
      s = None
      for t in sorted(incs.union(decs)):
        if t in incs: ninc += 1
        if t in decs: ndec += 1
        if s:
          (t0, n) = s
          t1 = t - 1
          # look for answers in the range [t0..t1]
          ans = list(x for x in irange(t0, t1) if x % k == 0)
          printf("tickets = 1 - {t0}..{t1} [incs = decs = {n}] ans={ans}", t1=t - 1)
          s = None
        if ninc == ndec:
          s = (t, ninc)
      

      Solution: 1480 tickets were printed.

      It turns out there are no solutions larger than 8519, so a basic search of ticket numbers can stop there (and give a program that finds all possible solutions), and so the code above need only consider numbers of up to 4-digits.

      8519 is divisible by 7 and 1217. With 7 tickets per books have solutions with 7, 1484, 8512, 8519 tickets. With 1217 tickets per book the only solution is 8519 tickets.

      Like

  • Jim Randell 8:10 am on 30 April 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Brainteaser 1567: How many teams? 

    From The Sunday Times, 20th September 1992 [link]

    The teams in our local football league each play each of the others once in a season, earning three points for a win and one point for a draw. After the last Saturday of the season (when all the teams had played one game that day) I worked out the league table (with the teams in alphabetical order). I then consistently replaced digits in the table by letters, using different letters for different digits.

    Here is part of that table, showing some of the entries in three of the rows:

    What is the number of teams in the league? And what is the number TEAMS?

    This puzzle was selected for the book Brainteasers (2002, edited by Victor Bryant). The wording here is taken from the book and was only slightly changed from the original puzzle.

    [teaser1567]

     
    • Jim Randell 8:11 am on 30 April 2019 Permalink | Reply

      If there are n teams in the league, then at the end of the season each team has played all the other (n – 1) teams, and this total number of matches must be represented in the sum of the “won”, “drawn”, “lost” columns in the table.

      H + O + W = n – 1
      M + A + N = n – 1
      T + E + A = n – 1

      If each team played one match on the final Saturday, then there must be an even number of teams. And if n is even, then (n – 1) is odd.

      We are given the points in the third row:

      3T + E = S

      And we are given the “goals against” for two teams. Each “lost” game involves conceding at least one goal, so:

      N ≤ Y, A ≤ M

      (and the values cannot be equal).

      Together these give us enough information to assign values to the letters.

      We can solve these alphametic expressions using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      The following run file executes in 216ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      # sums of "won", "drawn", "lost" are the same
      "H + O + W == M + A + N == T + E + A"
      
      # sum is odd
      "(H + O + W) % 2 = 1"
      
      # points for third row
      "3 * T + E = S"
      
      # "lost" <= "goals against"
      "N < Y"
      "A < M"
      
      # answer: (number of teams, value of TEAMS)
      --answer="(H + O + W + 1, TEAMS)"
      

      Solution: There are 12 teams in the league. TEAMS = 16459.

      The first row has “won”, “drawn”, “lost” values of 0, 3, 8, but we don’t know which order.

      The second row has 5 “won”, 4 “drawn”, 2 “lost”, and 7 “goals against”.

      The third row has 1 “won”, 6 “drawn”, 4 “lost” and 5 “goals against”, giving 9 points.

      There are 12 teams, so there are 66 matches played in total.

      Like

  • Jim Randell 8:57 am on 16 April 2019 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2952: Silly slip 

    From The Sunday Times, 21st April 2019 [link]

    Please help me find my silly slip. I correctly added a five-figure number to a four-figure number to give a six-figure total. Then I tried to substitute letters for digits systematically and I ended up with:

    SILLY + SLIP = PLEASE

    However, in these letters I have made one silly slip, so please find it and then work out what the correct sum was.

    What was the correct six-figure numerical answer?

    [teaser2952]

     
    • Jim Randell 8:58 am on 16 April 2019 Permalink | Reply

      We can use the [[ bungled_sum() ]] solver (originally written for Puzzle 56).

      Run: [ @repl.it ]

      >>> bungled_sum(['SILLY', 'SLIP', 'PLEASE'])
                      L
      SILLY + SLIP = P?EASE / @[2,1] L -> ?
      97225 + 9271 = 106496 / ?=0 A=4 E=6 I=7 L=2 P=1 S=9 Y=5
      

      Solution: The numerical result of the sum is 106496.

      The mistake is in the L of PLEASE (the result of the sum), it should be a letter that is different from all the other letters, although that does make it hard to make an acceptable word, but we can check this makes a viable alphametic sum using the [[ SubstitutedSum() ]] solver from the enigma.py library.

      % python enigma.py SubstitutedSum "SILLY + SLIP = PXEASE"
      (SILLY + SLIP = PXEASE)
      (97225 + 9271 = 106496) / A=4 E=6 I=7 L=2 P=1 S=9 X=0 Y=5
      

      Like

      • Jim Randell 4:06 pm on 20 April 2019 Permalink | Reply

        I assumed this puzzle was in the same vein as other “bungled sum” problems.

        But the text says that letters are substituted for digits “systematically”, but it doesn’t say that each letter stands for a different digit (which is usual in alphametic puzzles).

        If we allow letters to stand for the same digit, then we can solve the alphametic sum:

        % python enigma.py SubstitutedExpression "SILLY + SLIP = PLEASE" --distinct=""
        (SILLY + SLIP = PLEASE)
        (99007 + 9091 = 108098) / A=0 E=8 I=9 L=0 P=1 S=9 Y=7
        [1 solution]
        

        The duplicated digits are: A and L are both 0, I and S are both 9.

        Like

      • Jim Randell 11:01 pm on 21 April 2019 Permalink | Reply

        Here is a faster (but longer) solution, using the minizinc.py library.

        from minizinc import MiniZinc, var, alphametic, substitute
        
        # the sum is a 5-digit number plus a 4-digit number and a 6-digit result
        #
        #    a b c d e      S I L L Y
        #      f g h i        S L I P
        #  -----------    -----------
        #  j k m n p q    P L E A S E
        
        fmt = "{abcde} + {fghi} = {jkmnpq}"
        
        # create the model
        p = MiniZinc(f"""
        
        include "globals.mzn";
        
        % the symbols in the incorrect sum
        {var("0..9", "AEILPSY")};
        
        constraint all_different([A, E, I, L, P, S, Y]);
        
        % symbols for the correct sum
        {var("0..9", "abcdefghijkmnpq")};
        
        % the correct sum
        constraint {alphametic(fmt)};
        
        % no leading zeros
        constraint a != 0 /\ f != 0 /\ j != 0;
        
        % the incorrect sum differs in only one place
        constraint sum([
          a != S, b != I, c != L, d != L, e != Y,
          f != S, g != L, h != I, i != P,
          j != P, k != L, m != E, n != A, p != S, q != E,
        ]) = 1;
        
        solve satisfy;
        
        """)
        
        # solve it
        for s in p.solve():
          # output the sum
          print(substitute(fmt, s))
        

        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
Create your website at WordPress.com
Get started
%d bloggers like this: