S2T2

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

• 

  Jim Randell 6:59 am on 1 March 2026 Permalink | Reply
  Tags: by: Howard Williams   

  Teaser 3310: Building bridges 

  From The Sunday Times, 1st March 2026 [link] [link]

  Chuck’s ranch is 16 km north of a narrow straight river flowing west to east. His cousin Dwayne has a ranch 72 km south and 30 km east of Chuck’s ranch. To join their ranches, they are each required to build a straight road from their ranch to a bridge that will be constructed over the river at a location yet to be decided.

  Selfishly, Chuck wishes to have the bridge built at a location that would require Dwayne’s road to be as much as possible longer than the road he has to build on his side of the river. Dwayne wishes another location for the bridge, a location that would require the roads on both sides of the river to be of equal lengths.

  What is the distance between these two bridge locations?

  [teaser3310]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell is discussing. Toggle Comments

   
  • 

    Jim Randell 7:12 am on 1 March 2026 Permalink | Reply

    (See also: Teaser 3286).

    Here is a numerical solution. (Which saves having to do any calculus).

    The following Python program runs in 72ms. (Internal runtime is 231µs).

    from enigma import (hypot, find_max, find_zero, printf)
    
    # calculate lengths of road for location of bridge x
    # x = km E from C
    C = lambda x: hypot(16, x)
    D = lambda x: hypot(56, 30 - x)
    
    # calculate how much more road D builds than C
    f = lambda x: D(x) - C(x)
    
    # find C's proposed bridge location (maximise f)
    xC = find_max(f, -100, +130).v
    printf("xC = {xC:.3f}")
    
    # find D's proposed bridge location (f = 0)
    xD = find_zero(f, -100, +130).v
    printf("xD = {xD:.3f}")
    
    # calculate the distance between the proposed locations
    d = abs(xC - xD)
    printf("diff = {d:.3f}")
    

    Solution: The proposed locations for the bridge are 75 km apart.

    

    C’s proposed location is 12 km west of the nearest point on the river to him. C’s road would be 20 km, and D’s road would be 70 km. (Total road length would be 90 km).

    (This corresponds to the position where the angles that the roads make with the river are equal. So if we mirrored one of the brothers ranches in the river, so that they are both on the same side, then there would be one straight road that joins the bridge to both ranches).

    D’s proposed location is 33 km east of the nearest point on the river to him. Both roads would be 65 km. (Total road length would be 130 km).

    ---

    The minimal total road length occurs if the bridge is built 6.66 km east of the nearest point on the river to C. C’s road would be 17.33 km, and D’s road would be 60.66 km. (Total road length = 78 km).

    (If we were to draw a straight line between the ranches, we achieve the shortest possible combined distance, and the position of the bridge is where the line crosses the river).

    Note that measuring the distances between points, we have:

    [C→D] × [XC→XD] = 78 × 75 = 5850
    [C→XC] × [D→XD] + [C→XD] × [D→XC] = 20 × 65 + 65 × 70 = 5850

    Which means the quadrilateral (C, XC, D, XD) is cyclic.

    ---

    Analytically:

    The two roads are the same length when:

    √(56^2 + (30 − x)^2) = √(16^2 + x^2)
    3136 + (900 − 60x + x^2) = 256 + x^2
    ⇒
    60x = 3780
    x = 63

    And we see both roads have length 65 km.

    To calculate the maximum of the function f(x) we can differentiate it, at look for stationary points (i.e. points where f'(x) = 0):

    f(x) = √(56^2 + (30 − x)^2) − √(16^2 + x^2)
    f'(x) = ((x − 30) / √(x^2 − 60x + 4036)) − (x / √(x^2 + 256))

    And we can find values when f'(x) is 0 by looking for values where:

    ((x − 30) / √(x^2 − 60x + 4036)) = (x / √(x^2 + 256))
    ⇒
    (x − 30)^2 (x^2 + 256) = x^2 (x^2 − 60x + 4036)
    (x^2 − 60x + 900) (x^2 + 256) = x^2 (x^2 – 60x + 4036)
    x^4 − 60x^3 + 1156x^2 − 15360x + 230400 = x^4 − 60x^3 + 4036x^2
    ⇒
    2880x^2 + 15360x − 230400 = 0
    960(x + 12)(3x − 20) = 0
    x = −12; x = 20/3

    x = −12 is a stationary point that gives the maximum value of f(x) (= 50 km when D’s road is 70 km and C’s road is 20 km).

    (And x = 20/3 is not a stationary point of f(x), but does give the position of the bridge for the minimum combined distance for the roads).

    LikeLike

  Reply Cancel reply

  Required fields are marked *

  Name *

  Email *

  Website

  Notify me of new comments via email.

  Notify me of new posts via email.

  Δ

• 

  Jim Randell 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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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: The 5-digit number was 83160.

    There are 6 candidate scenarios (number = sum × multiple):

    2376 = 594 × 4 → 23760 = 792 × 30
    3564 = 594 × 6 → 35640 = 792 × 45
    4752 = 594 × 8 → 47520 = 792 × 60
    7128 = 594 × 12 → 71280 = 792 × 90
    8316 = 594 × 14 → 83160 = 792 × 105

    In each case the sum of the digits in the 4-digit and 5-digit numbers is 18, and so the sum of the 2-digit combinations from the 4-digit number is 33 × 18 = 594, and the sum of the 2-digit combinations from the 5-digit number is 44 × 18 = 792.

    Of the 5-digit numbers only the last one is a 3-digit multiple of the sum, and this provides the answer to the puzzle.

    LikeLike

  • 

    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])
    

    .

    LikeLike

    • 

      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])
      

      LikeLike

  • 

    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)
    

    LikeLike

    • 

      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)
      

      LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell, Alex.T.Sutherland, Brian Gladman, and 1 other are discussing. Toggle Comments

   
  • 

    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).

    LikeLike

  • 

    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))
    

    LikeLike

    • 

      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
      

      LikeLike

      • 

        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.

        LikeLike

  • 

    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)) 
    

    LikeLike

  • 

    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.

    LikeLike

    • 

      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.

      LikeLike

      • 

        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.

        LikeLike

        • 

          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).

          LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Alex T Sutherland, Ruud, and Jim Randell are discussing. Toggle Comments

   
  • 

    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?

    LikeLike

    • 

      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}]")
      

      LikeLike

    • 

      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

      LikeLiked by 1 person

  • 

    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))
    

    LikeLiked by 1 person

    • 

      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.

      LikeLike

      • 

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

        I didn’t read it like that.

        LikeLike

    • 

      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.

      LikeLike

      • 

        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).

        LikeLike

        • 

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

          Thanks for the clear explanation.

          LikeLike

  • 

    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.
    

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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

    LikeLike

  • 

    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)];
    
    
    

    LikeLike

  • 

    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)
    

    LikeLike

    • 

      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)
      

      LikeLike

  • 

    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)
    

    LikeLike

  • 

    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)}.")
    
    

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell and Frits are discussing. Toggle Comments

   
  • 

    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

    LikeLike

    • 

      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]]

      LikeLike

  • 

    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}") 
    

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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.

    LikeLike

  • 

    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))  
    

    LikeLike

  • 

    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)
    

    LikeLiked by 1 person

  • 

    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))  
    

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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

    LikeLike

  • 

    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)
    

    LikeLike

  • 

    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()))

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell and Hugo are discussing. Toggle Comments

   
  • 

    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.

    LikeLike

    • 

      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.

      LikeLike

  • 

    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.

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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).

    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.

    LikeLike

  • 

    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"     
    

    LikeLike

    • 

      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.

      LikeLike

  • 

    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;
    
    
    

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

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

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

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

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

    Solution: The final total is 102.

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

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

    LikeLike

    • 

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

      This my version

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

      LikeLike

    • 

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

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

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

      LikeLike

  • 

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

    Here is a solution based on a bit of analysis:

    We have:

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

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

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

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

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

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

    We can address this manually, or programatically.

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

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

    ---

    Manually:

    We are looking to solve:

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

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

    This boils down to choosing two subsets such that:

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

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

    Otherwise we have:

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

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

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

    LikeLike

    • 

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

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

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

      LikeLike

      • 

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

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

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

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

        LikeLike

    • 

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

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

      LikeLike

      • 

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

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

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

        LikeLike

      • 

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

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

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

        LikeLike

        • 

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

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

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

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

          LikeLike

    • 

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

      Or, using a single call to express():

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

      LikeLike

  • 

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

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

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

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

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

    LikeLike

  • 

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

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

    LikeLike

  • 

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

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

    LikeLike

  • 

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

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

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

    It worked well – poem below:

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

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

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

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

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

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

    LikeLike

