# 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|} \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 \\

\hline 5 & 6.950852 \\

\hline 6 & 7.948380 \\

\hline 7 & 8.937211 \\

\hline 8 & 9.932821 \\

\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. 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 (16, 16) & 99 & 163.997397 & 0.002603 \\

\hline (13, 16) & 100 & 163.997611 & 0.002389 \\

\hline (14, 24) & 97 & 163.997789 & 0.002211 \\

\hline (13, 13) & 101 & 163.997826 & 0.002174 \\

\hline (14, 15) & 100 & 163.997833 & 0.002167 \\

\hline \end{array} \]

Comparing these with those reported by Jim Randell on this page, there is agreement on the solution with the most free space but I find other solutions with more free space than the five that Jim reports (in fact I find 11 solutions with more free space than 1000th of a coin width). I believe this difference arises because I develop end configurations in a way (described earlier) that produces fully optimised minimum end lengths whereas Jim only considers a limited number of end configurations.

Although I can sometimes find more space in this way, sadly this is not enough to achieve a solution for 163.

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 |
from itertools import combinations_with_replacement as cwr from collections import defaultdict from math import sqrt, atan2, sin, cos # this value is the length of the triple of circles # containing two full circles and two half circles rho = 1 + sqrt(4 * sqrt(3) - 3) # 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 # recursively place <n> coins into the tray for the # endpoint sequences. The (x, y) positions of coin # centres are returned relative to the centre-line # of the last complete triangular triple. def gen_nxr(n, cs=()): ln = len(cs) if ln == n: yield cs else: # initialise with coins B and C | B |D F| # from the last complete triple |A C| E | if not cs: p2 = (1, 1) p1 = tangent_cc(1, p2, (-1, 1)) else: p1, p2 = cs[-2:] # tangent to top edge of tray d = tangent_ce(1, p1, 4) # tangent to bottom edge of tray e = tangent_ce(1, p2, 0) # move D down to tangent B and C (and check it) dd = tangent_cc(1, p2, p1) if not 1.0 <= dd[1] <= 3.0: return # move E up to tangent to C and D (and check it) eu = tangent_cc(1, p2, d) if not 1.0 <= eu[1] <= 3.0: return # proceed to the next two coins starting # with the three initial coin positions yield from gen_nxr(n, cs + (d, e)) yield from gen_nxr(n, cs + (d, eu)) yield from gen_nxr(n, cs + (dd, e)) # find the minimum length sequences for each end coin # position; to return end lengths relative the the # centre-line of the last complete triple set ofs = 1; # to return lengths relative to the right hand end of # the last complete triple set ofs = -1; max_c is the # maximum number of coins in the ends computed ofs = 1 max_c = 20 # this is the length of a 'null' end n2ls = {0:(2,())} for cseq in gen_nxr(max_c): for nc, (x, y) in enumerate(cseq, 1): if nc in n2ls.keys() and x + ofs > n2ls[nc][0]: continue n2ls[nc] = x + ofs, cseq[:nc] for nc in sorted(n2ls.keys()): l, cs = n2ls[nc] t = ', '.join(f"({x:.6f}, {y:.6f})" for x, y in cs) print(f"{nc:2}: {l:9.6f}, {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(n2ls.keys(), 2): (l1, s1), (l2, s2) = n2ls[n1], n2ls[n2] # find how many middle sections can be # added between the two ends xr = lnth - l1 - l2 k = int(xr / rho) # calculate the number of coins coins = 3 * (k + 1) + n1 + n2 if coins >= lnth + 1: # space left in coin diameter units ln = s - (k * rho + l1 + l2) / 2 b2s[coins].append((n1 + n2, ln, s, k, f"({n1:2}, {n2:2})")) for nc in sorted(b2s.keys()): print(f"{nc} coins:") lst = 0 for nt, ln, s, k, tcns in sorted(b2s[nc]): t = int(1e9 * ln) if t == lst: continue else: lst = t print(f" {tcns} + [{k + 1}] + {ln:.6f} = {s}") |