# Radio Times Puzzle for Today No. 272

*by Professor Michael Paterson, University of Warwick*

#### Published on Thursday 19 July 2018 (link)

I have a tray of length 5 and width 2 so 10 round coins of width 1 will fit in it snugly without overlaps. No room for another. Similarly, a tray of length 50 will accommodate only 100 coins. Things get more interesting with a longer tray! A tray of length 500 and width 2 can accommodate at least 1001 coins. Show how this can be done. To be clear, this is just about fitting non-overlapping circles in rectangles, so no trickery with funny-shaped coins or thermal expansion coefficients! A useful hint is to start packing coins from the middle not from one end.

For a more mathematical challenge, what is the smallest \(n\) so that \(2n+1\) circles of diameter 1 can be packed without overlap in an \(n\) by 2 rectangle? If you think you have a good answer to this, do let me know, but note that the really hard problem, still I think unsolved, is to prove the best optimum result.

John Owen (the coordinator for the Sunday Times Teasers) introduced this puzzle as a ‘bonus teaser’ on the Sunday Times Teasers Discussion Group in the comments on this page. Subsequently he and others published possible solutions for the more difficult problem posed above, showing that a 2 by 166 tray holding 332 coins in a ‘2 by 2’ packing could accommodate 333 coins using a more compact packing using triples made up of three mutually touching coins. This solution was, for example, described by Jim Randell on his Enigmatic Code site.

To the surprise of many, including me, Robert Brown then announced that he had found an improved solution that could fit 331 coins into a 2 by 165 tray and also thought that he could fit 329 coins into a 2 by 164 tray. He was, however, using measurements from scaled drawings and asked whether I could confirm this solutions using a more precise computer based approach. This launched my own study of the problem that I will now describe (I may refer to coins packed into trays or circles packed into rectangles in what follows).

The basis for the initial solution is illustrated here:

Units of three mutually touching coins are placed as shown, alternately touching the lower and upper edges of the enclosing tray with small gaps of \((2-\sqrt{3})r\) between them and the opposite edge. These triples are then placed repeatedly to fill the tray. The distance between the centre-lines of adjacent triples (the dotted vertical lines) is given by \((1 + \sqrt{4\sqrt{3} -3})r \) which is approximately \(2.982r\). Except at each end, the two ‘half coins’ in each unit match with the half coins in adjacent (inverted) units to form full coins, which means that we can effectively fit three coins into a length of about \(2.982r\). The ‘packing ratio’ in the original “2 by 2” packing is 2 coins in a length of \(2r\) whereas our new packing achieves 3 coins in a length of about \(2.982r\), albeit at the cost of needing an extra one half a coin width at each end. Despite this cost, however, as we add each of these new units we gain a small amount of space so that eventually we overcome the initial cost and then go on to provide enough space to add an additional coin. Using this method it proves possible to pack 333 coins into a 2 by 164 tray, one more than the regular “2 by 2” packing.

The way Robert Brown’s improved solutions work is to modify each end of the arrangement by adjusting the coin positions to achieve a more compact packing. An example of such an arrangement is shown here:

In these ends, the triples are adjusted to align all lower coins on the lower edge of the tray, while the upper coins alternate between touching the upper edge and touching the two coins below them. These end arrangements can terminate on coins D, H, L … and can be applied at both ends of the overall sequence with regular triples being used in the middle section. A further possible adjustment is to raise coins G, K, … to touch the coins above them, a move which turns out to be slightly better in reducing the lengths of the ends.

Robert designed these coin layouts by hand but the approach can be automated. If we start from a triple and restrict ourselves to coins that touch tray edges or other coins, then there are three different positions where the next two coins can be placed as shown here:

When we place another two coins, each of these three initial positions give another three positions for these coins giving 9 positions in total. Each time we repeat the process the number of coin positions triples so we end up with 3, 9, 27, … possibilities (in practice, the number is less because a lot of the positions are duplicates). If we now consider a specific coin in the sequences, the many different sequences reaching this coin will result in slightly different positions and we can pick the sequence that minimises its length and hence obtain the minimum length end for this number of coins. The resulting length measured from the centre of coin B to a tray edge that encloses the target ending coins is given here (with coins of unit radius):