• 

  Jim Randell 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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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).

    LikeLike

    • 

      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}")
      

      LikeLiked by 1 person

      • 

        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).

        LikeLike

        • 

          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.

          LikeLike

  • 

    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]) 
    

    LikeLike

  • 

    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])];
    

    LikeLike

  • 

    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.

    LikeLike

  • 

    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}.")
    

    LikeLike

• 

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

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell, Pete Good, NigelR, and 1 other are discussing. Toggle Comments

   
  • 

    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]

    LikeLike

    • 

      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

      LikeLike

      • 

        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).

        LikeLike

  • 

    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!

    LikeLike

    • 

      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.

      LikeLike

      • 

        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….!!

        LikeLike

  • 

    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
    

    LikeLike

  • 

    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.

    LikeLike

  • 

    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.

    LikeLike

    • 

      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.

      LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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.

    

    LikeLike

    • 

      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)  
      

      LikeLike

      • 

        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}")
        

        LikeLike

  • 

    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.

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Hugo and Jim Randell are discussing. Toggle Comments

   
  • 

    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:

    

    LikeLike

  • 

    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.

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

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

   
  • 

    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.

    

    LikeLike

    • 

      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)
      

      LikeLike

      • 

        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.

        LikeLike

        • 

          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.

          LikeLike

          • 

            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.

            LikeLike

    • 

      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.

      LikeLike

      • 

        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)
        

        LikeLike

      • 

        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.

        LikeLike

  • 

    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")
    

    LikeLike

    • 

      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.

      LikeLike

  • 

    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.

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Frits and Jim Randell are discussing. Toggle Comments

   
  • 

    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.

    LikeLiked by 1 person

    • 

      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}")
      

      LikeLike

      • 

        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))).

        LikeLike

  • 

    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}")  
    

    LikeLike

    • 

      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).

      LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell is discussing. Toggle Comments

   
  • 

    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.

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  GeoffR and Jim Randell are discussing. Toggle Comments

   
  • 

    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)

    LikeLike

  • 

    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.")
    
    

    LikeLike

• 

  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]

  Rate this:

  Share:

  • X
  • Facebook
  • WhatsApp
  • Email

  Like Loading...

  Jim Randell, Hugh Casement, and NigelR are discussing. Toggle Comments

   
  • 

    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.

    LikeLike

    • 

      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.

      

      LikeLike

    • 

      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?

      LikeLike

      • 

        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.

        LikeLike

        • 

          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!

          LikeLike

  • 

    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!).

    LikeLike

    • 

      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.

      LikeLike