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?


ANSWERS

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


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

Best Known Coverings of a Square by n 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:

Best Known Coverings of a Equilateral Triangle by n 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)


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

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 = 1
Trivial.
r = 3
Trivial.
r = 5
Trivial.

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

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

10.            11.            12.
r = 22.000193+
Found by Steve Trevorrow
in November 2005.
r = 24.960634+
Found by Gerrit de Blaauw
in October 2005.
r = 28.371389+
Found by Steve Trevorrow
in November 2005.

13.            14.            15.
r = 31.545867+
Found by Steve Trevorrow
in November 2005.
r = 35.095647+
Found by Tomas Rokicki
in November 2005.
r = 38.837995+
Found by Tomas Rokicki
in November 2005.

16.            17.            18.
r = 42.458116+
Found by Tomas Rokicki
in November 2005.
r = 46.291242+
Found by Tomas Rokicki
in November 2005.
r = 50.119762+
Found by Boris von Loesch
in November 2005.

19.            20.            21.
r = 54.240293+
Found by Tomas Rokicki
in November 2005.
r = 58.400567+
Found by Addis Locatelli and Schoen
in November 2005.
r = 62.558877+
Found by Boris von Loesch
in November 2005.

22.            23.
r = 66.760286+
Found by Tomas Rokicki
in November 2005.
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.