\[\begin{array}{|c|r|r|} \hline \text{Number of Coins} & \text{Lengh} \\

\hline 0 & 2.000000 \\

\hline 1 & 2.981970 \\

\hline 2 & 3.981970 \\

\hline 3 & 4.966411 \\

\hline 4 & 5.963939 & X \\

\hline 5 & 6.950852 \\

\hline 6 & 7.948380 & X \\

\hline 7 & 8.937211 \\

\hline 8 & 9.932821 & X \\

\hline 9 & 10.923484 \\

\hline 10 & 11.919137 & X \\

\hline 11 & 12.911202 & X \\

\hline 12 & 13.905453 \\

\hline 13 & 14.898920 \\

\hline 14 & 15.893171 & X \\

\hline 15 & 16.887423 & X \\

\hline 16 & 17.880890 & X \\

\hline

\end{array}\]

It can be seen from this table that \(n\) coins can be fitted in a space that is slightly less than \(n+2\) long. Note here that the yellow coins are counted as regular triples in the centre section, not in the end sections. But, to my surprise, minimising the lengths in this way does not find the shortest end sequences! This is because, in looking for minimum end lengths we have to consider ends built starting from both sides of a ‘2 + 2 half’ unit and sometimes the minimum length unit will be that constructed from the other end. Jim Randell used a neat way of working this out without by looking at each result and checking if a length with three less coins plus a ‘2+2 half’ unit was of shorter. This shows that the lengths marked with ‘X’s are not of minimum length and do not need to be used. So we are left with these possible end configurations:

\[\begin{array}{|c|r|} \hline \text{Number of Coins} & \text{Lengh} \\

\hline 0 & 2.000000 \\

\hline 1 & 2.981970 \\

\hline 2 & 3.981970 \\

\hline 3 & 4.966411 \\

\hline 5 & 6.950852 \\

\hline 7 & 8.937211 \\

\hline 9 & 10.923484 \\

\hline 12 & 13.905453 \\

\hline 13 & 14.898920 \\

\hline

\end{array}\]

The method of looking for a fit is now as follows:

- Select a target tray length and two possible end sequences
- Subtract the lengths of the two end sequences from the tray length and divide the remainder by the length of of the triple unit
- The integer part of the result is one less than the number of triple units needed to complete the packing
- Add the numbers of coins in the centre section and the two ends and check if we have packed an extra coin

The Python program below automates this process and produces the following results for the smallest tray found that allows an extra coin (164). The lengths are given in coin widths and these solutions are the five that fit with the most free space left:

\[\begin{array}{|c|c|r|r|} \hline \text{Ends} & \text{Triples} & \text{Length} & \text{Gap}\\

\hline (12, 12) & 102 & 163.997397 & 0.002603 \\

\hline (8, 10) & 104 & 163.997789 & 0.002211 \\

\hline (6, 12) & 104 & 163.998490 & 0.001510 \\

\hline (4, 8) & 106 & 163.999583 & 0.000416\\

\hline (6, 6) & 106 & 163.999583 & 0.000417 \\

\hline \end{array} \]

Although we have used different methods, comparing these with those reported by Jim Randell on this page, there is complete agreement on these five solutions. I did at first believe that my length minimisation technique could find more solutions but Jim’s approach was better than mine and always found the same or better results. Here are the best results for the lengths 164, 165 and 166:

