# Problem of the Month (October 2005)

This month we consider 4 problems concerning circles.

1. Packing Circles with Two Different Sized Circles

Given positive integers 1<m≤n, we wish to pack m circles of one size and n circles of another size into a unit circle so that the total area of the circles is maximized. What are the maximal area packings for various m and n? The corresponding problem for squares was the problem of the month in April 2000. What are the best solutions for packing circles in a square or squares in a circle?

2. Covering a Square with Circles of Any Size

The problem of covering a unit square with n circles of equal size has been well studied. You can the best known solutions here. A variant of this problem is to cover a unit square with n circles of any size and minimal combined area. What are the minimal covers for various n? What are the minimal circle covers of an equilateral triangle of length 1?

3. Packing Discrete Circles on a Square Torus

Say we have circles of diameter d, all centered at half lattice points, packed inside a square torus with side n. If d and n are fixed, how many non-overlapping circles C(n,d) will fit? For each n, C(n,d) is a non-increasing piecewise constant function of d, which can be illustrated by exhibiting the packings at the discontinuities. For example, for n=5, the discontinuities occur for d=1, √2, √5, 2√2, and 5. For each n, can you find the discontinuities of C(n,d), and the value of C(n,d) at those points? It is clear that C(n,1)=n2 and C(n,n)=1 are always discontinuities. What other general formulas are true?

4. Packing Circles of Radii 1, 2, 3, . . ., n in a Circle.

What is the smallest Circle that contains non-overlapping circles of radii 1, 2, 3, . . ., n?

1. Here are the best known two circle packings:

Best Known Packings of m equal Circles and n equal Circles in a Circle
 m=2, n=2area 13π/18 = 2.268+ m=2, n=3area 2.345+(David W. Cantrell) m=2, n=4area 3π/4 = 2.356+
 m=2, n=5area 7π/9 = 2.443+(David W. Cantrell) m=2, n=6area 2.438+(David W. Cantrell) m=3, n=3area 2.502+
 m=3, n=4area 2.445+(David W. Cantrell) m=3, n=5area 2.459+ m=3, n=6area 2.537+(Philippe Fondanaiche)

 m=3, n=8, 9area 2.537+, 2.601+(Philippe Fondanaiche) m=4, n=4, 5area = 2.525+, 2.618+ m=4, n=6area = 2.523+(David W. Cantrell)

 m=4, n=8, 9area = 2.541+, 2.590+(Philippe Fondanaiche) m=5, n=5, 6, 7area 2.459+, 2.520+, 2.662+(David W. Cantrell)

 m=6, n=6area = 2.531+(David W. Cantrell) m=2, 3, 4, 5, 6, n=7area 2.531+, 2.575+, 2.662+, 2.618+, 2.706+(David W. Cantrell, Maurizio Morandi)

2. Here are the best known coverings of a square by circles:

Best Known Coverings of a Square by n Circles
 n=1area π/2 = 1.570+ n=3area 1.442+ n=4area 1.397+
 n=5area 5π/12 = 1.309+ n=6area 1.2965+(David W. Cantrell) n=7area 1.2813+(Philippe Fondanaiche)

 n=8area 1.2687+(David W. Cantrell) n=9area 1.2558+(David W. Cantrell) n=13area 1.185+

And here are the best known coverings of a equilateral triangle by circles:

Best Known Coverings of a Equilateral Triangle by n Circles
 n=1area π/3 = 1.047+ n=2area 7π/24 = .916+(Hans Melissen) n=3area π/4 = .785+(Hans Melissen)
 n=4area 5π/24 = .654+(Hans Melissen) n=5area .644+(David W. Cantrell)

 n=6area .630+(David W. Cantrell) n=7area .624+(David W. Cantrell)

3. Here are the small discontinuities of discrete packings of circles on a torus:

n=1, d=1

