Tagged: by: Howard Williams Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 7:15 am on 4 January 2026 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3302: Challenging grandson 

    From The Sunday Times, 4th January 2026 [link] [link]

    My grandson likes making puzzles; his most recent one started with a four-digit number with all the digits different. He added up all the possible two-digit combinations of these four digits (e.g., if the digits were 0, 1, 2 and 3 he would add 01 + 02 + 03 + 10 + 12 + …). This total divided exactly into his four-digit number.

    Not satisfied with this, he said he had added an extra digit (different from all the others) to the end of his number to make a five-digit number. The five-digit number was an exact multiple of the total of all the two-digit combinations of these five digits. He said that if he told me how many digits were in this multiple, I would be able to work out his five-digit number.

    What was his five-digit number?

    [teaser3302]

     
    • Jim Randell's avatar

      Jim Randell 7:35 am on 4 January 2026 Permalink | Reply

      When constructing the sum of the combinations, with 4 digits, each can be paired with 3 others, and so appears 3 times in the tens column and 3 times in the units column. The total sum is therefore:

      33 × sum(digits)

      And starting with 5 digits the total sum is:

      44 × sum(digits)

      This Python program runs in 68ms. (Internal runtime is 955µs).

      from enigma import (irange, nsplit, div, ulambda, filter_unique, ndigits, printf)
      
      # generate possible scenarios
      def generate():
        digits = set(irange(0, 9))
      
        # the first number is a 4-digit multiple of 33 with distinct digits
        for n1 in irange.round(1000, 9999, step=33, rnd='I'):
          ds = nsplit(n1)
          if len(set(ds)) != 4: continue
          # calculate the sum of the 2-digit combinations
          t1 = sum(ds)
          s1 = 33 * t1
          # n1 is a multiple of s1
          k1 = div(n1, s1)
          if k1 is None: continue
      
          # add in an extra digit to form the second number
          for d in digits.difference(ds):
            n2 = 10*n1 + d
            # calculate the sum of the 2-digit combinations
            s2 = 44 * (t1 + d)
            # n2 is a multiple of s2
            k2 = div(n2, s2)
            if k2 is None: continue
      
            # return (number, sum, multiple) values for each number
            printf("[n1={n1} s1={s1} k1={k1} -> n2={n2} s2={s2} k2={k2}]")
            yield ((n1, s1, k1), (n2, s2, k2))
      
      # find solutions unique by number of digits in k2
      f = ulambda("((n1, s1, k1), (n2, s2, k2)): ndigits(k2)")
      ss = filter_unique(generate(), f).unique
      
      # output solutions
      for ((n1, s1, k1), (n2, s2, k2)) in ss:
        printf("n2={n2} [s2={s2} k2={k2}; n1={n1} s1={s1} k1={k1}]")
      

      Solution: [To Be Revealed]

      Like

    • Ruud's avatar

      Ruud 8:51 am on 4 January 2026 Permalink | Reply

      import peek
      import istr
      import collections
      
      collect = collections.defaultdict(list)
      for n4 in istr.range(1000, 10000):
          if not n4.all_distinct():
              continue
          s4 = 33 * sum(n4)
          if not n4.is_divisible_by(s4):
              continue
          for n1 in istr.range(10):
              if n1 in n4:
                  continue
              n5 = n4 | n1
              s5 = 44 * sum(n5)
              if n5.is_divisible_by(s5):
                  multiple = n5 / s5
                  collect[len(multiple)].append(n5)
      
      for n5s in collect.values():
          if len(n5s) == 1:
              peek(n5s[0])
      

      .

      Like

      • ruudvanderham's avatar

        ruudvanderham 7:15 pm on 4 January 2026 Permalink | Reply

        Slightly faster:

        import peek
        import istr
        import collections
        
        collect = collections.defaultdict(list)
        for p4 in istr.permutations(range(10), 4):
            n4 = istr.join(p4)
            s4 = 33 * sum(n4)
            if not n4.is_divisible_by(s4):
                continue
            for n1 in set(istr.range(10)) - set(p4):
                n5 = n4 | n1
                s5 = 44 * sum(n5)
                if n5.is_divisible_by(s5):
                    multiple = n5 / s5
                    collect[len(multiple)].append(n5)
        
        for n5s in collect.values():
            if len(n5s) == 1:
                peek(n5s[0])
        

        Like

    • Frits's avatar

      Frits 11:43 am on 4 January 2026 Permalink | Reply

      from itertools import permutations
      
      # the extra digit must be zero due to the alternating sum rule
      d = dict()
      for A, B, C in permutations(range(1, 10), 3):
        # divisibility of 11 rule (alternating digit sum is 0 or a multiple of 11)
        if (D := (A + C - B) % 11) in {0, A, B, C, 10}: continue
        # calculate sum of digits (must be a multiple of 3)
        if (s := A + B + C + D) % 3: continue
        # calculate first multiple  
        m1, r = divmod(ABCD := 1000 * A + 100 * B + 10 * C + D, 33 * s)
        if r or m1 % 2: continue  # as m2 = 7.5 * m1
        # number of digits in second multiple must be unique
        d[nd2] = 0 if (nd2 := len(str(m2 := int(7.5 * m1)))) in d else 10 * ABCD
        
      for k, v in d.items():
        if v:
          print("answer:", v)
      

      Like

      • Frits's avatar

        Frits 12:47 pm on 4 January 2026 Permalink | Reply

        from itertools import permutations
        
        # the extra digit must be zero due to the alternating sum rule
        d = dict()
        digits = set(range(1, 10))    
        # D must be even as 10 * ABCD must be divisible by 44
        for D in [2, 4, 6, 8]:
          for A, C in permutations(digits - {D}, 2):
            # divisibility of 11 rule (alternating digit sum is 0 or a multiple of 11)
            if (B := (A + C - D) % 11) in {0, A, C, D, 10}: continue
            # calculate sum of digits (must be a multiple of 3)
            if (s := A + B + C + D) % 3: continue
            # calculate first multiple  
            m1, r = divmod(ABCD := 1000 * A + 100 * B + 10 * C + D, 33 * s)
            if r or m1 % 2: continue  # as m2 = 7.5 * m1
            # number of digits in second multiple must be unique
            d[nd2] = 0 if (nd2 := len(str(int(7.5 * m1)))) in d else 10 * ABCD
              
        for k, v in d.items():
          if v:
            print("answer:", v)
        

        Like

  • Unknown's avatar

    Jim Randell 6:50 am on 9 November 2025 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3294: Four by four 

    From The Sunday Times, 9th November 2025 [link] [link]

    With the school inspector scheduled to visit her school, Tina is taking extra care in preparing her lesson plan. The lesson deals with areas, shapes and symmetries. She has produced soft cards on which have been printed a four by four grid, and will ask the pupils to cut the grid into two shapes of equal area, but by only cutting along the lines. She wanted them to create as many different possible shapes in this way, explaining that two shapes are different only if you can’t make one the same as the other by rotating it, turning it over, or both. It turned out that the maximum number of different shapes was the same as the number of pupils in the class.

    How many pupils are there in the class?

    [teaser3294]

     
    • Jim Randell's avatar

      Jim Randell 7:30 am on 9 November 2025 Permalink | Reply

      (See also: BrainTwister #29, Enigma 54).

      This Python program considers possible dissections of the grid into two connected shapes, and then records a canonical form of the shapes to find the number of different shapes.

      It runs in 233ms. (Internal runtime is 154ms).

      from enigma import (Accumulator, irange, subsets, grid_adjacency, filter2, repeat, printf)
      
      # adjacency matrix for a 4x4 grid
      adj = grid_adjacency(4, 4)
      
      # the pieces (individual cells in the grid)
      pieces = set(irange(16))
      
      # rotate the grid 90 degrees clockwise
      rot = [3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12]
      def rotate(ps): return set(rot[p] for p in ps)
      
      # mirror the grid vertically
      mir = [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12]
      def mirror(ps): return set(mir[p] for p in ps)
      
      # slide a shape to the bottom LH corner
      (Bs, Ls) = ({0, 1, 2, 3}, {0, 4, 8, 12})
      def slide(ps):
        while Bs.isdisjoint(ps):
          ps = set(p - 4 for p in ps)
        while Ls.isdisjoint(ps):
          ps = set(p - 1 for p in ps)
        return ps
      
      # find the canonical form for a shape
      def canonical(ps):
        # find the minimal representation
        r = Accumulator(fn=min)
        # consider the possible rotations of the shape
        for ss in repeat(rotate, ps, 3):
          # also consider reflections
          for xs in repeat(mirror, ss, 1):
            # slide to minimal position
            xs = slide(xs)
            r.accumulate(tuple(sorted(xs)))
        # return the minimum value
        return r.value
      
      # are the pieces in <ps> connected?
      def is_connected(ps, cs=None):
        if ps and not cs:
          # move a piece from ps to cs
          ps = set(ps)
          cs = {ps.pop()}
        # move pieces in ps that are connected to cs into cs
        while ps:
          # partition ps into those connected to cs and those that aren't
          (ps, pcs) = filter2((lambda p: cs.isdisjoint(adj[p])), ps)
          if not pcs: return False
          cs.update(pcs)
        return True
      
      # collect canonical shapes
      ss = set()
      
      # choose an 8-subset of the pieces
      for ps in subsets(pieces, size=8, fn=set):
        # and the remaining pieces
        rs = pieces.difference(ps)
        # check both sets are connected
        if not (is_connected(ps) and is_connected(rs)): continue
        # collect canonical shapes
        ss.add(canonical(ps))
      
      # output canonical shapes
      for (i, ps) in enumerate(sorted(ss), start=1): printf("{i}: {ps}")
      printf("{n} canonical shapes", n=len(ss))
      

      (The internal runtime can easily be reduced to 41ms by noting that each shape must include a corner cell, and a cell adjacent to it, so we only need to look for 6 other cells to go with them).

      Solution: There are 19 pupils in the class.

      These are the shapes (in grey) that can be generated:

      Although these are not necessarily the only ways to cut the shapes out of the grid. (Note that cutting out shape 9 and shape 15 both leave a complementary shape (in orange) that corresponds to shape 18).

      Like

    • Frits's avatar

      Frits 3:58 pm on 9 November 2025 Permalink | Reply

      Version 1.

      I had a version without itertools.combinations but that was less efficient.

      from collections import defaultdict
      from itertools import combinations
      
      N = 4
      N2 = N * N
      H = N2 // 2
      
      def I(i, j, n=N):
        return i * n + j
      
      def rotate(s, n):
        r = [None] * n * n
        for i in range(n):
          for j in range(n):
            r[I(j, n - i - 1, n)] = s[I(i, j, n)]
        return tuple(r)
      
      def mirror(s, n):
        r = [None] * n * n
        for i in range(n):
          for j in range(n):
            r[I(j, i, n)] = s[I(i, j, n)]
        return tuple(r)
      
      # is <s> the smallest after rotations/mirrors?
      def is_canonical(s):
        z4 = (0, ) * N
        # go from 4x4 matrix to a 3x3 matrix if all data in SE corner
        if s[:N] == z4:
          if tuple(s[i * N] for i in range(N)) == z4:
            s = tuple(s[i] for i in range(N, N2) if i % N)
          
        # dimension of <s>
        n = int(len(s)**.5) 
        
        # rotations of the square
        if (rot1 := rotate(s, n)) < s: return False
        if (rot2 := rotate(rot1, n)) < s: return False
        if (rot3 := rotate(rot2, n)) < s: return False
        # mirrors
        if (mirror(s, n)) < s: return False
        if (mirror(rot1, n)) < s: return False
        if (mirror(rot2, n)) < s: return False
        if (mirror(rot3, n)) < s: return False
        
        return True
      
      # adjacent squares  
      d_a = defaultdict(list)
      for a in range(N):
        for b in range(N):
          for i, c in enumerate([a - 1, a, a + 1]):
            for j, d in enumerate([b - 1, b, b + 1]):
              if 0 <= c < N and 0 <= d < N and i + j in {1, 3}:
                d_a[I(a, b)] += [I(c, d)]
      
      # are all positive elements in <s> connected with each other
      def _connected(k, s, adj, curr):
        global conn_seen
        if len(conn_seen) == H: 
          yield conn_seen
        elif k:
          # add positive adjacent squares
          conn_seen |= set(x for x in adj[curr] if s[x])    
          for nxt in adj[curr]:
            if s[nxt]:
              yield from _connected(k - 1, s, adj, nxt)
      
      def connected(k, s, adj, curr):
        global conn_seen
        conn_seen = {curr}
        # check if all selected squares are connected
        for conn in _connected(k, s, adj, curr): 
          return True
        
        return False
      
      sols = []         
      # check all shapes of <H> squares
      for cmb in combinations(range(N2), H):
        s = tuple((1 if i in cmb else 0)for i in range(N2))
        if not connected(H - 1, s, d_a, cmb[0]): continue
        # check if <s> is smallest of all rotations/mirrors
        if is_canonical(s):
          oth = tuple(1 - x for x in s)
          # determine first square not selected
          f = next(i for i, x in enumerate(oth) if x)
          if not connected(H - 1, oth, d_a, f): continue
          sols.append(s)
          
      print("answer:", len(sols))
      

      Like

      • Frits's avatar

        Frits 7:18 am on 11 November 2025 Permalink | Reply

        When comparing my “connected()” to Brian Gladman’s “is_connected()” I noticed that my version was slow. This one is more efficient. The overall program now also has a decent internal runtime.

        # are all positive elements in <s> connected with each other
        def _connected(s, adj, curr, ss=set()):
          global conn_seen
          # add positive adjacent squares
          conn_seen |= set(x for x in adj[curr] if s[x])    
          if len(conn_seen) == H: 
            yield conn_seen
          else:
            for nxt in adj[curr]:
              if s[nxt] and nxt not in ss:
                yield from _connected(s, adj, nxt, ss | {nxt})
        
        def connected(s, adj, curr):
          global conn_seen
          conn_seen = {curr}
          # check if all selected squares are connected
          for _ in _connected(s, adj, curr, {curr}): 
            return True
          
          return False
        

        Like

        • Brian Gladman's avatar

          Brian Gladman 2:42 pm on 11 November 2025 Permalink | Reply

          @Frits
          The version on which you comment above was:

          # given a set <p> of (x, y) positions for unit squares arranged 
          # on a rectangular grid, return true if the set of squares form
          # a connected region
          def is_connected(p):
            # if two sets of squares in a list of such sets have 
            # any squares that are connected, combine the two sets 
            def combine(s):
              for s1, s2 in combinations(s, 2):
                if any(y in adj[x] for x in s1 for y in s2):
                  s[s.index(s1)].update(s2)
                  s.remove(s2)
                  return True
              return False
            sets = [set([n]) for n in p]
            # combine any sets that have connected members
            while combine(sets):
              pass
            # are all squares connected?
            return len(sets) == 1
          

          After thinking about it, I realised it was pretty inefficient so I updated it.

          Like

    • Frits's avatar

      Frits 7:26 am on 10 November 2025 Permalink | Reply

      Version 2.

      More code (not my priority) but more efficient (my priority).
      When cutting from side to side all squares in both shapes have to be connected.
      Choosing 4 starting positions for curring is enough to generate all possible shapes.

      from collections import defaultdict
      
      N = 4
      N2 = N * N
      H = N2 // 2
      
      # direction moving from x to y: Up/Right/Down/Left: 0/1/2/3
      dir = lambda x, y: (0 if x[0] > y[0] else 1 if y[1] > x[1] else
                          2 if x[0] < y[0] else 3)
      
      def I(i, j, n=N):
        return i * n + j
      
      def rotate(s, n):
        r = [None] * n * n
        for i in range(n):
          for j in range(n):
            r[I(j, n - i - 1, n)] = s[I(i, j, n)]
        return tuple(r)
      
      def mirror(s, n):
        r = [None] * n * n
        for i in range(n):
          for j in range(n):
            r[I(j, i, n)] = s[I(i, j, n)]
        return tuple(r)
      
      # is squaee list <s> the highest after rotations/mirrors?
      def is_canonical(s):
        z4 = (0, ) * N
        # go from N x N matrix to a N-1 x N-1 matrix if all data in NW corner
        if s[N2 - N:] == z4:
          if tuple(s[i * N + N - 1] for i in range(N)) == z4:
            s = tuple(s[i] for i in range(N2 - N) if (i + 1) % N)
          
        # dimension of <s>
        n = int(len(s)**.5) 
         
        # rotations of the square
        if (rot1 := rotate(s, n)) > s: return False
        if (rot2 := rotate(rot1, n)) > s: return False
        if (rot3 := rotate(rot2, n)) > s: return False
        # mirrors
        if (mirror(s, n)) > s: return False
        if (mirror(rot1, n)) > s: return False
        if (mirror(rot2, n)) > s: return False
        if (mirror(rot3, n)) > s: return False
         
        return True
      
      # check cutting sequence <s> and return list of squares
      def gen_squares(s):
        # containers for shape 1 and 2
        shape1, shape2 = set(), set()
        # process the directions of the cuts
        for x, y in zip(s, s[1:]):
          match(dir(x, y)):
            case 0: # U: add square east of it
              shape1.add(I(y[0], y[1]))
              shape2.add(I(y[0], y[1] - 1))
            case 1: # R: add square south of it
              shape1.add(I(x[0], y[1] - 1))  
              shape2.add(I(x[0] - 1, y[1] - 1))  
            case 2: # D: add square west of it
              shape1.add(I(x[0], y[1] - 1))
              shape2.add(I(x[0], y[1]))
            case 3: # L: add square north of it
              shape1.add(I(x[0] - 1, y[1]))   
              shape2.add(I(x[0], y[1]))    
        
        ns = True
        # keep coloring adjacent fields of shape 1 with same color
        while ns:
          ns = set()
          for s in shape1:
            # if adjacent square not in shape2 then add to shape1
            ns |= set(a for a in d_a[s] if a not in shape1 and 
                                           a not in shape2)
          shape1 |= ns 
        
        # both shapes must be of the same size
        if len(shape1) != H:
          return None
        return tuple(1 if i in shape1 else 0 for i in range(N2))
        
      # generate a cutting sequence from side to side and return squares
      def cut(curr, ss=[]):
        # stop when reaching a side 
        if len(ss) > 1 and not {0, N}.isdisjoint(ss[-1]):
          # do we have <H> squares per shape?
          if (sqs := gen_squares(ss)) is not None:
            yield sqs
        else:
          # move the pair of scissors in 4 directions
          for mv in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            new = (curr[0] + mv[0], curr[1] + mv[1])
            # if not out of bounds
            if {-1, N + 1}.isdisjoint(new) and new not in ss:
              # we must move inside the NxN square after first cut
              if ss or {0, N}.isdisjoint(new): 
                yield from cut(new, ss + [new])
      
      # adjacent squares  
      d_a = defaultdict(list)
      for a in range(N):
        for b in range(N):
          for i, c in enumerate([a - 1, a, a + 1]):
            for j, d in enumerate([b - 1, b, b + 1]):
              if 0 <= c < N and 0 <= d < N and i + j in {1, 3}:
                d_a[I(a, b)] += [I(c, d)]
                 
      seen = set()
      # start cutting near last column
      for st in [(0, 3), (1, 4), (2, 4), (3, 4)]:
        # generate squares by performing cuts
        for s in cut(st, [st]):
          # check if <s> is highest of all rotations/mirrors
          if is_canonical(s):
            seen.add(s)
      
      print("answer:", len(seen)) 
      

      Like

    • Alex.T.Sutherland's avatar

      Alex.T.Sutherland 2:19 pm on 15 November 2025 Permalink | Reply

      I have a pattern that I don’t think is included in the above results.Should the answer be 20?
      Am I wrong?

         1   1   0   0
         1   1   1   0
         1   1   1   0
         0   0   0   0

      Let me know what you think.

      Like

      • Jim Randell's avatar

        Jim Randell 2:29 pm on 15 November 2025 Permalink | Reply

        @Alex: The 0’s are the same as shape 15 in my diagram. And the 1’s are the same as shape 18.

        Like

        • Alex.Sutherland's avatar

          Alex.Sutherland 4:24 pm on 20 November 2025 Permalink | Reply

               Thank you for your reply.
               My error .I have cleared up the problem.
               The following may be of interest.

               It is concerned with Teaser 3295 (Always as the Crow flies.)

               Quad = abcd; Vertical diagonal = S; Horz diagonal = F;

               My answer is based on the equation a^2 + c^2 = b^2 + d^2 simce it is
               an orthodiagonal quad .
               This is the equation for Pythagorean Trebles (x^2 * y^2 = R^2);
               I have a list (from a previous puzzle) of such trebles.
               From the list of (x y R) trebles I get a set of possible values
          for ‘abcd’.
               Choosing at least 2  with equal largest R  and with  both x and y
          <100.

                x     y     R
               13    84    85;        % Obtained from the list
               36    77    85;
               40    75    85;
               51    68    85;

               Choose 2 from the set of 4….(6). eg [a c] = [40 75] ;[b d] = [13 84]
               Using each choice iterate S (99->50) to find if F is integer.In
          this case
               I get 3 answers for ‘abcdSF’.
               Choose that whose S is maximum.
               The periphery = a+b+c+d.
               In my  program the answer is a 3 digit number with digits
          increasing consectutively.
               Diagonal difference = 7 miles.
               Run time = 17ms . PC using Pentium processor .Non Python.

               As a sideline the locations were found to form a cyclic quad as
          well as being
               ortho diagonal. ie ac + bd = S*F;
               Am I in the right ball park or do I start again?

                               Regards
                                      A.T.Sutherland.

          Like

          • Jim Randell's avatar

            Jim Randell 2:41 pm on 21 November 2025 Permalink | Reply

            @Alex:

            I also used the condition a^2 + c^2 = b^2 + d^2 to find candidate orthodiagonal quadrilaterals (my program is [ here ]).

            Although I did not assume that the actual value of the sums must be a perfect square (and so form a Pythagorean triple), as this is not true in general (e.g. 1^2 + 8^2 = 4^2 + 7^2 = 65, which is not a perfect square), and I wanted to make sure I found all candidate arrangements.

            But, if you do assume this, you can still find all 11 possible candidate orthodiagonal quadrilaterals with different 2-digit sides (or 12 if you count a solution that has the same sides as one of the other candidates, but a smaller AS diagonal) that do not have any three of the vertices collinear. And one of these is the solution to the puzzle.

            Four of the 11 candidate quadrilaterals are convex and cyclic as well as orthodiagonal, and for these the intersection of the diagonals cuts each of the diagonals into 2 integer lengths, so they can be composed from 4 Pythagorean triangles.

            However, there are candidate solutions where three of the vertices are collinear, that are not found if you only use Pythagorean triples to construct opposite sides).

            I will post some additional notes on my solution on Sunday (on the page for Teaser 3295).

            Like

  • Unknown's avatar

    Jim Randell 7:08 am on 14 September 2025 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3286: Water stop 

    From The Sunday Times, 14th September 2025 [link] [link]

    Chuck and his brother live on a long straight road that runs from west to east through their ranches. Chuck’s ranch is 13 km west of his brother’s. The two brothers often go from one ranch to the other on horseback, but go via a nearby river so that their horses may be watered. The shortest route via the river consists of two straight sections, one being 11 km longer than the other. The point at which they reach the river is 6 km north of the road.

    What is the total length of the route between the ranches that goes via the river?

    [teaser3286]

     
    • Jim Randell's avatar

      Jim Randell 7:26 am on 14 September 2025 Permalink | Reply

      Solving a couple of simultaneous quadratic equations gives an unlikely looking answer:

      Suppose the the ranches are at C and B, and the water is at W, 6 km north of a point X on the road.

      (We can assume the distance BW is greater than CW, if it is not the situation is a reflection of this).

      Then we have two right angled triangles:

      CXW: horizontal = y; vertical = 6; hypotenuse = x
      BXW: horizontal = 13 − y; vertical = 6; hypotenuse = x + 11

      And the required answer is the sum of the two hypotenuses (= 2x + 11).

      This then gives rise to two equations:

      CXW: x² = y² + 6²
      BXW: (x + 11)² = (13 − y)² + 6²

      The equations can be solved manually, but here is a program that uses a numerical solver.

      This Python program runs in 70ms. (Internal runtime is 145µs).

      from enigma import (hypot, find_zero, printf)
      
      # calculate values for x from each triangle
      fx1 = lambda y: hypot(y, 6)
      fx2 = lambda y: hypot(13 - y, 6) - 11
      
      # calculate values of x from each triangle
      # and return the difference
      f = lambda y: fx1(y) - fx2(y)
      
      # find solutions when the difference is zero
      r = find_zero(f, -100, 100)
      y = r.v
      x = fx1(y)
      d = x + (x + 11)
      printf("d={d:.3f} [x={x:.3f} y={y:.3f}]")
      

      Solution: The total length of the route via the river is 26 km.

      The river is 7.5 km from one ranch, and 18.5 km from the other. So the total journey is twice as far as following the road.

      Or we can mirror the diagram (so that X is 4.5 km beyond B) to give a second scenario:


      I think the puzzle text would have been less confusing if the brothers had just met for a picnic at W. Each travelling via a straight track from their respective ranch; one travelling 11 km further than the other. What was the total distance to the picnic spot travelled by the brothers?

      Like

      • Jim Randell's avatar

        Jim Randell 10:22 am on 14 September 2025 Permalink | Reply

        Or a similar approach using 2D geometry routines from enigma.py:

        from enigma import (point_dist, find_values, printf)
        
        # positions for C and B
        (C, B) = ((0, 0), (13, 0))
        # and the river is at W = (x, 6)
        
        # calculate difference between distances CW, BW
        def f(x):
          W = (x, 6)
          return abs(point_dist(C, W) - point_dist(B, W))
        
        # find solutions when the difference is 11
        for r in find_values(f, 11, -100, 100):
          x = r.v
          W = (x, 6)
          (d1, d2) = (point_dist(C, W), point_dist(B, W))
          d = d1 + d2
          printf("d={d:.3f} [W=({x:.3f}, 6); d1={d1:.3f} d2={d2:.3f}]")
        

        Like

      • Jim Randell's avatar

        Jim Randell 1:20 pm on 14 September 2025 Permalink | Reply

        And here is an exact solution, that uses the [[ Polynomial ]] class from the enigma.py library, to derive a quadratic equation, which can then be solved to give the required answer.

        from enigma import (Rational, Polynomial, sq, printf)
        
        Q = Rational()
        q12 = Q(1, 2)  # q12 = 0.5 will also work
        
        # calculate area^2 of the triangle using: (1/2) base . height
        A2 = sq(q12 * 13 * 6)
        
        # sides of the triangle (as polynomials)
        (a, b, c) = (Polynomial("x"), Polynomial("x + 11"), 13)
        
        # polynomial for area^2 of the triangle using Heron's formula
        s = (a + b + c) * q12
        p = s * (s - a) * (s - b) * (s - c)
        
        # find solutions of p(x) = A2 for positive x
        for x in p.roots(A2, domain='F', include='+'):
          # calculate total distance
          d = x + (x + 11)
          printf("d={d} [x={x}]")
        

        The program determines that the required solution is derived from the positive solution of the following quadratic equation (which it then solves):

        12x² + 132x − 144 = 1521

        (2x − 15)(2x + 37) = 0

        x = 7.5

        Liked by 1 person

    • Ruud's avatar

      Ruud 10:11 am on 14 September 2025 Permalink | Reply

      @Jim
      I don’t know why you say that you get an unlikely answer.
      The negative y just means that the point W is west of C (or east of B). And then it all fits.

      I have the following solution:

      import sympy as sp
      
      l = sp.symbols("l", real=True)
      eq = sp.Eq(sp.sqrt(((l + 11) / 2) ** 2 - 36) - 13, sp.sqrt(((l - 11) / 2) ** 2 - 36))
      print(sp.solveset(eq, l, domain=sp.S.Reals))
      

      Liked by 1 person

      • Jim Randell's avatar

        Jim Randell 11:43 am on 14 September 2025 Permalink | Reply

        @ruud: I said it looks unlikely, because the puzzle text can be read to imply that the brothers do not follow the road because the horses would have to go for 13 km without water.

        Like

        • Ruud's avatar

          Ruud 11:59 am on 14 September 2025 Permalink | Reply

          I didn’t read it like that.

          Like

      • Ruud's avatar

        Ruud 3:41 pm on 14 September 2025 Permalink | Reply

        The advantage of sympy over enigma.find_zero is that sympy results in an exact answer, whereas find_zero is an approximation using a golden section search.
        But of courae, sympy can’t solve arbitary expressions.

        Like

        • Jim Randell's avatar

          Jim Randell 4:14 pm on 14 September 2025 Permalink | Reply

          @Ruud: True. Although if we substitute the answer found by my programs using [[ find_zero() ]] into the equations we see that they are indeed exact answers. And the code runs over 1000× faster than using SymPy.

          But I also wrote a program that gives an exact answer using the [[ Polynomial() ]] class. And it still runs many times faster than using SymPy. (It generates a quadratic equation, and then solves it using the quadratic formula).

          Like

          • Ruud's avatar

            Ruud 4:28 pm on 14 September 2025 Permalink | Reply

            Thanks for the clear explanation.

            Like

    • Alex T Sutherland's avatar

      Alex T Sutherland 3:45 pm on 17 September 2025 Permalink | Reply

      Problem Solution:-    Using Cosine Rule and Quadratic Equation. 
      Triangle:-            Obtuse. Sides 'a' , 'b' = 'a'+11, & 13.
      Method:-              Solve for side 'a' using the Cosine Rule.
                    ie      b^2 =      [a^2 + 13^2 - 2*a*13*cos(B)]; B =angle oppsite side 'b'.
                            (a+11)^2 = [    "                                                             ];.........(1)
      
                            -cos(B) is determined in terms of 'a' from the small 
                             right angled triangle.
      
                             -cos(B) = sqrt(1- (6/a)^2);                                 ;........(2)
                              
                             From (1) & (2) integer coefficients (m n p) can be
                             determined for the qudratic m*(a*a) + n*a + p = 0;
                             Solve the quadratic for 'a'. May use a roots function
                             or the standard equation.
      
      Problem Answer:-       2*a + 11;
      
      Time:-                 The following were those obtained  from a 15+ years old PC.  
                                         (Running Non Python).
      
      Elapsed time is 0.007039 seconds.    Jim Randell's initial solution.
      
      Elapsed time is 0.000216 seconds.    Above method using a roots solver.
      
      Elapsed time is 0.000102 seconds.    Above method using the standard equation. 
      
      Code length:-         1 line; Maybe 2 in specifing the coefficients.           
      
      SideLine:-            The sum of the digits in the coefficients is 1 more 
                                              than the problem answer.
      

      Like

  • Unknown's avatar

    Jim Randell 6:41 am on 6 July 2025 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3276: First and last multiple 

    From The Sunday Times, 6th July 2025 [link] [link]

    Johann enjoys playing with numbers and making up numerical challenges for his elder brother Jacob. He has worked out a new challenge, which involves Jacob trying to find the whole-number square root of a six-digit number. He explained that the sum of the individual digits [of the six-digit number] is exactly five times the sum of its first and last digits. To make it easier, he tells him that no number is repeated in the six digits, there are no zeros, and the last three digits are in descending numerical order.

    What is the square root of the six digit number?

    [teaser3276]

     
    • Jim Randell's avatar

      Jim Randell 6:48 am on 6 July 2025 Permalink | Reply

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

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

      Run: [ @codepad ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # sqrt(ABCDEF) = XYZ
      --distinct="ABCDEF"
      --invalid="0,ABCDEFXZ"
      --answer="XYZ"
      
      # XYZ is the square root of ABCDEF
      "sq(XYZ) = ABCDEF"
      
      # the sum of the digits of the square is 5 times the
      # sum of the first and last digit
      "A + B + C + D + E + F == 5 * (A + F)"
      
      # the final three digits are in descending order
      "D > E > F"
      
      # [optional] performance tweaks
      --reorder="[1]"
      --invalid="1|2,X"
      

      Solution: The square root is 661.

      And so the 6-digit number is: 661^2 = 436921.

      And we have:

      4 + 3 + 6 + 9 + 2 + 1 = 25 = 5 × (4 + 1)
      9 > 2 > 1

      Like

    • GeoffR's avatar

      GeoffR 10:17 am on 6 July 2025 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:a; var 1..9:b; var 1..9:c; var 1..9:d;
      var 1..9:e; var 1..9:f; 
      var 316..999:ans; % square root of abcdef
      
      var 100000..999999: abcdef == 100000*a + 10000*b 
      + 1000*c + 100*d + 10*e + f;
      
      constraint all_different([a, b, c, d, e, f]);
      
      constraint a + b + c + d + e + f == 5 * (a + f);
      constraint d > e /\ e  > f;
      
      predicate is_sq(var int: c) =
         let {
            var 0..ceil(pow(int2float(ub(c)),(1/2))): z
         } in z*z = c;
      
      constraint ans * ans == abcdef;
      constraint is_sq(abcdef);
      
      solve satisfy;
      
      output["Square root of the six digit number = " ++  show(ans)];
      
      
      

      Like

    • Frits's avatar

      Frits 3:03 pm on 6 July 2025 Permalink | Reply

      # last 2 digits y and z  (abcdef = xyz^2)
      last2 = set(i for i in range(11, 100) 
                  if i % 10 and 9 < (m := (i * i) % 100) < 90 and m // 10 > m % 10)
      
      for yz in last2:
        # A + F <= 7 so X < 9
        for x in range(3, 9):
          xyz = 100 * x + yz
          abcdef = xyz * xyz
          if len(set(s := str(abcdef))) != 6: continue
          if s[3] <= s[4] or "0" in s: continue
          dgts6 = [int(x) for x in s]
          if sum(dgts6) != 5 * (dgts6[0] + dgts6[-1]): continue
      
          print("answer:", xyz)
      

      Like

      • Frits's avatar

        Frits 5:57 pm on 6 July 2025 Permalink | Reply

        Processing six-digit numbers to find a valid square root.

        from enigma import is_square
        
        # last 2 digits e and f  (abcdef = xyz^2)
        last2 = set(divmod(m, 10) for i in range(11, 100) 
                    if i % 10 and 9 < (m := (i * i) % 100) < 90 and m // 10 > m % 10)
        for (e, f) in last2:
          ef = 10 * e + f
          for d in range(e + 1, 10):
            _def = 100 * d + ef
            # 21 <= 5 * (a + f) <= 39  or  4 < a + f < 8
            for a in set(range(max(1, 5 - f), 8 - f))- {d, e, f}:
              # remaining for b + c
              if not (3 <= (bc := 5 * (a + f) - (a + d + e + f)) <= 17): continue
              adef = 10**5 * a + _def
              # determine missing numbers x and y (x + y = bc with x < y)
              for x in set(range(max(1, bc - 9), (bc + 1) // 2)) - {a, d, e, f}:
                if (y := bc - x) in {a, x, d, e, f}: continue
                for b, c in ((x, y), (y, x)):
                  n = adef + 10**4 * b + 10**3 * c
                  if (xyz := is_square(n)):
                    print("answer:", xyz)
        

        Like

    • Ruud's avatar

      Ruud 4:22 pm on 6 July 2025 Permalink | Reply

      import math
      import istr
      
      for i in range(int(math.sqrt(100_000)), int(math.sqrt(1_000_000))):
          if (sum((sq := istr(i * i))) == 5 * (sq[0] + sq[-1])) and sq.all_distinct() and "0" not in sq and sq[-3] > sq[-2] > sq[-1]:
              print(sq, i)
      

      Like

    • GeoffR's avatar

      GeoffR 9:17 am on 9 July 2025 Permalink | Reply

      sq6 = [ n**2 for n in range(317, 1000)    
              if len(set(str(n**2))) == 6 ]
      
      for num in sq6:
        ds = str(num)
        if '0' in ds: continue
        dig = [int(x) for  x in ds]
        if (dig [3] > dig[4] > dig[5]):
          if sum(dig[:6]) == 5 * (dig[0] + dig[5]):
            print (f"Square root is {int(num ** 0.5)}.")
      
      

      Like

  • Unknown's avatar

    Jim Randell 7:12 am on 25 May 2025 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3270: Tunnel vision 

    From The Sunday Times, 25th May 2025 [link] [link]

    Four ramblers came to a tunnel that they all had to travel through. The tunnel was too dangerous to travel through without a torch, and unfortunately they only had one torch. It was also too narrow to walk through more than two at a time. The maximum walking speed of each of the walkers was such that they could walk through the tunnel in an exact number of minutes, less than ten, which was different for each walker. When two walkers walked together, they would walk at the speed of the slower one.

    They all managed to get through the tunnel and in the quickest possible time, this time being five sixths of the total of their individual crossing times.

    In ascending order, what are their four four individual crossing times?

    [teaser3270]

     
    • Jim Randell's avatar

      Jim Randell 7:34 am on 25 May 2025 Permalink | Reply

      See also: Enigma 981, [@wikipedia].

      This Python program runs in 63ms. (Internal runtime is 1.8ms).

      from enigma import (Accumulator, irange, subsets, div, cache, printf)
      
      # find minimum total crossing times for individual times <ts> (all different)
      # where <xs> is the times of the participants on the far side
      @cache
      def _time(ts, xs):
        # 1 or 2 people take the max of the times
        if len(ts) < 3: return max(ts)
        # otherwise, find minimal time for 2 to cross (x, y) and 1 to return (z)
        r = Accumulator(fn=min)
        for xy in subsets(ts, size=2):
          for z in xs.union(xy):
            # minimise the remaining scenario
            t = _time(ts.difference(xy).union({z}), xs.union(xy).difference({z}))
            r.accumulate(max(xy) + z + t)
        return r.value
      time = lambda ts, xs=(): _time(frozenset(ts), frozenset(xs))
      
      # choose 4 individual crossing times; all different and <10 minutes
      for ts in subsets(irange(1, 9), size=4):
        # target time is 5/6 the sum of the individual times
        t = div(5 * sum(ts), 6)
        if t is None or time(ts) != t: continue
        # output solution
        printf("{ts} -> {t}")
      

      Solution: The individual crossing times are: 1, 2, 7, 8 minutes.

      The total of the individual crossing times is 18 minutes.

      And the minimum crossing time is 15 minutes (15 = 18 × 5/6), for example:

      t=0: 1+2 cross (2 min) {1, 2}
      t=2: 1 returns (1 min) {2}
      t=3: 7+8 cross (8 min) {2, 7, 8}
      t=11: 2 returns (2 min) {7, 8}
      t=13: 1+2 cross (2 min) {1, 2, 7, 8}
      t=15: crossing complete

      Like

      • Jim Randell's avatar

        Jim Randell 1:48 pm on 27 May 2025 Permalink | Reply

        I experimented further with this puzzle.

        Here is a modified version of my program which will produce a minimal sequence of crossings, and is also modified to use [[ multiset ]] instead of [[ set ]], which allows individual crossing times to be repeated:

        from enigma import (Accumulator, multiset, irange, subsets, div, printf)
        
        # find minimum total crossing times for individual times <ts>
        # where <xs> is the times of the participants on the far side
        def _time(ts, xs, ss):
          # 1 or 2 people take the max of the times
          if ts.size() < 3: return (ts.max(), ss + [list(ts.sorted())])
          # otherwise, find minimal time for 2 to cross (x, y) and 1 to return (z)
          r = Accumulator(fn=min)
          for xy in ts.subsets(size=2):
            for z in xs.combine(xy):
              # minimise the remaining scenario
              (t, ss_) = _time(ts.difference(xy).add(z), xs.combine(xy).remove(z), ss + [list(xy.sorted()), [z]])
              r.accumulate_data(xy.max() + z + t, ss_)
          return (r.value, r.data)
        time = lambda ts, xs=(): _time(multiset(ts), multiset(xs), list())
        
        # choose 4 individual crossing times
        for ts in subsets(irange(1, 9), size=4, select='C'):
          # target time is 5/6 the sum of the individual times
          t = div(5 * sum(ts), 6)
          if t is None: continue
          (t_, ss) = time(ts)
          if t_ != t: continue
          # output solution
          printf("{ts} -> {t} {ss}")
        

        We find there are 2 further solutions if repeated individual crossing times are allowed.

        And the program can also be used to find solutions for other variations of the puzzle, for example, where there are 5 participants, all with different crossing times less than 12.

        [Solutions below.]


        If repeated crossing times are allowed in the original puzzle (use [[ select='R' in line 19), the following scenarios are also solutions to the puzzle:

        (1, 1, 4, 6) → 10 [[1, 1], [1], [4, 6], [1], [1, 1]]
        (2, 2, 7, 7) → 15 [[2, 2], [2], [7, 7], [2], [2, 2]]

        And if we extend the puzzle to 5 participants (with different individual crossing times less than 12 minutes):

        (1, 2, 6, 10, 11) → 25 [[1, 6], [1], [1, 2], [1], [10, 11], [2], [1, 2]]

        Like

    • Frits's avatar

      Frits 2:49 pm on 26 May 2025 Permalink | Reply

      Only using analysis for the multiple of 6.

      from itertools import combinations
      
      # decompose the integer <t> into <k> increasing
      # numbers between mn and mx (inclusive)
      def decompose(t, k=4, mn=1, mx=9, vs=[]):
        if k == 1:
          if vs[-1] < t <= mx:
            yield set(vs + [t])
        else:
          for n in range(mn, mx + 1):
            if 2 * k * n + k * (k - 1) > 2 * t:
              break
            yield from decompose(t - n, k - 1, n + 1, mx, vs + [n])
      
      # get all four ramblers through the tunnel from a to b
      def solve(a, b=set(), e=0, ss=[], t=0): 
        global quickest
        if len(a) == 2 and not e: # penultimate stage
          quickest = min(quickest, t + max(a)) 
        else:
          if e: # we are at the end of the tunnel
            for c in combinations(b, 1):
              if (t_ := t + c[0]) < quickest:
                solve(a | set(c), b.difference(c), 0, ss + [c], t_)
          else: # we are at the start of the tunnel   
            for c in combinations(a, 2):
              if (t_ := t + max(c)) < quickest:
                solve(a.difference(c), b  | set(c), 1, ss + [c], t_)
      
      # total of their individual crossing times <ti> must be a multiple of 6
      # to get to five sixths
      for ti in range(12, 31, 6):
        # choose times for the four ramblers (with sum <ti>)
        for t4 in decompose(ti):
          quickest = 999
          # get the quickest possible time for these four times
          solve(t4)
          # five sixths?
          if 6 * quickest == 5 * ti:
            print(f"answer: {sorted(t4)}")
      

      or faster

      from itertools import combinations, permutations
      from collections import defaultdict
      
      # assume a and e are walking back times (may have same value) 
      # b, c, d and f must have different values
      
      # 1: (a, b)  2: a  3: (c, d)  4: e  5: (e, f)
      dct = defaultdict(lambda: 45) # default value 45
      dgts = set(range(1, 10))
      for c, d in combinations(range(1, 10), 2):
        for b, f in permutations(dgts - {c, d}, 2):
          # total of their individual crossing times must be 
          # a multiple of 6 to get to five sixths
          if (b + c + d + f) % 6 == 0: 
            # go for quickest possible time
            a, e = min(c, f), min(b, c) 
            # store the quickest possible time
            t = max(a, b) + a + d + e + max(e, f)
            t4 = tuple(sorted([b, c, d, f]))
            dct[t4] = min(dct[t4], t)
      
      for k, v in dct.items():
        # five sixths of the total of their individual crossing times
        if 5 * sum(k) == 6 * v:
          print(f"answer: {k}") 
      

      Like

  • Unknown's avatar

    Jim Randell 1:03 am on 2 March 2025 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3258: On grid 

    From The Sunday Times, 2nd March 2025 [link] [link]

    Using all the digits 1 to 9 in a 3 by 3 grid, I have devised a game. In this grid, if each of the three rows, three columns and two diagonals are read both forwards and backwards, there are 16 three-digit numbers.

    Points are awarded to each of these three-digit numbers; with 1 point awarded if it’s a prime number, 3 points if it’s a perfect square, 6 points if a perfect cube; with the points being cumulative if more than one applies.

    What is the highest number of points that can be awarded?

    [teaser3258]

     
    • Jim Randell's avatar

      Jim Randell 1:27 am on 2 March 2025 Permalink | Reply

      Here’s a brute force solution.

      It runs in 177ms (using PyPy).

      from enigma import (
        defaultdict, Accumulator, primes, powers, nsplit, irange, subsets, rev, printf
      )
      
      # points for 3-digit primes, squares, cubes
      cats = [
        (primes.between(100, 999), 1),  # prime -> +1
        (powers(10, 31, 2), 3),  # square -> +3
        (powers(5, 9, 3), 6),  # cube -> +6
      ]
      # collect points for 3-digit sequences, in both directions
      pts = defaultdict(int)
      for (ns, p) in cats:
        for n in ns:
          ds = nsplit(n)
          if len(set(ds)) < len(ds): continue
          pts[ds] += p
          pts[rev(ds)] += p
      
      # find maximal grids
      r = Accumulator(fn=max, collect=1)
      for ss in subsets(irange(1, 9), size=len, select='P'):
        (A, B, C, D, E, F, G, H, I) = ss
        # eliminate repeated solutions
        if not (A < C and A < G and A < I and B < D): continue
        # score this grid
        p = sum(pts.get(k, 0) for k in [
          (A, B, C), (D, E, F), (G, H, I),  # rows
          (A, D, G), (B, E, H), (C, F, I),  # columns
          (A, E, I), (C, E, G),  # diagonals
        ])
        r.accumulate_data(p, ss)
      
      # output solution(s)
      printf("max points = {r.value} [from {r.count} grids]")
      for (A, B, C, D, E, F, G, H, I) in r.data:
        printf("-> [ {A} {B} {C} | {D} {E} {F} | {G} {H} {I} ]")
      

      Solution: The maximum possible points total is: 27.

      Here is a grid that scores 27:

      The scoring numbers are:

      137 is prime → +1
      169 = 13^2 → +3
      961 = 31^2 → +3
      324 = 18^2 → +3
      587 is prime → +1
      125 = 5^3 → +6
      521 is prime → +1
      729 = 27^2 = 9^3 → +9
      total = 27

      As the numbers are read in both directions this grid can be rotated and reflected to give 7 additional grids using the same numbers.

      These can be seen by removing the check at line 25 from the program.

      Like

    • Frits's avatar

      Frits 1:22 pm on 2 March 2025 Permalink | Reply

      from enigma import SubstitutedExpression
      from itertools import permutations
      
      # determine valid primes 123 - 987
      P = {3, 5, 7}
      P |= {n for n in range(11, 100, 2) if all(n % p for p in P)}
      P = {n for n in range(123, 988, 2) if all(n % p for p in P) and
           len(set(str(n))) == 3}
           
      sqs = {sq for n in range(10, 32) if len(set(str(sq := n * n))) == 3}
      cbs = {cb for n in range(5, 10) if len(set(str(cb := n * n * n))) == 3}
      
      # make dictionary of points per number
      d = {(n := int(''.join(p))): 1 
           if n in P else 3 if n in sqs else 6 if n in cbs else 0 
           for p in permutations("123456789", 3)}
           
      # check numbers both square and cube        
      for c in cbs:
        if c in sqs:
          d[c] = 9  
      
      # return points for number <n>
      pts = lambda n: d[n]
          
      rows = "ABC DEF GHI".split()
      cols = list(''.join(x) for x in zip(*rows))
      diags = ["AEI", "CEG"]
      vars = rows + cols + diags
      vars += [v[::-1] for v in vars]
      ans = ' + '.join(f"pts({v})" for v in vars)
      
      exprs = []
      # avoid rotations, reflections etc
      exprs.append("A < C")  
      exprs.append("A < G")   
      exprs.append("A < I")  
      exprs.append("B < D") 
      # calculate one of the variables
      exprs.append("45 - (A + B + C + D + E + F + G + I) = H") 
        
      # the alphametic puzzle
      p = SubstitutedExpression(
        exprs,
        answer="@ans, (ABC, DEF, GHI)",
        macro=dict([("ans", ans)]),
        d2i=dict([(1, "CDGI")] +
                 [(k, "A") for k in range(7, 9)] +
                 [(9, "AB")]),
        env=dict(pts=pts),
        digits=range(1, 10),
        verbose=0,    # use 256 to see the generated code
      ) 
      
      mx, sols = 0, []
      # collect answers
      for t, m in sorted(p.answers(), reverse=True):
        if mx and t != mx: break
        sols.append(m)
        mx = t
        
      print("answer:", mx)
      print()
      print("Example(s):")
      # print examples
      for s in sols:
        print()
        print('\n'.join(str(x) for x in s))  
      

      Like

    • Ruud's avatar

      Ruud 7:41 pm on 2 March 2025 Permalink | Reply

      Even more brute force:

      import istr
      
      
      def is_square(n):
          square_root = int(n) ** (1.0 / 2.0)
          return round(square_root) ** 2 == n
      
      
      def is_cube(n):
          cube_root = int(n) ** (1.0 / 3.0)
          return round(cube_root) ** 3 == n
      
      
      max_score = 0
      
      for a, b, c, d, e, f, g, h, i in istr.permutations(istr.digits("1-9")):
          total = 0
          for n in (a | b | c, d | e | f, g | h | i, a | d | g, b | e | h, c | f | i, a | e | i, c | e | g):
              for m in n, n[::-1]:
                  total += m.is_prime() + 3 * is_square(m) + 6 * is_cube(m)
          max_score = max(max_score, total)
      
      print(max_score)
      

      Liked by 1 person

    • Frits's avatar

      Frits 6:11 am on 4 March 2025 Permalink | Reply

      Using Jim’s trick of also storing the points of the reversed entry.

      from itertools import permutations
      
      # determine valid primes 123 - 987
      P = {3, 5, 7}
      P |= {n for n in range(11, 100, 2) if all(n % p for p in P)}
      P = {str(n) for n in range(123, 988, 2) if all(n % p for p in P)}
           
      sqs = {str(n * n) for n in range(10, 32)}
      cbs = {str(n * n * n) for n in range(5, 10)}
      
      # make dictionary of points per three-digits tuple
      d = {tuple(int(x) for x in p): 1 
           if (s := ''.join(p)) in P else 3 if s in sqs else 6 if s in cbs else 0 
           for p in permutations("123456789", 3)}
                
      # check numbers both square and cube        
      for c in cbs:
        if c in sqs:
          d[tuple(int(x) for x in c)] =  9  
          
      # let every entry also contain the points of the reversed entry 
      d = {k: v + d[k[::-1]] for k, v in d.items()}
      
      # return points for sequence of three digits <s>
      pts = lambda s: d[s]
      
      alldgts = set(range(1, 10))
      sols, mx = [], 0
      
      # A B C
      # D E F
      # G H I
          
      for A in range(1, 7):
        # eliminate repeated solutions
        for C, G, I in permutations(range(A + 1, 10), 3):
          r5 = alldgts - {A, C, G, I}
          for B in r5 - {9}:  # B < D
            r4 = r5 - {B}
            p4 = pts((A, B, C))
            for D in [x for x in r4 if x > B]:
              p3 = p4 + pts((A, D, G))
              for E, F, H in permutations(r4 - {D}):
                p0 = (p3 + pts((D, E, F)) + pts((G, H, I)) + pts((B, E, H)) + 
                           pts((C, F, I)) + pts((A, E, I)) + pts((C, E, G))) 
                if p0 >= mx:
                  if p0 > mx:
                    sols = []
                    mx = p0
                  sols.append([(A, B, C), (D, E, F), (G, H, I)])
                
      print("answer:", mx)
      print()
      print("Example(s):")
      # print examples
      for s in sols:
        print()
        print('\n'.join(str(x) for x in s))  
      

      Like

  • Unknown's avatar

    Jim Randell 7:00 am on 12 January 2025 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3251: Number test 

    From The Sunday Times, 12th January 2025 [link] [link]

    I asked my daughter to find as many three-digit numbers as she could, each of which had the property that the number equalled the sum of the cubes of its individual digits. If she only found one such number, I asked her to give me this number — otherwise, if she had found more than one, to give me the sum of all such numbers found.

    She gave me a prime number, from which I could see that not all answers had been found.

    Which number or numbers did she not find?

    [teaser3251]

     
    • Jim Randell's avatar

      Jim Randell 7:07 am on 12 January 2025 Permalink | Reply

      It is straightforward to test all 3-digit numbers for the required property, and then look for (proper) subsets of the numbers found, to find a subset with a prime sum.

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

      from enigma import (irange, nsplit, subsets, is_prime, diff, printf)
      
      # find 3-digit numbers that are the sum of the cube of their digits
      cb = list(d**3 for d in irange(0, 9))
      ns = list(n for n in irange(100, 999) if n == sum(cb[d] for d in nsplit(n)))
      printf("numbers = {ns}")
      
      # find (proper) subsets that sum to a prime
      for ss in subsets(ns, min_size=1, max_size=len(ns) - 1):
        t = sum(ss)
        if not is_prime(t): continue
        # output solution
        missing = diff(ns, ss)
        printf("sum{ss} = {t}; missing = {missing}")
      

      Solution: The numbers not found are: 371, 407.

      There are only four such numbers (if leading zeros are disallowed):

      153, 370, 371, 407

      And the only strict subset of these with a prime sum is:

      153 + 370 = 523

      If all four numbers had been found, the sum would also have been prime:

      153 + 370 + 371 + 407 = 1301

      Like

    • Frits's avatar

      Frits 2:56 pm on 12 January 2025 Permalink | Reply

      from itertools import combinations
      
      def is_prime(n):            
        if n < 4:
          return n > 1
        if n % 2 == 0 or n % 3 == 0:
          return False
      
        # all primes > 3 are of the form 6n +/- 1
        # start with f=5 (which is prime) and test f, f+2 for being prime
        f, r = 5, int(n**0.5)
        while f <= r:
          if n % f == 0: return False
          if n % (f + 2) == 0: return False
          f += 6
      
        return True
      
      nums = []
      for a in range(1, 10):
        a3 = a * a * a
        for b in range(10):
          a3b3 = a3 + b * b * b
          for c in range(10):
            t = a3b3 + c * c * c
            if t // 100 != a: continue
            if t % 10 != c: continue
            if (t % 100) // 10 != b: continue
            nums += [t]   
      sum_nums = sum(nums)
      
      print("answer(s):")
      for k in range(1, len(nums)):
        # pick <k> numbers from <ns> she has missed
        for s in combinations(nums, k):
          # she gave me a prime number
          if is_prime(sum_nums - sum(s)):
            print(s)
      

      Like

    • ruudvanderham's avatar

      ruudvanderham 12:09 pm on 13 January 2025 Permalink | Reply

      Rather straightforward:

      import istr
      
      istr.repr_mode("str")
      
      solutions = {i for i in istr(range(100, 1000)) if sum(digit**3 for digit in i) == i}
      print(*list(f"missing: {solutions - set(x)}" for r in range(1, len(solutions)) for x in istr.combinations(solutions, r=r) if sum(x).is_prime()))

      Like

  • Unknown's avatar

    Jim Randell 6:57 am on 3 November 2024 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3241: Users pay 

    From The Sunday Times, 3rd November 2024 [link] [link]

    I live in a cul-de-sac which had planning permission for building on ten identical plots along the whole length of one side of the road. The developer started building, and numbered the properties, from the closed end. The plots aren’t all finished, and the cost of surfacing the whole road has to be paid by the owners of the completed properties. It was decided that the owners would only contribute to the cost of the road leading to their property, so the owner of number 1 pays for the road section in front of their property, the cost of the section outside number 2 is shared equally between numbers 1 and 2, and so on.

    My contribution is £ 1,000, while that of another homeowner is £ 3,800.

    What is my house number and how many houses have been built?

    [teaser3241]

     
    • Hugo's avatar

      Hugo 7:18 am on 3 November 2024 Permalink | Reply

      This doesn’t appear to make sense. If the houses are numbered from the closed end, one would expect the owner of no. 1 to have to pay the highest contribution, since he is furthest from the point of access to the road.

      Like

      • Jim Randell's avatar

        Jim Randell 8:16 am on 3 November 2024 Permalink | Reply

        I think the way it works is as follows:

        If 3 houses were built, then:

        road section #1 is paid for by house #1
        road section #2 is paid for by houses #1, #2 (half each)
        road sections #3..#10 are paid for by houses #1, #2, #3 (one third each)

        So house #1 pays the most, then #2 and then #3, and the entire cost of the road is covered.

        Like

    • Jim Randell's avatar

      Jim Randell 7:52 am on 3 November 2024 Permalink | Reply

      It took me a couple of attempts to work out how this puzzle is meant to work. I assumed the houses are built in numerical order starting at #1.

      This Python program runs in 70ms. (Internal runtime is 537µs).

      from enigma import (Rational, irange, subsets, printf)
      
      Q = Rational()
      
      # consider total number of houses built
      for n in irange(1, 10):
      
        # accumulate total cost (in sections) for each house
        cost = dict((i, 0) for i in irange(1, n))
        # allocate costs for each section
        for k in irange(1, 10):
          m = min(k, n)
          for i in irange(1, m):
            cost[i] += Q(1, m)
      
        # look for one cost which is 3.8x another
        for (a, b) in subsets(sorted(cost.keys()), size=2):
          if 10 * cost[a] == 38 * cost[b]:
            printf("n={n} -> a={a} b={b}")
      

      Solution: 8 houses have been built. The setters house is #7.

      The cost of the ten sections of road is distributed among the 8 houses as follows:

      #1: 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 831/280
      #2: 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 551/280
      #3: 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 411/280
      #4: 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 953/840
      #5: 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 743/840
      #6: 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 115/168
      #7: 1/7 + 1/8 + 1/8 + 1/8 = 29/56
      #8: 1/8 + 1/8 + 1/8 = 3/8

      The setter (at house #7) pays £1000, so the actual costs are:

      #1: £ 5731.03
      #2: £ 3800.00
      #3: £ 2834.48
      #4: £ 2190.80
      #5: £ 1708.05
      #6: £ 1321.84
      #7: £ 1000.00
      #8: £ 724.14

      So it is the occupant of house #2 who has to pay £ 3800.

      And the total cost of the road is £ 19310.35.

      Like

  • Unknown's avatar

    Jim Randell 5:35 am on 18 August 2024 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3230: Polytunnel 

    From The Sunday Times, 18th August 2024 [link] [link]

    I have extended my market garden by the addition of a polytunnel. The polyethylene cover is supported at intervals by identical sets of three vertical pillars supporting metal arcs, of negligible thickness, resting on the level ground on both sides. In each set, the highest pillar is in the middle of the cross-section, at the highest point of the tunnel. The other two pillars are of equal height, being three quarters of the height of the central pillar. These shorter pillars are positioned on each side, 2/11 of the ground-level width of the tunnel from each edge.

    Each metal arc is part of a circle (less than a semicircle), and the highest point is exactly 3m above the ground.

    What is the ground-level width of the polytunnel in cm?

    [teaser3230]

     
    • Jim Randell's avatar

      Jim Randell 5:36 am on 18 August 2024 Permalink | Reply

      By considering two right-angled triangles we can derive a linear equation for the depth of the centre of the arc below ground level (x), from which the width of the polytunnel (2w) can be determined.

      The triangles are indicated in the following diagram:

      This Python program (appropriately enough) uses the [[ Polynomial() ]] class from the enigma.py library to perform the calculations.

      It runs in 76ms. (Internal runtime is 139µs).

      Run: [ @replit ]

      from enigma import (Rational, Polynomial, sq, sqrt, printf)
      
      Q = Rational()
      
      # suppose the polytunnel has ground-level semi-width w
      # and the centre of the circle is a distance x below ground
      # we have:
      #
      #  r = x + 300
      #  r^2 = w^2 + x^2
      #  r^2 = (7w/11)^2 + (225 + x)^2
      
      fx = Polynomial('x')  # depth of origin
      fr = fx + 300  # radius of arc
      
      f1 = sq(fr) - sq(fx)  # = w^2
      f2 = sq(fr) - sq(fx + 225)  # = (7w/11)^2
      
      f = sq(Q(7, 11)) * f1 - f2  # equate values of w^2
      
      # solve f(x) = 0 for positive real x
      for x in f.roots(domain='F', include='0+'):
        # calculate width
        W = sqrt(f1(x)) * 2
        printf("polytunnel width = {W:g} cm [x = {x:g}]")
      

      Solution: The width of the polytunnel at ground level is 660 cm.

      The polynomial to determine the depth of the centre of the circular arc simplifies to:

      f(x) = 2x − 63

      From which we easily find the depth of the centre and the radius of the circle:

      x = 31.5
      r = 331.5

      And from these we calculate the semi-width of the polytunnel:

      w^2 = r^2 − x^2 = (r + x)(r − x)
      w^2 = 363 × 300 = 108900
      ⇒ w = 330

      So the total width of the polytunnel is 660 cm.

      Like

    • Frits's avatar

      Frits 11:24 am on 18 August 2024 Permalink | Reply

      I made my narrowing down routine from scratch.
      Of course there are more efficient ways to do this (I don’t know them by heart).

      from sys import float_info
      eps = float_info.epsilon
      
      # r = x + 300    # the centre of the circle is a distance x below ground
      # 49.w^2 - 117600.x - 17_640_000 = 0
      # 49.w^2 -  72600.x - 19_057_500 = 0
      
      f1 = lambda x: 17_640_000 + 117_600 * x
      f2 = lambda x: 19_057_500 +  72_600 * x
      
      mode = ""
      x = 100         # choose an arbitrarily starting value
      delta = 5       # increment/decrement value for variable x
      
      # find a value for "x" where both f1(x) and f2(x) are (almost) the same
      while True:
        v1, v2 = f1(x), f2(x)
        # do we have an solution where both values are (almost) the same?
        if abs(v2 - v1) <= eps:
          w = (2_400 * x + 360_000)**.5
          print(f"answer:  ground-level width = {round(w, 2)} cm")
          break
        
        if v1 < v2:
          if mode == "more": 
            delta /= 2
          x += delta
          mode = "less"
        else:
          if mode == "less": 
            delta /= 2
          x -= delta
          mode = "more"     
      

      Like

      • Frits's avatar

        Frits 11:34 am on 18 August 2024 Permalink | Reply

        The program was only made if you don’t want to analyse the problem till a solution is found.

        Like

    • GeoffR's avatar

      GeoffR 6:23 pm on 18 August 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % X = half tunnel width, Y =  depth below ground, R = circle radius
      % All dustances in mm.
      
      % Assumed UB's for variables
      var 1..4500:R;  var 1..4000:X; var 1..1500:Y; 
      
      constraint R == 3000 + Y;  
      
      constraint X * X  + Y * Y == R * R;
       
      % (2250 + Y)^2 + (7/11 * X)^2 = R * R
      constraint 121 * R * R == 121 * ((2250 + Y) * (2250 + Y)) + (49 * X * X);
      
      solve satisfy;
      
      
      

      Like

  • Unknown's avatar

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

    Teaser 3219: Number funnel 

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

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

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

    What is the bottom total?

    [teaser3219]

     
    • Jim Randell's avatar

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

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

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

      Run: [ @replit ]

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

      Solution: The final total is 102.

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

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

      Like

      • Ruud's avatar

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

        This my version

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

        Like

      • NigelR's avatar

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

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

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

        Like

    • Jim Randell's avatar

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

      Here is a solution based on a bit of analysis:

      We have:

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

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

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

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

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

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

      We can address this manually, or programatically.

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

      Run: [ @replit ]

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

      Manually:

      We are looking to solve:

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

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

      This boils down to choosing two subsets such that:

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

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

      Otherwise we have:

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

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

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

      Like

      • Frits's avatar

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

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

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

        Like

        • Jim Randell's avatar

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

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

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

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

          Like

      • Frits's avatar

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

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

        Like

        • Jim Randell's avatar

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

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

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

          Like

        • Frits's avatar

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

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

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

          Like

          • Jim Randell's avatar

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

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

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

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

            Like

      • Jim Randell's avatar

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

        Or, using a single call to express():

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

        Like

    • Hugo's avatar

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

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

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

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

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

      Like

    • Hugo's avatar

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

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

      Like

    • GeoffR's avatar

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

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

      Like

    • GeoffR's avatar

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

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

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

      It worked well – poem below:

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

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

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

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

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

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

      Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 5 April 2024 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3211: Descendants’ ages 

    From The Sunday Times, 7th April 2024 [link] [link]

    I have three daughters and a grandson. They are all of different ages, with the eldest being younger than 35 years old, and my grandson being the youngest.

    Three years ago the square of the age of my eldest daughter was equal to the sum of the squares of the ages of the other three. In another three years’ time the sum of the square of the age of my eldest daughter plus the square of the age of my grandson will be equal to the sum of the squares of the ages of my other two daughters.

    In ascending order, what are their ages?

    [teaser3211]

     
    • Jim Randell's avatar

      Jim Randell 4:43 pm on 5 April 2024 Permalink | Reply

      A straightforward solution using the [[ SubstitutedExpression ]] solver from the enigma.py library:

      The following run file executes in 100ms. (Internal runtime of the generated program is 25.6ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      # suppose daughters are aged D, E, F, and the grandson G
      
      SubstitutedExpression
      
      # allow for ages from 0-34
      --base=35
      
      # ages in descending order
      "D > E" "E > F" "F > G"
      
      # 3 years ago ...
      "sq(D - 3) == sq(E - 3) + sq(F - 3) + sq(G - 3)"
      
      # 3 years time ...
      "sq(D + 3) + sq(G + 3) == sq(E + 3) + sq(F + 3)"
      
      # answer is ages in ascending order
      --answer="(G, F, E, D)"
      --template=""
      

      Solution: The ages are: 9, 24, 25, 34.

      Three years ago we have:

      31² = 961
      6² + 21² + 22² = 961

      and in three years time we have:

      37² + 12² = 1513
      27² + 28² = 1513

      The next smallest solution is with ages: 9, 21, 30, 36. Which explains why the age of the eldest daughter was limited to 34 (although the puzzle could have said “less than 36”, and still had a unique solution).

      Like

      • Jim Randell's avatar

        Jim Randell 6:14 pm on 5 April 2024 Permalink | Reply

        Or using less brute force:

        This Python program has an internal runtime of 1.4ms.

        Run: [ @replit ]

        from enigma import (irange, sum_of_squares, sq, printf)
        
        # consider possible ages for the eldest daughter
        for D in irange(34, 18, step=-1):
          # 3 years ago ...
          for (G, F, E) in sum_of_squares(sq(D - 3), 3, sep=1):
            (G, F, E) = (G + 3, F + 3, E + 3)
            # 3 years time ...
            if sq(D + 3) + sq(G + 3) == sq(E + 3) + sq(F + 3) and not (D - G < 15):
              # output solution
              printf("{G}, {F}, {E}, {D}")
        

        Liked by 1 person

        • Frits's avatar

          Frits 10:48 am on 6 April 2024 Permalink | Reply

          @Jim, please elaborate on the lower bound of variable D.

          NB Your first program seems to consider negative ages as well (3 years ago).

          Like

          • Jim Randell's avatar

            Jim Randell 11:57 am on 6 April 2024 Permalink | Reply

            My first program allows the full range of ages (including negative ages for the “3 years ago” case), as I wondered if the puzzle had an “unexpected” configuration. But this didn’t give any answers in the “unexpected” range, so for my second program I used a more normal interpretation, that the grandson has a non-negative age 3 years ago, and that at least the eldest daughter is old enough to be his mother. (I’ve now added a check to ensure this). Both programs find the same answer.

            Like

    • Frits's avatar

      Frits 5:03 pm on 5 April 2024 Permalink | Reply

        
      from itertools import combinations
        
      # pick 4 different squares for the situation of 3 years ago
      for sqG, sqD1, sqD2, sqE in combinations([i**2 for i in range(32)], 4):
        if sqE != sqG + sqD1 + sqD2: continue
        G, D1, D2, E = [int(x**.5) for x in [sqG, sqD1, sqD2, sqE]]
      
        # check the situation in 3 years time
        if (E + 6)**2 + (G + 6)**2 != (D1 + 6)**2 + (D2 + 6)**2: continue
        print("answer: ages", [G + 3, D1 + 3, D2 + 3, E + 3]) 
      

      Like

    • GeoffR's avatar

      GeoffR 10:36 am on 6 April 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Three daughters and one grandson
      var 1..34:D1; var 1..34:D2; var 1..34:D3; var 1..34:GS;
      
      constraint all_different([D1, D2, D3, GS]);
      
      % Make D1 the eldest daughter
      constraint D1 > D2 /\ D1 > D3 /\ D1 > GS;
      
      % My grandson is the youngest person
      % D2 can be less than D3, as on same side of the two equations
      constraint GS < D2 /\ GS < D3 /\ D2 < D3;
      
      % Three years ago the square of the age of my eldest daughter was equal to
      % the sum of the squares of the ages of the other three
      
      constraint (D1-3) * (D1-3) == (D2-3) * (D2-3) + (D3-3) * (D3-3) + (GS-3) * (GS-3);
      
      % However, in three years time..
      constraint (D1+3) * (D1+3) + (GS+3) * (GS+3) == (D2+3) * (D2+3) + (D3+3) * (D3+3);
      
      solve satisfy;
      
      output ["[GS, D2, D3, D1] = " ++ show([GS, D2, D3, D1])];
      

      Like

    • GeoffR's avatar

      GeoffR 4:16 pm on 6 April 2024 Permalink | Reply

      This teaser only gives a unique answer with an upper age limit of less than 35. If this upper age limit is increased. there are other values which satisfy the two equations e.g.

      [GS, D2, D3, D1] = [9, 21, 30, 36]
      ———-
      [GS, D2, D3, D1] = [9, 20, 33, 38]
      ———-
      [GS, D2, D3, D1] = [9, 18, 45, 48]
      ———-
      [GS, D2, D3, D1] = [9, 17, 60, 62]

      There are further values, but the eldest daughter’s age starts getting unrealistic. For clarity, the answer is not included in the above extra possibilities.

      Like

    • GeoffR's avatar

      GeoffR 6:10 pm on 9 April 2024 Permalink | Reply

      Initially I assumed D2 could be the mother of the setter’s grandson(GS).
      The code below works OK if any of the daughters is the mother, with a lower bound of GS+13.

      # Mother of GS is one of the daughters
      # Assume the mother had a minimum age of 13 when GS was born.
      for GS in range(3, 20):
        for D2 in range(GS+13, 33):
          for D3 in range(1, 34):
            for D1 in range(1, 35):
              if not(GS < D2 < D3 < D1):continue
              # Conditions 3 years ago and 3 years hence
              if (D1-3)**2 == (D2-3)**2 + (D3-3)**2 + (GS-3)**2 \
                  and (D1+3)**2 + (GS+3)**2 == (D2+3)**2 + (D3+3)**2:
                    print(f"Grandson = {GS}, Daughters = {D2}, {D3} and {D1}.")
      

      Like

  • Unknown's avatar

    Jim Randell 4:39 pm on 16 February 2024 Permalink | Reply
    Tags: by: Howard Williams,   

    Teaser 3204: Pressing problem 

    From The Sunday Times, 18th February 2024 [link] [link]

    The Mint’s machine can press circular coins from square plates of precious metal in straight rows with no gaps between coins. Currently, the coins are pressed with the same number of coins in each column and row, with their centres lying on the same vertical and horizontal straight lines.

    As newly appointed Warden of the Mint, Newton set about reviewing its operational efficiency. He found that more rows can be squeezed into the same plate by shifting some rows so that each coin in it touches two coins in the row above; each of these rows will have one fewer coin in it. With this method, the best that can be done is to produce exactly 8 per cent more coins per plate.

    How many more coins per plate can be produced in this way?

    Note: The intention of this puzzle is that the size of the plate allows the rows and columns of the coins in the original (square-packed) configuration to fit exactly with no extra metal around the edges. Without this condition the puzzle has multiple solutions.

    [teaser3204]

     
    • Jim Randell's avatar

      Jim Randell 4:59 pm on 16 February 2024 Permalink | Reply

      Note: See my comment below for a better program that solves the intended puzzle (and can also be used to find the multiple solutions for the original puzzle where the plate can have non-integer sizes).

      If the coins have diameter of 1, then in hexagonal packing the distance between the centres of alternate rows is (√3)/2.

      This Python program considers increasing sized squares until we achieve an 8% better yield from hexagonal packing vs. square packing.

      It runs in 56ms. (Internal runtime is 342µs).

      Run: [ @replit ]

      from enigma import (irangef, inf, intf, divf, sqrt, printf)
      
      r34 = sqrt(3, 4)
      
      # pack the coins in a square of side <x>
      # return (<number in square packing>, <number in hex packing>)
      def pack(x):
        n = intf(x)  # number of rows in square packing
        ns = n * n
        h = divf(x - 1, r34) + 1  # number of rows in hex packing
        nh = n * h
        if x % 1 < 0.5: nh -= divf(h, 2)
        return (ns, nh)
      
      # consider increasing sheet size
      for x in irangef(1.0, inf, step=0.01):
        if not (x % 1 < 0.5): continue
        (ns, nh) = pack(x)
        # does hex packing give 8% more coins? (nh/ns = 1.08)
        if 100 * nh == 108 * ns:
          printf("{d} additional coins [x={x:.2f}: ns={ns} nh={nh}]", d=nh - ns)
          break
      

      Solution: [see my comment below]

      Like

      • Frits's avatar

        Frits 12:31 pm on 17 February 2024 Permalink | Reply

        @Jim, as must be a divisible by 25 I thought you would use a different step.

        The puzzle doesn’t ask for the first solution (you use “break”).
        I am always in favour of exploring the full solution space. I still have to figure out if we can use a break based on logic

        Like

        • Jim Randell's avatar

          Jim Randell 12:55 pm on 17 February 2024 Permalink | Reply

          @Frits: You can remove the [[ break ]] to look for further solutions. But eventually you reach a point where the hexagonal packing is always better than an 8% improvement so you can stop then (without finding any further layouts – although there is a range of square sizes that give the required solution).

          Like

    • NigelR's avatar

      NigelR 9:35 am on 18 February 2024 Permalink | Reply

      It seems odd – bordering on bizarre – that, to make this teaser work in the way that most seem to be interpreting it, you have to assume that the original sheet is bigger than it needs to be by 0.33 of the coin diameter, or some 6.6%. By extension, and also noting that the puzzle is curiously worded: ‘… by shifting some rows…’ rather than: ‘…by shifting alternate rows..’, there are several solutions possible. For example, strictly consistent with the teaser as worded and using the same assumption, there is a valid solution for a much larger plate but leaving the first n rows unchanged. Only the last few rows are shifted, with a full row being added on the bottom. This yields the same required increase in coin number, but with the original sheet being oversized by a smaller percentage!

      Like

      • Jim Randell's avatar

        Jim Randell 9:53 am on 18 February 2024 Permalink | Reply

        @NigelR: Would that be “best that can be done” with that size of square though?

        I supposed the size of square depends on the pressing machine rather than the coins, as it may be used to make coins of several different sizes. And presumably the unused metal is then recycled into new plates.

        Like

        • NigelR's avatar

          NigelR 11:10 am on 18 February 2024 Permalink | Reply

          @Jim: Point taken – while my scheme would yield the right gain in coin number, it would not be optimal so is not a valid solution. I’m still troubled by the apparently arbitrary size of the original plate….!!

          Like

    • Frits's avatar

      Frits 10:43 am on 18 February 2024 Permalink | Reply

      I followed the same method as Jim and Brian but am not convinced that this is a correct approach as the wording of the puzzle isn’t fully clear to me.

      from fractions import Fraction as RF
      
      # final number of coins = 27/25 * n^2 so n must be a multiple of 5
      n = 5
      while True:
       
        # final situation: m rows with m * n - m / 2 coins and m > n
        # (starting with a row of n coins followed by a row of n - 1 coins, etc)
      
        # we may have a solution if m * n - m / 2 equals 1.08 * n^2
        # or m = (54 * n^2) / (50 * n - 25)
        # or m = 1.08 * n + 27 / (100 * n - 50) + 0.54
      
        # assume diameter coin is 1
        # height of <m> packed rows: 1 + (m - 1) * sqrt(0.75)
        # squeeze as many rows as possible (sheet is less than (n + 1) x (n + 1):
        # n + 1 - sqrt(0.75) <= height of m rows < n + 1
       
        # n + 1 - sqrt(0.75) <= 1 + (m - 1) * sqrt(0.75) < n + 1
       
        # n <= m * sqrt(0.75)
      
        # as 1.08 * sqrt(0.75) < 1 every increment of 1 of n will result in
        # an increment of the height of less than 1
        # thus as soon for a certain <n> the height is less than <n> we can
        # stop processing
      
        # final number of rows
        m = RF(54 * n**2, 50 * n - 25)
        # whole number of rows?
        if m.denominator == 1:
          # if we can't squeeze in one more row
          if n + 1 - 3**.5 / 2 <= (h := 1 + (m - 1) * 3**.5 / 2) < n + 1:
            print(f"answer: {m * n - m // 2 - n**2} coins")
       
        # when can we stop processing?
        if not (2 * n <= m * 3**.5):
          break
      
        n += 5
      

      Like

    • Pete Good's avatar

      Pete Good 5:40 pm on 19 February 2024 Permalink | Reply

      Jim,
      I solved this teaser analytically by deriving two quadratic equations for the number of coins pressed after Newton’s change. The first equation assumes that an even number of rows can be pressed and the second one assumes that an odd number of rows can be pressed. The first quadratic equation has a whole number solution and the second has none. The solution follows directly from this result.

      Like

    • Jim Randell's avatar

      Jim Randell 12:58 pm on 20 February 2024 Permalink | Reply

      It seems the way the setter intended the puzzle to work is that that square plate is an exact number of coin diameters across, and the alternate packing consists of some (but not necessarily every other) shifted, shorter rows.

      I have added a note to the puzzle text.

      Like

      • Jim Randell's avatar

        Jim Randell 1:40 pm on 20 February 2024 Permalink | Reply

        Here is a Python program that solves the intended puzzle:

        Run: [ @replit ]

        from enigma import (Accumulator, irange, irangef, inf, sqrt, intf, divf, printf)
        
        r3 = sqrt(3)
        
        # consider increasing sheet size
        for x in irangef(1.0, inf, step=1.0):
          n = intf(x)
          ns = n * n  # square packing
        
          # find maximal packing for some shifted rows
          acc = Accumulator(fn=max)
          f = x % 1
          # max number of rows in hex packing
          m = divf(x - 1, 0.5 * r3) + 1
          # consider the number of shifted rows
          for s in irange(0, divf(m, 2)):
            # calculate the number of unshifted rows we can fit in
            u = s + intf(x - 1 - s * r3) + 1
            nh = u * n + s * (n - 1 if f < 0.5 else n)
            acc.accumulate_data(nh, (u, s))
          (nh, (u, s)) = (acc.value, acc.data)
        
          # can we fit in 8% more coins?
          if 100 * nh == 108 * ns:
            printf("{d} additional coins [x={x:.2f} u={u} s={s}: ns={ns} nh={nh}]", d=nh - ns)
            break
        

        Solution: 32 additional coins per plate can be produced.

        If the coins have diameter 1 and the plate measures 20 × 20, then the original square packing produces 400 coins per sheet.

        However, by shifting 8 of the rows, we have room for 2 more unshifted rows, for a total of 432 coins, and this is an 8% increase over the original packing.

        And this is the only solution if the size of the plate is constrained to be an exact multiple of the coin diameter.


        However if size of the plate is not so constrained there are 2 further solutions.

        If we change the step at line 6 to allow non-integer square sizes (and remove the break statement), we can find the three sizes of square that give us a possible solution. The smallest is that found by my original program, and the largest is an integer sized square that gives the intended answer.

        Here is a diagram of square packing and hexagonal packing with a 5.4 × 5.4 sheet:

        This is a full hexagonal packing, where every other row is shifted (and this was how I originally interpreted the puzzle, and was the solution found by my original program above).

        We get 25 coins/sheet using square packing and 27 coins/sheet using hexagonal packing, an 8% increase.

        The minimal size square that gives this configuration is: (5√3)/2 + 1 ≈ 5.3301…

        But for squares of size 5.5 or larger the alternate rows in the hexagonal packing do not have to be reduced by one coin (as specified by the puzzle text). So the square size must be in the range 5.33… < x < 5.50.


        And with a 10.47 × 10.47 square, the square packing gives 100 coins, but by shifting 2 rows we have room for an extra row:

        This alternate packing has 108 coins, which is also an 8% increase.

        Like

  • Unknown's avatar

    Jim Randell 4:44 pm on 15 December 2023 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3195: Garden divide 

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

    I have a triangular-shaped garden, the sides of which are an exact number of feet long. To improve its usefulness, I’ve decided to partition it by building a straight fence from one corner to the centre of the opposite side. The length of this fence is exactly 51 feet and the side it attaches to is now 26 feet long each side of the fence.

    What, in ascending order, are the lengths of the other two sides of my garden?

    [teaser3195]

     
    • Jim Randell's avatar

      Jim Randell 5:05 pm on 15 December 2023 Permalink | Reply

      We can use the cosine rule to calculate the missing sides in terms of the cosine of their opposite angles, which are supplementary (i.e. their sum is 180°).

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

      Run: [ @replit ]

      from enigma import (irange, sq, is_square, printf)
      
      # the fence is length: a
      # and divides the base of the triangle into: b + b = 2b
      (a, b) = (51, 26)
      
      # by the cosine rule we have:
      #
      # x^2 = a^2 + b^2 - 2.a.b.cos(theta)
      # y^2 = a^2 + b^2 + 2.a.b.cos(theta)
      
      # consider increasing squares for x
      z = sq(a) + sq(b)
      for x in irange(a - b + 1, a + b - 1):
        # calculate the 2.a.b.cos(theta) term
        t = z - sq(x)
        # calculate y
        y = is_square(z + t)
        if y is None or y < x: continue
        # output solution
        printf("x={x} y={y}")
      

      Solution: The other two sides of the garden are: 35ft and 73ft.

      Like

      • Frits's avatar

        Frits 6:18 pm on 15 December 2023 Permalink | Reply

         
        # get 2 squares that sum up to n (with minimum m)
        # https://stackoverflow.com/questions/72093402/sum-of-two-squares-in-python
        def sum_of_two_squares(n, m):
          i = m
          j = int(n ** (1/2))
        
          while i < j:
            x = i * i + j * j
            if x == n:
              yield i, j
        
            if x < n:
              i += 1
            else:
              j -= 1
              
        # by the cosine rule we have:
        #
        # x^2 = a^2 + b^2 - 2.a.b.cos(t)
        # y^2 = a^2 + b^2 + 2.a.b.cos(t)
        
        # so x^2 + y^2 = 2 * (a^2 + b^2)
              
        (a, b) = (51, 26)      
        
        for xy in sum_of_two_squares(2 * (a**2 + b**2), b):
          print("answer:", xy)  
        

        Like

        • Jim Randell's avatar

          Jim Randell 8:33 pm on 15 December 2023 Permalink | Reply

          In fact there is a [[ sum_of_squares() ]] function already in enigma.py.

          from enigma import (sum_of_squares, sq, printf)
          
          # the fence is length: a
          # and divides the base of the triangle into: b + b = 2b
          (a, b) = (51, 26)
          
          # x^2 + y^2 = 2(a^2 + b^2)
          for (x, y) in sum_of_squares(2 * (sq(a) + sq(b)), 2):
            if a - b < x and y < a + b:
              printf("x={x} y={y}")
          

          Like

    • GeoffR's avatar

      GeoffR 10:43 am on 16 December 2023 Permalink | Reply

      # Central fence length (a) and given half side of triangle (b)
      a, b = 51, 26 
      
      # Other two sides of triangle are x and y
      # Cosine rule gives:  x^2 + y^2 = 2 * (a^2 + b^2)
      
      # Max side of other two triangle sides < 51 + 26 i.e. < 77
      # Make x the smallest unknown triangle side
      for x in range(5, 77):
        for y in range(x+1, 77):
          # triangle side constraints
          if not x < (a + b):continue
          if not y < (a + b):continue
          if x * x + y * y == 2 * a**2 + 2 * b**2:
             print(f"Other two sides of garden are {x}ft. and {y}ft.")
      
      

      Without the triangle constraints there is another integer solution to the equation x^2 + y^2 = 2 * (a^2 + b^2). This is x = 25 and y = 77. This would make the overall triangle sides (25,52,77), which is not possible, so this cannot be the teaser answer.

      Like

  • Unknown's avatar

    Jim Randell 4:42 pm on 6 October 2023 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3185: Multiple squares 

    From The Sunday Times, 8th October 2023 [link] [link]

    My grandson likes to compile 3×3 magic squares, where each of the three rows of numbers, each of the three columns of numbers and both of the straight diagonals, add up to the same total. This he did without repeating any of the nine numbers in the square.

    He has now progressed to compiling similar 3×3 squares, which instead of the eight rows, columns and diagonals of numbers adding to the same total, they instead multiply to produce the same product.

    In his first such square this product was 32,768. He was able to find every square of nine different whole numbers that gives this product, excluding identical rotational and mirrored squares.

    What, in ascending order, were the totals of the nine numbers in each of his different squares?

    [teaser3185]

     
    • Jim Randell's avatar

      Jim Randell 5:09 pm on 6 October 2023 Permalink | Reply

      32768 = 2^15, so each multiplicative square is filled with numbers that are powers of 2. And we can treat it as an additive magic square of the corresponding exponents.

      So we just need to find how many essentially different additive magic squares there are (modulo rotation and reflection) with a magic constant of 15. And we can then transform the exponents back to powers of 2 to give the required answers. (Note we allow an exponent of 0 to give a corresponding value of 2^0 = 1).

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to generate all possible additive magic squares of exponents, and then collects those that are different, and we then transform the exponents back to powers of two and sum the numbers in the corresponding multiplicative magic square to give the required total.

      It runs in 77ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, irange, uniq, printf)
      
      # orientations of a square
      squares = [
        # rotations
        (0, 1, 2, 3, 4, 5, 6, 7, 8),
        (2, 5, 8, 1, 4, 7, 0, 3, 6),
        (8, 7, 6, 5, 4, 3, 2, 1, 0),
        (6, 3, 0, 7, 4, 1, 8, 5, 2),
        # reflections
        (2, 1, 0, 5, 4, 3, 8, 7, 6),
        (8, 5, 2, 7, 4, 1, 6, 3, 0),
        (6, 7, 8, 3, 4, 5, 0, 1, 2),
        (0, 3, 6, 1, 4, 7, 2, 5, 8),
      ]
      
      # find the canonical form of a square
      def canonical(sq):
        return min(tuple(sq[j] for j in js) for js in squares)
      
      # find possible squares
      p = SubstitutedExpression(
        [
          # rows
          "A + B + C == 15",
          "D + E + F == 15",
          "G + H + I == 15",
          # columns
          "A + D + G == 15",
          "B + E + H == 15",
          "C + F + I == 15",
          # diagonals
          "A + E + I == 15",
          "C + E + G == 15",
        ],
        base=11,
        answer="(A, B, C, D, E, F, G, H, I)"
      )
      
      # collect results
      ts = list()
      
      # find different squares
      for sq in uniq(canonical(sq) for sq in p.answers(verbose=0)):
        # transform the powers to numbers, and sum them
        t = sum(2**n for n in sq)
        printf("[{sq} -> {t}]")
        ts.append(t)
      
      # output solution
      printf("totals = {ts}", ts=sorted(ts))
      

      Solution: The totals of the numbers in the different squares are: 1022, 1533, 1911.

      And the corresponding squares are:

      Like

    • Hugo's avatar

      Hugo 9:26 am on 15 October 2023 Permalink | Reply

      If we halve each number in the first of those squares, we get one with magic product 4096.
      But that’s certainly not the smallest possible value, as Dudeney showed:
      see the solution and comments to Puzzle no. 203.

      Like

  • Unknown's avatar

    Jim Randell 4:39 pm on 4 August 2023 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3176: Equal shares 

    From The Sunday Times, 6th August 2023 [link] [link]

    When I married, my wife insisted that everything be equally shared between us, which I readily agreed to, provided it included the gardening.

    The garden is rectangular, with a smaller rectangular vegetable plot, of different relative dimensions, in one corner, the area of which is less than 7 per cent of that of the whole garden. The rest of the garden is lawned.

    To satisfy my wife, I constructed the shortest straight length of partition that would split the garden in half, so that half the vegetable plot and half the lawn were each side of the partition. The length of the partition was 30 metres, which exactly equalled the perimeter of the vegetable plot. Both before and after partitioning, all side lengths were an exact number of metres.

    What is the area of the lawn in each half?

    [teaser3176]

     
    • Jim Randell's avatar

      Jim Randell 5:40 pm on 4 August 2023 Permalink | Reply

      See also: Puzzle #213.

      I am assuming the layout is similar to this previous puzzle, with the vegetable plot fully occupying a corner of the garden.

      I used the [[ line_intersect() ]] function in the enigma.py library to determine where the partition meets the boundaries of the garden.

      This Python program runs in 170ms.

      Run: [ @replit ]

      from enigma import (Rational, irange, subsets, decompose, line_intersect, sq, catch, printf)
      
      Q = Rational()
      h = Q(1, 2)
      
      # check for partition crossing L/R boundaries
      def check1(x, y, a, b):
        r = line_intersect((h * a, h * b), (h * x, h * y), (0, 0), (0, y), internal=2, div=Q)
        return r.y.denominator == 1 and sq(x) + sq(y - 2 * r.y) == 900
      
      # check for partition crossing U/D boundaries
      def check2(x, y, a, b):
        r = line_intersect((h * a, h * b), (h * x, h * y), (0, 0), (x, 0), internal=2, div=Q)
        return r.x.denominator == 1 and sq(x - 2 * r.x) + sq(y) == 900
      
      # consider the dimensions of the garden
      for (y, x) in subsets(irange(1, 50), size=2):
        # consider dimensions of the vegetable plot
        for (a, b) in decompose(15, 2, increasing=0, sep=1, min_v=1):
          if not (a < x and b < y and Q(a, b) not in {Q(x, y), Q(y, x)} and a * b < Q(7, 100) * x * y): continue
          # look for a solution
          if any(catch(fn, x, y, a, b) for fn in [check1, check2]):
            # calculate allocation of lawn
            lawn = x * y - a * b
            printf("lawn allocation = {r} m^2 [x={x} y={y}; a={a} b={b}]", r=h * lawn)
      

      Solution: Each half has 270 sq m of lawn.

      And 18 sq m of vegetable plot.

      The garden is a 18 m × 32 m and the vegetable plot is 3 m × 12 m.

      Like

      • Jim Randell's avatar

        Jim Randell 10:53 pm on 4 August 2023 Permalink | Reply

        Or here is an alternative approach:

        We know the veg plot has a perimeter of 30, and integer sides, so we can generate possibilities for the dimensions. We can then look for an integer distance from a corner for the partition to hit the perimeter, and that gives us a line through the centre of the veg plot, and we can extend that line until it is 30m long, which gives us the overall dimensions of the garden.

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

        Run: [ @replit ]

        from enigma import (irange, decompose, ihypot, div, printf)
        
        # consider the (a, b) veg plot, it has a perimeter of 30
        for (a, b) in decompose(15, 2, increasing=0, sep=1, min_v=1):
        
          # and where the partition hits the perimeter of the veg plot
          for d2 in irange(2, a - 1, step=2):
        
            # calculate the size of the (x, y) garden
            h = ihypot(a - d2, b)
            if h is None: continue
            x = div(30 * (a - d2), h)
            y = div(30 * b, h)
            if x is None or y is None: continue
            x += d2
            # check area and ratio conditions
            if not (100 * a * b < 7 * x * y): continue
            if a * y == x * b or a * x == y * b: continue
        
            # calculate the allocation of lawn
            lawn = (x * y - a * b) * 0.5
            printf("lawn allocation = {lawn:g} m^2 [a={a} b={b} d={d} -> x={x} y={y}]", d=d2 // 2)
        

        Like

        • Frits's avatar

          Frits 11:23 pm on 4 August 2023 Permalink | Reply

          @Jim, I don’t immediately see with this program how you can guarantee with that also the lawn is divided in half.

          Like

          • Jim Randell's avatar

            Jim Randell 11:30 pm on 4 August 2023 Permalink | Reply

            @Frits: Because the line that forms the partition passes through both the centre of the the veg plot and the centre of the entire garden, so each is divided exactly in half.

            Like

            • Frits's avatar

              Frits 12:04 am on 5 August 2023 Permalink | Reply

              @JIm, Thanks. I now see that the partition passes through the centre of the entire garden because of the adjustment of the x variable.

              Like

      • Frits's avatar

        Frits 10:37 am on 5 August 2023 Permalink | Reply

        Similar to the alternative approach.

        from enigma import pythagorean_triples, div
        
        # (a - 2 * d)^2 + b^2 = h^2, max(a - 2 * d, b) = 12 with d > 0
        for (p, q, h) in pythagorean_triples(12):
          # check both combinations of p and q
          for (j, k) in [(p, q), (q, p)]:
            a, b, amin2d = 15 - j, j, k
            if a < b: continue
            
            (d, r) = divmod(a - amin2d, 2)
            if not r and d > 0:
              x = div(30 * amin2d, h) 
              y = div(30 * b, h)
              if x is None or y is None: continue
              x += 2 * d
              if not (100 * a * b < 7 * x * y): continue
              if a * y == x * b or a * x == y * b: continue
                 
              # calculate the allocation of lawn
              lawn = (x * y - a * b) / 2
              print(f"answer: {lawn:g} m^2")   
        

        The pair (x, y) (without the addidion of 2*d) can also be easily be determined by using pythagorean_triples(30) as x^2 + y^2 = 30^2. From the pair it is not known which is x and which is y.

        Unfortunately (for performance reasons) there is no builtin reverse order in pythagorean_triples(). I am not sure yet how to continue if you know x and y.

        Like

        • Jim Randell's avatar

          Jim Randell 12:11 pm on 5 August 2023 Permalink | Reply

          Here’s a solution that starts from possible values of (x − 2d, y):

          from enigma import (irange, sum_of_squares, subsets, div, printf)
          
          # provide a stream of the permutations of elements in <seq>
          def permute(seq, select='P'):
            for ss in seq:
              yield from subsets(ss, size=len, select=select)
          
          # the length of the partition is 30m
          for (x_, y) in permute(sum_of_squares(900, 2, min_v=2, sep=1)):
            for b in irange(1, min(y - 1, 14)):
              h = div(30 * b, y)
              if h is None: continue
              a = 15 - b
              d2 = div(a * y - b * x_, y)
              if d2 is None or d2 < 2 or d2 % 2 != 0: continue
              x = x_ + d2
              # check area and ratio conditions
              if not (100 * a * b < 7 * x * y): continue
              if a * y == x * b or a * x == y * b: continue
          
              # calculate the allocation of lawn
              lawn = (x * y - a * b) * 0.5
              printf("lawn allocation = {lawn:g} m^2 [a={a} b={b} d={d} -> x={x} y={y}]", d=d2 // 2)
          

          Like

        • Jim Randell's avatar

          Jim Randell 1:11 pm on 6 August 2023 Permalink | Reply

          @Frits: The [[ pythagorean_triples() ]] approach is a very efficient way to solve the puzzle.

          There are only a few triangles that can fit in the vegetable plot, and only (3, 4, 5) gives a viable 2d value. And then one of the orientations is rejected by the area test.

          Like

    • Frits's avatar

      Frits 10:48 pm on 4 August 2023 Permalink | Reply

         
      from enigma import SubstitutedExpression, is_square
      
      # invalid digit / symbol assignments
      d2i = dict()
      for d in range(0, 10):
        vs = set()
        if d == 0: vs.update('A')
        # bit
        if d > 1: vs.update('X') 
        # MN < 30
        if d > 2: vs.update('M')
        # PQ < 42 (Situation1 : (PQ - 2 * H)**2 + MN**2 == 900 and H <= 6)
        if d > 4: vs.update('P')
        # b = 15 - A <= 14  as A = 1...7
        if d > 6: vs.update('GH')
        if d > 7: vs.update('A')
        
        d2i[d] = vs
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ # check 2 situations depending on bit <X>
          # situation 1 (X = 1):  (0, H) is where the partition crosses the y-axis
          # situation 2 (X = 0):  (G, 0) is where the partition crosses the x-axis
          
          # length of the partition was 30 metres
          "X == 1 or P < 3",     # if X == 0 then PQ**2 < 900
          "PQ < 42",
          
          # set variable H to zero if not applicable
          "X == 1 or H == 0",
          # length of the partition was 30 metres
          "X == 0 or div(PQ - is_square(900 - MN**2), 2) == H",
         
          # set variable G to zero if not applicable
          "X == 0 or G == 0",
          # length of the partition was 30 metres
          "X == 1 or div(MN - is_square(900 - PQ**2), 2) == G",
         
          # garden and plot have dimensions MN by PQ and A by b = 15 - A (A: 1...7)
          "A < MN < PQ",
          
          # plot area is less than 7 per cent of that of the whole garden
          "100 * A * (b := 15 - A) < 7 * MN * PQ",
          
          # different relative dimensions
          "b * MN != A * PQ",
          "b < PQ",
        
          # situation 1: (0, H) must be on line through (A/2, b/2) and (MN/2, PQ/2)
          # line y = d.x + H, d = (PQ - b) / (MN - A)
          # X == 0 or b / 2 - (A / 2) * d == H leads to
          "X == 0 or A * (PQ - b) == (b - 2 * H) * (MN - A)",
          
          # situation 2: (G, x) must be on line through (A/2, b/2) and (MN/2, PQ/2)
          # line y = d.x + c  with c = b / 2 - A * d
          # X == 1 or d * G + b / 2 - A * d == 0 leads to
          "X == 1 or 2 * (A - G) * (PQ - b) == b * (MN - A)",
        ],
        answer="(MN * PQ - A * b) / 2, (MN, PQ), (A, b), (G, H), X, (PQ - b) / (MN - A)",
        d2i=d2i,
        distinct="",
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for ans in p.answers():
        print(f"answer: {ans[0] if ans[0] % 1 else int(ans[0])} m^2")
      

      Like

      • Frits's avatar

        Frits 10:53 am on 5 August 2023 Permalink | Reply

        A new maximum for the long side of the garden (PQ) seems to be 36. This follows from the x^2 + y^2 = 30^2 formula as mentioned in the text with the alternative approach program.

        Like

    • Hugo's avatar

      Hugo 5:35 pm on 13 August 2023 Permalink | Reply

      My first idea was a garden 30×14 with a 1-metre-wide strip of vegetable bed along a short side; the dividing line runs across the middle, parallel to the long sides. Though the area of the bed is certainly less than 7% of the total, it’s not exactly in one corner.

      Then I remembered Puzzle 213 and soon found the expected solution.
      There would be another with the garden 26×24 and the bed 11×4, but its area is then just over 7% of the total. It too involves a 3:4:5 triangle (scaled up sixfold), something I somehow suspected.

      Like

  • Unknown's avatar

    Jim Randell 4:38 pm on 19 May 2023 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3165: Round the bend 

    From The Sunday Times, 21st May 2023 [link] [link]

    My new craft project involves card folding and requires a certain amount of precision and dexterity. For the penultimate stage a rectangular piece of card, with sides a whole number of centimetres (each less than 50cm), is carefully folded so that one corner coincides with that diagonally opposite to it. The resulting five-sided polygon also has sides of integer lengths in cm. The perimeter of the polygon is five twenty-eighths smaller than that of the perimeter of the original rectangular card.

    As a final check I need to find the new area of the card.

    What, in square centimetres, is the area of the polygon?

    [teaser3165]

     
    • Jim Randell's avatar

      Jim Randell 5:27 pm on 19 May 2023 Permalink | Reply

      See also: Teaser 2687.

      If the original rectangle has sides a and b (where a < b), then it has a perimeter of:

      p4 = 2a + 2b

      If the diagonal of the rectangle is h = hypot(a, b), then the length of the fold is:

      f = (a/b) h

      and this forms one of the sides of the pentagon, and so must be an integer.

      The side b is split by the fold into two (integer) lengths:

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

      And so the perimeter of the pentagon is:

      p5 = 2a + 2x + f

      And the area of the pentagon is (the yellow area plus half the blue area):

      P = a(x + y/2) = a(b + x)/2

      The following Python program considers Pythagorean Triples for (a, b, h).

      It runs in 55ms. (Internal runtime is 73µs).

      Run: [ @replit ]

      from enigma import (pythagorean_triples, div, printf)
      
      # consider (a, b, h) values for the original rectangle
      for (a, b, h) in pythagorean_triples(68):
        if not (b < 50): continue
      
        # calculate the length of the fold = f
        f = div(a * h, b)
        if f is None: continue
      
        # calculate the shorter split of side b
        x = div((b - a) * (b + a), 2 * b)
        if x is None: continue
      
        # check perimeters
        p4 = 2 * (a + b)
        p5 = 2 * (a + x) + f
        if 28 * p5 != 23 * p4: continue
      
        # calculate the area of the pentagon
        P = 0.5 * a * (x + b)
      
        # output solution
        printf("a={a} b={b} h={h} f={f} x={x}; p4={p4} p5={p5}; P={P:g}")
      

      Solution: The area of the pentagon is 468 cm².

      The original rectangle is 24 × 32 (perimeter = 112).

      The fold divides the 32 side into 7 + 25, with a fold length of 30. Making the perimeter of the pentagon 92. (92/112 = 23/28).

      The rectangle is divided into 4 triangles: 2× T1 (base x, height a, area 84), 2× T2 (base y, height a, area 300), total area = 768.

      And the area of the pentagon is 2×T1 + T2 = 468.

      Liked by 1 person

      • Jim Randell's avatar

        Jim Randell 4:12 pm on 21 May 2023 Permalink | Reply

        Looking at my diagram the yellow triangles are an (x, a, y) Pythagorean triple (and b = x + y), so it gives us the dimensions of the rectangle immediately, and we then just need to find the length of the fold f.

        Run: [ @replit ]

        from enigma import (pythagorean_triples, ihypot, printf)
        
        # consider (a, b) values for the original rectangle, b = x + y
        for (x, a, y) in pythagorean_triples(54):
          b = x + y
          if not (a < b < 50): continue
        
          # calculate the length of the fold
          f = ihypot(y - x, a)
          if f is None: continue
        
          # check the perimeters
          p4 = 2 * (a + b)
          p5 = 2 * (a + x) + f
          if 28 * p5 != 23 * p4: continue
        
          # calculate the area of the pentagon
          P = 0.5 * a * (x + b)
        
          # output solution
          printf("a={a} b={b} x={x} y={y} f={f}; p4={p4} p5={p5}; P={P:g}")
        

        Like

        • Frits's avatar

          Frits 8:53 am on 22 May 2023 Permalink | Reply

          Nice.

          You can even go with a maximum allowed hypotenuse of 48 (int((48**2 + 49**2) / (2 * 49))).

          Like

    • Frits's avatar

      Frits 3:01 pm on 20 May 2023 Permalink | Reply

      Using a different pythagorean triple .

      There also is a relationship between a and b (for a specific (p, q, r) setting):

      (p * a) mod r = (q * b) mod r

       
      from enigma import (pythagorean_triples, div, printf)
       
      # consider (a, b, ?) values for the original rectangle
      
      # f also is the hypothenuse of a pythagorean triple
      # as f^2 = (a^2 / b)^2 + a^2     (see my explanation at PuzzlingInPython)
      for (y, a, f) in pythagorean_triples(int((47**2 + 48**2)**.5)):
        if not (a < 49): continue
        
        # y = a^2 / b
        b = div(a * a, y)
        if b is None or b > 49: continue
        
        # calculate the shorter split of side b
        x = div((b - a) * (b + a), 2 * b)
        if x is None: continue
       
        # check perimeters
        p4 = 2 * (a + b)
        p5 = 2 * (a + x) + f
        if 28 * p5 != 23 * p4: continue
       
        # calculate the area of the pentagon
        P = 0.5 * a * (x + b)
       
        # output solution
        printf("a={a} b={b} f={f} x={x}; p4={p4} p5={p5}; P={P:g}")  
      

      Like

      • Jim Randell's avatar

        Jim Randell 3:26 pm on 20 May 2023 Permalink | Reply

        @Frits: Neat – it eliminates h from the equations.

        And we can calculate x more succinctly at line 15:

        x = div(b - y, 2)
        

        (y here is y − x in my analysis above).

        And in both these programs we are down to a single candidate solution before the perimeter check is performed (suggesting this condition is superfluous for rectangles in the specified range).

        Like

  • Unknown's avatar

    Jim Randell 4:32 pm on 24 March 2023 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3157: End-of-season analysis 

    From The Sunday Times, 26th March 2023 [link] [link]

    In our local football league each team plays each other once every season. The winner of a game is awarded one point, the loser no points and each team half a point if the game is drawn.

    In the end-of-season analysis, it was found that for each team, exactly half of the points that they were awarded had been awarded for their games against the 15 teams with the lowest number of points.

    How many teams were in the league?

    [teaser3157]

     
    • Jim Randell's avatar

      Jim Randell 5:40 pm on 24 March 2023 Permalink | Reply

      Here is a non-constructive analysis, that finds the only viable answer, but doesn’t show that there is an allocation of points that allows the puzzle to work:

      Equivalently we work in “half-points”, with 2 for a win and 1 for a draw.

      If there are (k + 15) teams (i.e. the bottom 15 teams and k top teams), then the table of points is a (k + 15) × (k + 15) matrix, such that:

      pts(i, i) = 0
      pts(i, j) + pts(j, i) = 2, where i ≠ j

      The sum of the entries in each row in the matrix gives the total points for the corresponding team, and last 15 rows represent the matches against the bottom 15 teams, whereas the first k rows represent the matches against the top k teams, so for each row these sections must have the same sum.

      In the 15 × 15 bottom right sub-matrix, we get an upper triangle with T(14) = 105 elements that sum to: B.

      And a lower triangle that sums to: 210 − B.

      Together the total number of points for the sub-matrix is 210. And this is the total number of points gained by the bottom 15 teams in their matches among themselves. And this accounts for half the points gained by the bottom 15 teams, so the total number of points gained by the bottom 15 teams against the top k teams is also 210, and this the total value of the entries in the k × 15 sub-matrix on the bottom left.

      Hence in total the bottom 15 teams scored 420 points. And the lowest number of points that the best of the bottom teams can achieve is 28 points. (If they all have the same number of points. If any of them score less than this the best of the bottom teams must have more points to compensate).

      Now, considering the top right 15 × k sub-matrix, the entries in this must sum to 30k − 210, and this must have the same value as the k × k top left sub-matrix. Which has entries that sum to 2 T(k − 1) = k² − k.

      Hence:

      k² − k = 30k − 210
      k² − 31k + 210 = 0
      (k − 10)(k − 21) = 0

      So: k = 10; or k = 21.

      In the case k = 10, the total number of points shared between the top 10 teams is 180, so the largest amount the team in 10th place can have is 18 points, but this is not enough.

      However if k = 21, the total number of points shared between the top 21 teams is 840, and the largest amount the team in 21st place can have is 40 points, and this is larger than the lowest number of points the best of the bottom teams can achieve.

      So this case gives the only viable answer to the puzzle. And I wrote a MiniZinc model to verify that a viable table can be constructed.

      Solution: There were 36 teams in the league.

      Here is one possible allocation of half-points:

       1: [0 0 0 0 2 2 2 2 2 0 0 2 0 2 2 2 2 2 2 2 2   0 2 2 2 2 2 2 2 2 2 2 2 2 2 2] → 56
       2: [2 0 0 2 0 2 0 0 2 2 1 0 2 0 0 2 2 2 2 2 2   2 1 0 2 2 2 2 2 0 2 2 2 2 2 2] → 50
       3: [2 2 0 0 0 0 2 0 1 2 1 2 0 0 1 2 2 2 2 2 2   2 2 0 0 2 2 2 2 2 2 1 2 2 2 2] → 50
       4: [2 0 2 0 0 0 0 0 0 0 0 2 2 2 2 0 1 0 2 2 2   0 2 2 2 0 0 2 0 2 1 2 0 2 2 2] → 38
       5: [0 2 2 2 0 0 2 0 2 2 0 0 0 2 0 0 0 0 2 2 1   2 0 0 0 0 2 2 2 1 2 2 2 2 2 0] → 38
       6: [0 0 2 2 2 0 0 0 0 0 1 0 1 0 0 2 2 2 1 2 2   2 2 2 1 0 0 2 2 0 0 2 2 2 0 2] → 38
       7: [0 2 0 2 0 2 0 0 0 0 0 2 2 1 0 0 0 2 2 2 2   2 2 2 0 2 1 0 2 2 2 1 1 0 2 0] → 38
       8: [0 2 2 2 2 2 2 0 0 0 0 0 0 0 2 1 0 2 0 2 0   2 2 2 0 2 2 0 2 2 1 2 0 0 0 2] → 38
       9: [0 0 1 2 0 2 2 2 0 0 0 0 0 0 2 0 2 0 2 2 2   2 0 0 2 2 0 2 1 0 2 2 2 0 2 2] → 38
      10: [2 0 0 2 0 2 2 2 2 0 0 0 0 0 2 0 0 0 2 1 2   2 2 2 2 2 2 0 2 1 2 0 2 0 0 0] → 38
      11: [2 1 1 2 2 1 2 2 2 2 0 0 0 0 0 0 0 2 0 0 0   0 0 2 2 1 0 2 2 2 0 0 2 2 2 2] → 38
      12: [0 2 0 0 2 2 0 2 2 2 2 0 0 0 1 2 0 0 0 0 2   2 0 2 2 0 2 2 0 0 0 1 2 2 2 2] → 38
      13: [2 0 2 0 2 1 0 2 2 2 2 2 0 0 0 0 0 0 0 0 2   2 2 0 0 2 2 2 2 0 2 1 0 2 0 2] → 38
      14: [0 2 2 0 0 2 1 2 2 2 2 2 2 0 0 0 0 0 0 0 0   0 0 2 2 2 2 0 1 2 0 0 2 2 2 2] → 38
      15: [0 2 1 0 2 2 2 0 0 0 2 1 2 2 0 0 2 1 0 0 0   2 2 1 2 0 0 2 0 0 2 2 0 2 2 2] → 38
      16: [0 0 0 2 2 0 2 1 2 2 2 0 2 2 2 0 0 0 0 0 0   2 1 2 2 0 0 1 0 2 2 2 0 1 2 2] → 38
      17: [0 0 0 1 2 0 2 2 0 2 2 2 2 2 0 2 0 0 0 0 0   2 2 0 1 2 2 0 0 2 2 2 0 0 2 2] → 38
      18: [0 0 0 2 2 0 0 0 2 2 0 2 2 2 1 2 2 0 0 0 0   0 1 2 2 2 0 0 1 1 0 2 2 2 2 2] → 38
      19: [0 0 0 0 0 1 0 2 0 0 2 2 2 2 2 2 2 2 0 0 0   0 0 2 2 0 2 0 2 2 1 0 2 2 2 2] → 38
      20: [0 0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 0 0   0 1 0 0 2 2 2 2 2 0 0 2 2 2 2] → 38
      21: [0 0 0 0 1 0 0 2 0 0 2 0 0 2 2 2 2 2 2 2 0   0 2 2 1 2 2 2 0 2 2 2 2 0 0 0] → 38
      
      22: [2 0 0 2 0 0 0 0 0 0 2 0 0 2 0 0 0 2 2 2 2   0 0 2 2 0 1 0 0 0 1 2 2 2 2 2] → 32
      23: [0 1 0 0 2 0 0 0 2 0 2 2 0 2 0 1 0 1 2 1 0   2 0 0 0 2 2 0 0 2 0 2 2 2 0 2] → 32
      24: [0 2 2 0 2 0 0 0 2 0 0 0 2 0 1 0 2 0 0 2 0   0 2 0 1 0 0 0 2 0 0 2 2 2 2 2] → 30
      25: [0 0 2 0 2 1 2 2 0 0 0 0 2 0 0 0 1 0 0 2 1   0 2 1 0 0 0 0 0 0 2 2 2 2 2 2] → 30
      26: [0 0 0 2 2 2 0 0 0 0 1 2 0 0 2 2 0 0 2 0 0   2 0 2 2 0 0 0 0 1 0 0 2 2 2 2] → 30
      27: [0 0 0 2 0 2 1 0 2 0 2 0 0 0 2 2 0 2 0 0 0   1 0 2 2 2 0 0 0 2 0 0 2 0 2 2] → 30
      28: [0 0 0 0 0 0 2 2 0 2 0 0 0 2 0 1 2 2 2 0 0   2 2 2 2 2 2 0 0 0 2 0 1 0 0 0] → 30
      29: [0 0 0 2 0 0 0 0 1 0 0 2 0 1 2 2 2 1 0 0 2   2 2 0 2 2 2 2 0 0 0 0 0 1 2 0] → 30
      30: [0 2 0 0 1 2 0 0 2 1 0 2 2 0 2 0 0 1 0 0 0   2 0 2 2 1 0 2 2 0 0 0 0 2 0 2] → 30
      31: [0 0 0 1 0 2 0 1 0 0 2 2 0 2 0 0 0 2 1 2 0   1 2 2 0 2 2 0 2 2 0 0 0 0 0 2] → 30
      32: [0 0 1 0 0 0 1 0 0 2 2 1 1 2 0 0 0 0 2 2 0   0 0 0 0 2 2 2 2 2 2 0 0 0 2 0] → 28
      33: [0 0 0 2 0 0 1 2 0 0 0 0 2 0 2 2 2 0 0 0 0   0 0 0 0 0 0 1 2 2 2 2 0 0 2 2] → 26
      34: [0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 1 2 0 0 0 2   0 0 0 0 0 2 2 1 0 2 2 2 0 0 2] → 26
      35: [0 0 0 0 0 2 0 2 0 2 0 0 2 0 0 0 0 0 0 0 2   0 2 0 0 0 0 2 0 2 2 0 0 2 0 0] → 20
      36: [0 0 0 0 2 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 2   0 0 0 0 0 0 2 2 0 0 2 0 0 2 0] → 16
      


      In general if there are n bottom teams we are looking for integer roots of:

      k² − (2n + 1)k + n(n − 1) = 0, where k ≥ n

      Which gives solutions:

      n = i (i + 1) / 2 = tri(i) [number of bottom teams]
      k = (i + 1) (i + 2) / 2 = tri(i + 1) [number of top teams]
      t = (i + 1)² [total number of teams in the league]
      for positive integers i

      And the answer to this puzzle is found when i = 5.

      Like

  • Unknown's avatar

    Jim Randell 4:36 pm on 10 February 2023 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3151: Plant stock 

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

    A garden centre bought 500 plants of four different varieties from its supplier. The price per plant of each variety was a whole number of pence and their total average price worked out at exactly one pound.

    The number of plants of variety 2 purchased was “d” greater than that of variety 1, and its price per plant was “d” pence less than that of variety 1. Similarly, the number of variety 3 plants equalled the number of variety 2 plus “d” and its price equalled the variety 2 price less “d” pence. Finally, the number of variety 4 plants equalled the number of variety 3 plus “d” and its price equalled the variety 3 price less “d” pence.

    What, in pence, is the most that a plant could have cost?

    [teaser3151]

     
    • Jim Randell's avatar

      Jim Randell 4:57 pm on 10 February 2023 Permalink | Reply

      If there were n plants of variety 1 bought at a price of p pence per plant, then we have the following plants bought:

      variety 1: n @ p
      variety 2: (n + d) @ (p − d)
      variety 3: (n + 2d) @ (p − 2d)
      variety 4: (n + 3d) @ (p − 3d)

      In total there were (4n + 6d) = 500 plants bought.

      For a given n we can calculate d (which needs to be an integer):

      d = (500 − 4n) / 6

      And the mean cost per plant was 100 pence, so the total cost of 500 plants was 50000 pence. And so we can calculate p (which also needs to be an integer):

      n.p + (n + d)(p − d) + (n + 2d)(p − 2d) + (n + 3d)(p − 3d) = 50000
      500p = 50000 + d(n + d) + 2d(n + 2d) + 3d(n + 3d)
      p = (50000 + d(14d + 6n)) / 500

      from enigma import (irange, div, printf)
      
      # consider the number of var 1 plants bought
      for n in irange(1, 124):
        d = div(500 - 4 * n, 6)
        if d is None: continue
      
        # find the price that makes the mean exactly 100
        p = div(50000 + d * (14 * d + 6 * n), 500)
        if p is None: continue
        printf("n={n} -> d={d} p={p}")
        break
      

      Solution: The maximum possible price for a plant is 284p.

      And for this value of p we have:

      n = 5; d = 80; p = 284

      variety 1: 5 plants @ 284 p each = £14.20
      variety 2: 85 plants @ 204 p each = £173.40
      variety 3: 165 plants @ 124 p each = £204.60
      variety 4: 245 plants @ 44 p each = £107.80
      total = 500 plants, £500.


      Manually:

      The equation for p can be simplified to:

      p = (d² + 150d + 10000) / 100
      p = d²/100 + 3d/2 + 100

      So d must be a multiple of 10, say d = 10k:

      p = k² + 15k + 100
      n = 125 − 15k

      We maximise p by maximising k, and the largest value k can take (keeping n positive) is 8, giving:

      k = 8
      d = 80
      n = 5
      p = 284
      quantities = (5, 85, 165, 245)
      prices = (284, 204, 124, 44)

      Like

    • GeoffR's avatar

      GeoffR 9:31 am on 12 February 2023 Permalink | Reply

      
      # Using Jim's analysis
      PL = []  # list to store plant costs
      
      for n in range(1, 123):
        for d in range(1, 83):
          if 4*n + 6*d == 500:
            d = (500 - 4*n) // 6
            for p in range(1, 350):
              if 500*p == 50000 + d *(14*d + 6*n):
                PL.append(p)
      
      # Find maximum plant price
      print(f"Maximum plant price = {max(PL)} pence.")
      
      

      Like

  • Unknown's avatar

    Jim Randell 4:12 pm on 25 November 2022 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3140: Enjoy every minute 

    From The Sunday Times, 27th November 2022 [link] [link]

    On rugby international morning, I found myself, along with eight friends, in a pub 5.8 miles from the match ground. We were enjoying ourselves, and so wished to delay our departure for the ground until the last possible minute. The publican, wishing to keep our custom for as long as possible, offered to help us get there by carrying us, one at a time, as pillion passengers on his motorbike.

    We could walk at 2.5mph and the bike would travel at 30mph. We all left the pub together, and arrived at the ground in time for kick-off.

    Ignoring the time taken getting on and off the bike, what was our minimum travelling time in minutes?

    [teaser3140]

     
    • Jim Randell's avatar

      Jim Randell 4:58 pm on 25 November 2022 Permalink | Reply

      (Curiously this week’s New Scientist back page puzzle is a simpler variation on the problem [link]).

      If the friends just walked from pub to the stadium it would take 2.32 hours.

      If the barman ferried each of them individually between the pub and the stadium it would take 3.29 hours.

      But we can do better.

      If the barman takes the first friend on his motorbike, and the rest of the friends start walking towards the stadium. Then the barman drops the first friend off to walk the remainder of the distance to the stadium and returns to the group (now a short distance from the pub) and ferries the next friend to join the first friend, and so on until he collects the final friend and drops him off at the stadium at the same time that all the other friends arrive, then we can achieve a minimum overall time.

      The only thing to work out is how far before the stadium to drop the first friend, then it is just a matter of ferrying friends from the trailing to the leading group.

      If each of the k friends walks a distance x at velocity w, and travels by motorbike a distance (d − x) at a velocity v, then each journey takes:

      t = x/w + (d − x)/v

      And the total time taken for the barman to ferry them all is:

      t = [(2k − 1)d − 2kx]/v

      Everyone arrives at the stadium at the same time, so:

      x/w + (d − x)/v = [(2k − 1)d − 2kx]/v
      vx + (d − x)w = [(2k − 1)d − 2kx]w
      vx + dw − xw = (2k − 1)dw − 2kxw
      x(v + w(2k − 1)) = dw(2k − 2)
      x = 2dw(k − 1) / (v + w(2k − 1))

      or:

      n = 2k − 1
      x = dw(n − 1) / (v + wn)
      t = d(w + vn) / v(v + wn)

      The answer can then be calculated directly.

      Run: [ @replit ]

      from enigma import (fdiv, printf)
      
      k = 9    # number of people in the group
      d = 5.8  # distance between pub and stadium
      w = 2.5  # walking speed
      v = 30   # motorbike speed
      
      # calculate amount of walking per person
      n = 2 * k - 1
      x = fdiv(d * w * (n - 1), v + w * n)
      
      # calculate time taken
      t = fdiv(x, w) + fdiv(d - x, v)
      
      # output solution
      printf("t={t:g} hours (= {m:g} min) [x={x:g} miles]", m=t * 60)
      

      Solution: The minimum travelling time is 82 minutes.

      We calculate:

      x = 16/5 = 32/10
      t = 32/25 + 13/150 = 41/30 = 82/60

      So the first friend is dropped off 3.2 miles from the stadium (and walks the remainder of the way).

      Each friend walks for 76.8 minutes and is on the motorbike for 5.2 minutes. Giving each a total journey time of 82 minutes.

      Like

      • Jim Randell's avatar

        Jim Randell 10:56 pm on 30 November 2022 Permalink | Reply

        (See also: Enigma 977).

        Here is a numerical approach, based on the barman dropping the first friend off after a distance x (from the pub) while the remaining friends set off on foot.

        The barman then returns to the trailing group and ferries a single friend from the trailing to the leading group until everyone has been transferred to the leading group. And we record the maximal journey time for the friends to give us a total time to get all the friends to the stadium.

        We then use the [[ find_min() ]] function from the enigma.py library to determine at what distance x the shortest total journey time occurs.

        Unsurprisingly this gives us the same answer as the analytical approach above (but with considerably more effort). But it does show that the logic used in the analysis does indeed produce the minimum time.

        Run: [ @replit ]

        from enigma import (irange, fdiv, find_min, printf)
        
        k = 9    # number of people in the group
        d = 5.8  # distance between pub and stadium
        w = 2.5  # walking speed
        v = 30   # motorbike speed
        
        # if: A starts at a, velocity v; B starts at b, velocity w
        # return: (<position>, <time>) of meeting
        def meet(a, v, b, w, t0=0):
          t = fdiv(b - a, v - w)
          return (b + t * w, t0 + t)
        
        # run a scenario where the first person is dropped off at distance x
        # return the time taken for everyone to arrive
        def run(x):
          ts = list()
          # ferry friend 1 to x and let them walk the remaining distance (d - x)
          d1 = x
          t1 = fdiv(x, v)
          # and so the total time for the first friend is ...
          ts.append(t1 + fdiv(d - d1, w))
        
          # the position of the trailing group at time t is:
          tr = lambda t: min(t * w, d)
          # the position of the leading group at time t >= t1 is:
          ld = lambda t, t1=t1: min(x + (t - t1) * w, d)
        
          # ferry the remaining friends ...
          for _ in irange(2, k):
            # we return from d1 to the trailing group
            (d2, t2) = meet(d1, -v, tr(t1), w, t1)
            # and then back to the leading group
            (d3, t3) = meet(d2, +v, ld(t2), w, t2)
            if d3 < d:
              # they walk the remaining distance
              ts.append(t3 + fdiv(d - d3, w))
            else:
              # they are dropped off at the stadium
              (d3, t3) = (d, t2 + fdiv(d - d2, v))
              ts.append(t3)
            (d1, t1) = (d3, t3)
          # return the maximum time
          return max(ts)
        
        # find the minimal time
        r = find_min(run, 0, d)
        (t, x) = (r.fv, r.v)
        printf("min time = {t:g} hours (= {m:g} min) [drop 1 at {x:g} miles]", m=t * 60)
        

        Here is a graph of the total journey time against the distance x that the first friend is taken from the pub. We see that the minimum time is achieved when x = 2.6 miles.

        Like

      • NigelR's avatar

        NigelR 4:29 pm on 1 December 2022 Permalink | Reply

        Hi Jim. I very much enjoyed this puzzle (more for the logic than the Python content!) but I’m intrigued to know how you got to the term 2kx in your second equation. I got to it indirectly by looking at the vector sum of all the motorbike journeys out: [(k)(d-x)] +back: [(k)(d-x)-d] given that he finishes up a distance d from where he started. That then reduces to:
        [(2k-1)d -2kx] but is there a more intuitive way of getting to the second term?

        Like

        • Jim Randell's avatar

          Jim Randell 10:50 pm on 1 December 2022 Permalink | Reply

          @Nigel: The way I thought of it the barman makes a journey towards the stadium for each of the k friends. And in between friends he has to make (k − 1) return journeys towards the pub.

          If he made complete journeys between the pub and the stadium this would be (2k − 1) journeys of distance d for a total of (2k − 1)d.

          But if he made complete journeys he would be travelling over the ground that each friend walks, in both directions, so this amount is overcounting the barmans distance by 2x for each of the k friends.

          So the actual overall distance travelled by the barman is:

          (2k − 1)d − 2kx

          And this actual distance is travelled at velocity v, so we can determine the total time taken for the barman.

          Like

          • NigelR's avatar

            NigelR 9:31 am on 3 December 2022 Permalink | Reply

            Thanks Jim. It was the ‘in both directions’ that I was struggling to get my head around. This week’s puzzle is trivial by comparison!

            Like

    • Hugh Casement's avatar

      Hugh Casement 9:45 am on 4 December 2022 Permalink | Reply

      There were some early Brain-Teasers of a similar kind by Brigadier A.G.H. Brousson (who died in 1976), involving the Smart brothers who took part in races with one bicycle between them.
      Numbers 640, 663, 686, 722, 741, and 792 would presumably yield to a variant of Jim’s analysis as given here. 792 (at least) is flawed because it doesn’t specify that they all arrived together — nor, for that matter, whether riding pillion on the rear carrier is permitted (I know from experience that it seriously upsets the balance and steering!).

      Like

      • Jim Randell's avatar

        Jim Randell 10:53 am on 8 December 2022 Permalink | Reply

        @Hugh: Thanks. I’ll have a look at those. None of them are in the published books I’m working from, so it would have been a while before I got round to looking at them.

        Like

  • Unknown's avatar

    Jim Randell 4:33 pm on 23 September 2022 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3131: Heads up savings 

    From The Sunday Times, 25th September 2022 [link] [link]

    Little Spencer saves 5p coins in a jar, and when they reach £10, deposits them in his savings account. He likes playing with the coins. In one game, after first turning them all heads up, he places them in a row on the table. Starting from the left, he then turns over every 2nd coin until he has reached the end of the row. He then again starts from the left, and this time turns over every 3rd coin. He repeats this for every 4th, 5th coin etc, until finally he turned over just one coin, the last in the row.

    At the end of the game I could see that if Spencer had exactly 75 per cent more coins he would have an increase of 40 per cent in the number showing heads. However, if he had exactly 50 per cent fewer coins, he would have a decrease of 40 per cent in the number showing heads.

    What is the value of his 5p savings?

    There are now 750 Teaser puzzles available on the S2T2 site.

    [teaser3131]

     
    • Jim Randell's avatar

      Jim Randell 5:09 pm on 23 September 2022 Permalink | Reply

      (See also: Puzzle #08).

      Here is a constructive solution.

      It runs in 52ms. (Internal runtime is 409µs).

      Run: [ @replit ]

      from enigma import (irange, csum, div, printf)
      
      # play the game with <n> coins
      def coins(n):
        # each coin starts out showing heads = 1
        vs = [1] * n
        # allow the coins to be indexed from 1
        vs.insert(0, None)
        # every <k> coins
        for k in irange(2, n):
          # flip coin k, 2k, 3k, ....
          for i in irange(k, n, step=k):
            vs[i] ^= 1
        vs.pop(0)
        return vs
      
      # it is enough to calculate one sequence, and then use prefixes
      heads = list(csum(coins(350), empty=1))
      
      # consider initial number of coins
      for n in irange(1, 200):
        # we need 1.75 times the number of coins, and 0.5 times the number
        n1 = div(175 * n, 100)
        n2 = div(50 * n, 100)
        if n1 is None or n2 is None: continue
      
        # h1 is 1.4 times h; h2 is 0.6 times h
        (h, h1, h2) = (heads[x] for x in (n, n1, n2))
        if not (100 * h1 == 140 * h and 100 * h2 == 60 * h): continue
      
        # output solution
        printf("{n} coins = {h} heads; {n1} coins = {h1} heads; {n2} coins = {h2} heads")
      

      Solution: The total value of the coins is £1.40.

      Spencer has 28 coins.

      After performing the procedure there are 5 coins remaining heads up (= coins 1, 4, 9, 16, 25).

      If he had 1.75× the number of coins (= 49 coins), then 7 would remain heads up (= coins 1, 4, 9, 16, 25, 36, 49).

      And if he had 0.5× the number of coins (= 14 coins), then 3 would remain heads up (= coins 1, 4, 9).

      Like

      • Jim Randell's avatar

        Jim Randell 5:46 pm on 23 September 2022 Permalink | Reply

        Using the fact that the coins that remain heads up are exactly those in the perfect square numbered positions (numbering from 1), we can get a shorter (and faster) program.

        This Python program runs in 51ms. (Internal runtime is 221µs).

        Run: [ @replit ]

        from enigma import (irange, isqrt, div, printf)
        
        # play the game with <n> coins, return the number of heads
        heads = isqrt
        
        # consider initial number of coins
        for n in irange(1, 200):
          # we need 1.75 times the number of coins, and 0.5 times the number
          n1 = div(175 * n, 100)
          n2 = div(50 * n, 100)
          if n1 is None or n2 is None: continue
        
          # h1 is 1.4 times h, h2 is 0.6 times h
          (h, h1, h2) = (heads(x) for x in (n, n1, n2))
          if not (100 * h1 == 140 * h and 100 * h2 == 60 * h): continue
        
          # output solution
          printf("{n} coins = {h} heads; {n1} coins = {h1} heads; {n2} coins = {h2} heads")
        

        Like

    • NigelR's avatar

      NigelR 10:50 am on 26 September 2022 Permalink | Reply

      Irrespective of the number of times coin n in the row is flipped, its final H/T depends on whether n has an odd or even number of factors. (I hadn’t spotted the elegance of the perfect squares!).
      PS: I think the answer sought was actually the value of the coins, not the number.

      
      # Test whether n has an even number of factors
      countfac = lambda n: True if [1 if n % i == 0 else 0 for i in range(1, (n//2)+1)].count(1) %2==0 else False
      heads={x:1 for x in range(1,200)} #initialise heads as dictionary 
      for x in range(2,200):
          heads[x]=heads[x-1]
          if countfac(x): heads[x]+=1  #heads[n] now has cumulative number of heads for row of n coins
      #test for output conditions. Number of coins must be divisible by 4 if 75% greater is integer 
      for x in range(4,200,4):
          if x*1.75>200:continue
          y=int(x*1.75)
          z=int(x/2)
          if heads[y]!=heads[x]*1.4:continue
          if heads[z]!=heads[x]*0.6:continue
          value = divmod(5*x,100)
          print(x ,'coins in row, ',heads[x],'of which are heads. Value of savings is £',value[0],'and',value[1],'p')
      

      Like

      • Jim Randell's avatar

        Jim Randell 2:24 pm on 26 September 2022 Permalink | Reply

        @NigelR: I left determining the total value of a certain number of 5p coins as a simple exercise for the reader ;-).

        You could shorten this line of code somewhat:

        countfac = lambda n: True if [1 if n % i == 0 else 0 for i in range(1, (n // 2) + 1)].count(1) % 2 == 0 else False
        

        (True if ... else False) is just the same as evaluating ... (in a boolean context):

        countfac = lambda n: [1 if n % i == 0 else 0 for i in range(1, (n // 2) + 1)].count(1) % 2 == 0
        

        and then in the list comprehension, (1 if ... else 0) is also the same as ... (in a boolean context; in Python False and True are just 0 and 1 in disguise):

        countfac = lambda n: [n % i == 0 for i in range(1, (n // 2) + 1)].count(1) % 2 == 0
        

        and we don’t need to construct the list, just to count the number of 1’s in it:

        countfac = lambda n: sum(n % i == 0 for i in range(1, (n // 2) + 1)) % 2 == 0
        

        Also note that Python’s builtin range function does not include the endpoint. So if you want to go to 350 in line 4 you need to specify a stop value of 351. Similarly in line 8, to check up to 200 coins you need to specify a stop value of 201.

        (I tend to use the inclusive irange() function from the enigma.py library, which includes both endpoints, to avoid this kind of “fencepost” error).

        Like

        • NigelR's avatar

          NigelR 8:40 pm on 26 September 2022 Permalink | Reply

          JIm: Thank you so much for taking the time to unpick my messy code and for your very helpful advice – your countfac is much simpler and I’m now wiser! I couldn’t work out what on earth I’d done in the lambda an hour after writing it!
          Agree on the stop value of 351, but I did think about the 200/201 and concluded that Spencer would have banked the lot if it had reached 200, and hence he would only have been playing with up to 199 coins. Perhaps I’m overthinking it!

          Like

        • Jim Randell's avatar

          Jim Randell 10:08 am on 27 September 2022 Permalink | Reply

          Yes the (200, 350) case is a bit of a grey area. I decided he might like one last play with his coins before he banked them, so I might as well check it, as I prefer solutions that exhaustively explore the solution space.

          As it turns out it doesn’t provide an answer, so it doesn’t really matter if you check it or not.

          Like

    • NigelR's avatar

      NigelR 10:58 am on 26 September 2022 Permalink | Reply

      … and,of course, the 75% greater number is only hypothetical and hence can be greater than 200. My line 4 should go to 350, and line 10 is unnecessary.

      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