\[\begin{array}{|c|c|c|r|r|r|} \hline \text{Tray Length} & \text{Ends} & \text{Triples} & \text{Coins} & \text{Length} & \text{Gap}\\

\hline 164 & (12, 12) & 102 & 329 & 163.997397 & 0.002603 \\

\hline 165 & (8, 12) & 104 & 331 & 164.991648 & 0.008352 \\

\hline 166 & (10, 12) & 104 & 333 & 165.985507 & 0.014493 \\

\hline \end{array} \]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
from itertools import combinations_with_replacement as cwr from collections import defaultdict from math import sqrt, atan2, sin, cos model = 2 # the initial coin positions sep = (1 + sqrt(4 * sqrt(3) - 3)) base_coins = [ # separated coins (Jim's original) ((1 - sep, 1), (-1, 3)), # touching coins (Jim's alternative) ((1 - sep, 3), (-1, 1)), # triple on lower edge (my original) ((0, 1 + sqrt(3)) , (1, 1)), # triple on upper edge (my alternative) ((0, 3 - sqrt(3)) , (1, 3)) ] if model in {1, 2}: null_length = 0 coin_offset = -1 elif model in {3, 4}: null_length = 2 coin_offset = 3 else: print("model is in range 1..4") exit() # the coin radius radius = 1 # the length of the '2 + 2 half' units rho = radius * sep # the maximum number of coins considered in ends max_ec = 16 # the offset from the last coin in an end and # the end of the tray (normally the radius) ofs = radius # tolerance for distance calcualtions tol = 1e-12 * radius # calculate the coordinates of the centre of a # circle (p3) that is tangent to two given # circles p1 = (x1, y1) and p2 = (x2, y2) def tangent_cc(r, p1, p2, ty=1): x0, y0 = p1 x1, y1 = p2 l = sqrt((x1 - x0) ** 2 + (y1 - y0) ** 2) / 2 t = atan2(y1 - y0, x1 - x0) h = sqrt(4 * r * r - l * l) t = sorted(( (l * cos(t) - h * sin(t), l * sin(t) + h * cos(t)), (l * cos(t) + h * sin(t), l * sin(t) - h * cos(t)) )) return x0 + t[ty][0], y0 + t[ty][1] # calculate the coordinates of the centre of a # circle that is tangent to a given circle and # to a horizontal line at height h def tangent_ce(r, p1, h): x0, y0 = p1 y = abs(h - r) x = sqrt(4 * r * r - (y - y0) ** 2) return x + x0, y def check_last(r, cs): xx, yy = cs[-1] for x, y in cs[-3:-1]: t = (x - xx) ** 2 + (y - yy) ** 2 if t - 4 * r * r < -tol: raise ValueError # recursively place coins into the tray with each coin # placed in either of its constrained positions starting # with the last two coins in when called def gen_nxr(n, r, cs): check_last(r, cs) ln = len(cs) if ln == n: yield cs else: p1, p2 = sorted(cs[-2:], key=lambda x:x[0]) # place the next coin against the tray edge and # check that it doesn't overlap the other coin p3 = tangent_ce(r, p1, 0 if p1[1] < p2[1] else 4) t = (p3[0] - p2[0]) ** 2 + (p3[1] - p2[1]) ** 2 if t - 4 * r * r < -tol: return yield from gen_nxr(n, r, cs + (p3,)) # place the next coin against the last two and # check that it does not extend beyond the tray p3 = tangent_cc(r, p1, p2) if not 1.0 - tol < p3[1] < 3.0 + tol: return yield from gen_nxr(n, r, cs + (p3,)) # find the minimum length sequences for each end coin position n2ls = {0:(null_length, ())} for cseq in gen_nxr(max_ec + 2, radius, base_coins[model - 1]): for nc, (x, y) in enumerate(cseq[2:], 1): if nc in n2ls.keys() and x + ofs > n2ls[nc][0]: continue n2ls[nc] = x + ofs, cseq[2:nc+2] # remove ends that are not of minimum length ends = {} for nc in sorted(n2ls.keys()): l, cs = n2ls[nc] su = nc < 3 or abs(n2ls[nc-3][0] + rho - n2ls[nc][0]) > tol if su: ends[nc] = n2ls[nc] m = ' ' if su else 'X' t = ', '.join(f"({x:.6f}, {y:.6f})" for x, y in cs) print(f"{nc:2}: {l:16.12f} {m} {t}") print() b2s = defaultdict(list) # the overall length of the tray (in coin diameters) to be considered for s in range(163, 168): # the length in radius units lnth = 2 * s # select two sequences for the ends for n1, n2 in cwr(ends.keys(), 2): (l1, s1), (l2, s2) = ends[n1], ends[n2] # find how many middle sections can be # added between the two ends ends_lth = l1 + l2 xr = lnth - ends_lth q, r = divmod(xr, rho) k = int(q) # calculate the number of coins coins = 3 * k + coin_offset + n1 + n2 if coins >= 2 * int(s) + 1: # space left in coin diameter units ln = (k * rho + ends_lth) / 2 b2s[coins].append((ln, n1 + n2, s, k, f"({n1:2}, {n2:2})")) for nc in sorted(b2s.keys()): print(f"{nc} coins:") lst = 0 for ln, ct, s, k, tcns in sorted(b2s[nc]): # if abs(lst - ln) < tol: # continue # else: # lst = ln print(f" {tcns} + [{k:3}] = {ln:.9f} = {s} - {s-ln:.9f}") |