1 circle
 n=2, d=14 circles n=2, d=√22 circles n=2, d=21 circle
 n=3, d=19 circles n=3, d=√23 circles n=3, d=21 circle

 n=4, d=116 circles n=4, d=√28 circles n=4, d=24 circles n=4, d=2√22 circles n=4, d=41 circle

 n=5, d=125 circles n=5, d=√210 circles n=5, d=√55 circles n=5, d=2√22 circles n=5, d=51 circle

 n=6, d=136 circles n=6, d=√218 circles n=6, d=29 circles n=6, d=√56 circles n=6, d=34 circles n=6, d=3√22 circles n=6, d=61 circle

 n=7, d=149 circles n=7, d=√221 circles n=7, d=210 circles n=7, d=√58 circles n=7, d=2√25 circles n=7, d=√104 circles n=7, d=3√22 circles n=7, d=71 circle

 n=8, d=164 circles n=8, d=√232 circles n=8, d=216 circles n=8, d=√510 circles n=8, d=2√28 circles n=8, d=44 circles n=8, d=2√53 circles n=8, d=4√22 circles n=8, d=81 circle

 n=9, d=181 circles n=9, d=√236 circles n=9, d=216 circles n=9, d=√513 circles n=9, d=39 circles n=9, d=√106 circles n=9, d=√135 circles n=9, d=√174 circles n=9, d=3√23 circles n=9, d=4√22 circles n=9, d=91 circle

 n=10, d=1100 circles n=10, d=√250 circles n=10, d=225 circles n=10, d=√520 circles n=10, d=2√212 circles n=10, d=√1010 circles n=10, d=√137 circles n=10, d=2√55 circles n=10, d=54 circles n=10, d=√263 circles n=10, d=5√22 circles n=10, d=101 circle

 n=11, d=1121 circles n=11, d=√260 circles n=11, d=225 circles n=11, d=√521 circles n=11, d=2√213 circles n=11, d=√1010 circles n=11, d=√138 circles n=11, d=√176 circles n=11, d=2√55 circles n=11, d=√264 circles n=11, d=5√22 circles n=11, d=111 circle

It is clear that C(n,1)=n2 and C(n,n)=1 are always discontinuities.

Joseph DeVincentis noted that the possible discontinuities are square roots of the sum of two squares of integers, and showed C(n,√2)=n n/2 and C(n, n/2 √2)=2 are always discontinuities for n≥4. He also showed that C(2n,2)=n2, but wasn't sure this was a discontinuity.

4. The Al Zimmerman Programming Contest featured this problem. The best results for small n are shown below. Fixed circles are shown in blue, and rattlers are shown in purple.

 1. 2. 3. r = 1Trivial. r = 3Trivial. r = 5Trivial.

 4. 5. 6. r = 7Trivial. r = 9.001397+Found by Klaus Nagel and Hugo Pfoertnerin October 2005. r = 11.057040+Found by Fred Mellenderin October 2005.

 7. 8. 9. r = 13.462110+Found by Gerrit de Blaauwin October 2005. r = 16.221746+Found by Gerrit de Blaauwin October 2005. r = 19.233193+Found by Gerrit de Blaauwin October 2005.

 10. 11. 12. r = 22.000193+Found by Steve Trevorrowin November 2005. r = 24.960634+Found by Gerrit de Blaauwin October 2005. r = 28.371389+Found by Steve Trevorrowin November 2005.

 13. 14. 15. r = 31.545867+Found by Steve Trevorrowin November 2005. r = 35.095647+Found by Tomas Rokickiin November 2005. r = 38.837995+Found by Tomas Rokickiin November 2005.

 16. 17. 18. r = 42.458116+Found by Tomas Rokickiin November 2005. r = 46.291242+Found by Tomas Rokickiin November 2005. r = 50.119762+Found by Boris von Loeschin November 2005.

 19. 20. 21. r = 54.240293+Found by Tomas Rokickiin November 2005. r = 58.400567+Found by Addis Locatelli and Schoenin November 2005. r = 62.558877+Found by Boris von Loeschin November 2005.

 22. 23. r = 66.760286+Found by Tomas Rokickiin November 2005. r = 71.199461+Found by Boris von Loeschin December 2005.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 7/14/07.