Problem #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?

Problem #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 see 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?

Problem #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)=n² and C(n,n)=1 are always discontinuities. What other general formulas are true?

Problem #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?

Here are the best known two circle packings:

m=2, n=2 area 13π/18 = 2.268+

m=2, n=3 area 2.345+ (David W. Cantrell)

m=2, n=4 area 3π/4 = 2.356+

m=2, n=5 area 7π/9 = 2.443+ (David W. Cantrell)

m=2, n=6 area 2.438+ (David W. Cantrell)

m=3, n=3 area 2.502+

m=3, n=4 area 2.445+ (David W. Cantrell)

m=3, n=5 area 2.459+

m=3, n=6 area 2.537+ (Philippe Fondanaiche)

m=3, n=8, 9 area 2.537+, 2.601+ (Philippe Fondanaiche)

m=4, n=4, 5 area = 2.525+, 2.618+

m=4, n=6 area = 2.523+ (David W. Cantrell)

m=4, n=8, 9 area = 2.541+, 2.590+ (Philippe Fondanaiche)

m=5, n=5, 6, 7 area 2.459+, 2.520+, 2.662+ (David W. Cantrell)

m=6, n=6 area = 2.531+ (David W. Cantrell)

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

Problem #2:

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

n=1 area π/2 = 1.570+

n=3 area 1.442+

n=4 area 1.397+

n=5 area 5π/12 = 1.309+

n=6 area 1.2965+ (David W. Cantrell)

n=7 area 1.2813+ (Philippe Fondanaiche)

n=8 area 1.2687+ (David W. Cantrell)

n=9 area 1.2558+ (David W. Cantrell)

n=13 area 1.185+

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

n=1 area π/3 = 1.047+

n=2 area 7π/24 = .916+ (Hans Melissen)

n=3 area π/4 = .785+ (Hans Melissen)

n=4 area 5π/24 = .654+ (Hans Melissen)

n=5 area .644+ (David W. Cantrell)

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

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

Problem #3:

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

n=1, d=1 1 circle

n=2, d=1 4 circles n=2, d=√2 2 circles n=2, d=2 1 circle

n=3, d=1 9 circles n=3, d=√2 3 circles n=3, d=2 1 circle

n=4, d=1 16 circles n=4, d=√2 8 circles n=4, d=2 4 circles n=4, d=2√2 2 circles n=4, d=4 1 circle

n=5, d=1 25 circles n=5, d=√2 10 circles n=5, d=√5 5 circles n=5, d=2√2 2 circles n=5, d=5 1 circle

n=6, d=1 36 circles n=6, d=√2 18 circles n=6, d=2 9 circles n=6, d=√5 6 circles n=6, d=3 4 circles n=6, d=3√2 2 circles n=6, d=6 1 circle

n=7, d=1 49 circles n=7, d=√2 21 circles n=7, d=2 10 circles n=7, d=√5 8 circles n=7, d=2√2 5 circles n=7, d=√10 4 circles n=7, d=3√2 2 circles n=7, d=7 1 circle

n=8, d=1 64 circles n=8, d=√2 32 circles n=8, d=2 16 circles n=8, d=√5 10 circles n=8, d=2√2 8 circles n=8, d=4 4 circles n=8, d=2√5 3 circles n=8, d=4√2 2 circles n=8, d=8 1 circle

n=9, d=1 81 circles n=9, d=√2 36 circles n=9, d=2 16 circles n=9, d=√5 13 circles n=9, d=3 9 circles n=9, d=√10 6 circles n=9, d=√13 5 circles n=9, d=√17 4 circles n=9, d=3√2 3 circles n=9, d=4√2 2 circles n=9, d=9 1 circle

n=10, d=1 100 circles n=10, d=√2 50 circles n=10, d=2 25 circles n=10, d=√5 20 circles n=10, d=2√2 12 circles n=10, d=√10 10 circles n=10, d=√13 7 circles n=10, d=2√5 5 circles n=10, d=5 4 circles n=10, d=√26 3 circles n=10, d=5√2 2 circles n=10, d=10 1 circle

n=11, d=1 121 circles n=11, d=√2 60 circles n=11, d=2 25 circles n=11, d=√5 21 circles n=11, d=2√2 13 circles n=11, d=√10 10 circles n=11, d=√13 8 circles n=11, d=√17 6 circles n=11, d=2√5 5 circles n=11, d=√26 4 circles n=11, d=5√2 2 circles n=11, d=11 1 circle

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)=n², but wasn't sure this was a discontinuity.

Problem #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. r = 1 Trivial.	2. r = 3 Trivial.	3. r = 5 Trivial.	4. r = 7 Trivial.
5. r = 9.001397+ Found by Klaus Nagel and Hugo Pfoertner in October 2005.	6. r = 11.057040+ Found by Fred Mellender in October 2005.	7. r = 13.462110+ Found by Gerrit de Blaauw in October 2005.	8. r = 16.221746+ Found by Gerrit de Blaauw in October 2005.
9. r = 19.233193+ Found by Gerrit de Blaauw in October 2005.	10. r = 22.000193+ Found by Steve Trevorrow in November 2005.	11. r = 24.960634+ Found by Gerrit de Blaauw in October 2005.	12. r = 28.371389+ Found by Steve Trevorrow in November 2005.
13. r = 31.545867+ Found by Steve Trevorrow in November 2005.	14. r = 35.095647+ Found by Tomas Rokicki in November 2005.	15. r = 38.837995+ Found by Tomas Rokicki in November 2005.	16. r = 42.458116+ Found by Tomas Rokicki in November 2005.
17. r = 46.291242+ Found by Tomas Rokicki in November 2005.	18. r = 50.119762+ Found by Boris von Loesch in November 2005.	19. r = 54.240293+ Found by Tomas Rokicki in November 2005.	20. r = 58.400567+ Found by Addis Locatelli and Schoen in November 2005.
21. r = 62.558877+ Found by Boris von Loesch in November 2005.	22. r = 66.760286+ Found by Tomas Rokicki in November 2005.	23. r = 71.199461+ Found by Boris von Loesch in 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.