Problem of the Month
(March 2013)

Consider an infinite grid of unit squares. We want to place k disks on this grid so that: 1) no two disks cover part of the same unit square and 2) the set of squares that are at least partially covered by a disk form an m×n rectangle. For a given m and n, what is the minimum k that will work? For example, here are the best-known partial coverings for a few rectangles:

What are the answers for large m and n?


ANSWERS

Let f(m,n) be the smallest k that works for a given m and n.

It is easy to show:

f(1,n) = n/2

f(2,n) = n/3

f(3,n) = n/4 for n≥2

f(4,n) = n/5 for n≥3

f(5,n) = n/5 for n≥12

f(6,1) = 3
f(6,6n) = n
f(6,6n+i) = n+2 for 1≤i≤4
f(6,6n+5) = n+3

Joe DeVincentis showed that f(7,6n+i) = 2n+2 for 1≤i≤2 and f(7,6n+i) = 2n+3 for 3≤i≤6.

Joe DeVincentis conjectured that f(8,3n-i) = n+2 for 0≤i&le2 and n≥10. He showed this pattern is eventually optimal, with limiting efficiency 24.

Joe DeVincentis also showed that the width 9 rectangles eventually have period 10 with limiting efficiency 30.

What is the eventual behavior of f(m,n) for larger m?

Smallest-Known Number of Circles Covering m×n Rectangle
m\n1234567891011121314151617181920212223242526272829303132333435
1 11223 34455 66778 8991010 1111
2 11122 23334 44555 66677 78889 99101010 111111
3 21112 22233 33444 45555 66667 77788 88999
4 22111 22222 33333 44444 55555 66666 77777
5 32211 33222 43333 44444 55555 66666 77777
6 32223 13333 42444 45355 55646 66675 77778
7 43223 34445 GS JD JP JG 7 7 JD JD JD JD 9 9 JD JD JD JD 11 11 JD JD
8 43222 34444 5JD666 78888 910101010 11JD
9 53322 34444 55666 7JP888 99JD 1010 JD 11 JD JD JD
10 54322 35444 JP5666 JP7788 88 99JD10101111 11
11 64334 4 GS 5 5 JP JD 5 JD JD JD JD JD 7 JD 8 8 8 9 JP JD JP JP JD 11 JD
12 64333 2 JD JD 5 5 5 4 7 JD 7 7 7 6 JD 9 99989 1111111110 11
13 75433 4JP666 JD7JGJDJD JDJDJDJDJD JD JD JD JD
14 75433 4JG666 JDJDJDJDJD JDJDJGJD JD 11 JD JD JD
15 85433 47666 JD 7JDJD9 EF10JGJDJD JD JD JD JD
16 86444 4777JP JD7JDJDEF JGJDJP JD JD
17 96544 5JD 8JP7 JD7JDJD10 JDJGJPJD
18 96544 3JD887 76JDJGJG JPJP9JD
19 107544 5JD888 JDJDJD JDJD JDJDJD
20 107544 5JD888 89JD JD JD JD
21 117655 59998 89JD 11 JD
22 118655 591098 89JDJD
23 8655 6JD 10JD 9 99JD JDJD
24 8655 4JD10109 JP8JDJDJD
25 9755 6JD1010JD JD9JD
26 9766 6JD11JD 10 JP11
27 9766 611JD1110 JP11
28 10766 611 JD 11JD 11
29 108667 JDJD 111111
30 10866 5JDJD 11 JD 10
31 11877 711
32 11877 7
33 11977 7
34 977 7
35 9778
JD = Joe DeVincentis
JP = Jon Palin
GS = George Sicherman
JG = Jeremy Galvagni
EF = Erich Friedman

Jeremy Galvagni tried to cover a 100×100 square to see whether small, medium, or large circles were most efficient. By using a large circle, he managed a covering with 145 circles. Joe DeVincentis improved this to 129 circles, shown below. Can anyone do better?

Jeremy Galvagni also defined the covering efficiency of a covering as the area covered per circle. He notes that the multiples of the 6×6 packing of one circle all have efficiency 36. He asked for the smallest covering that is more efficient than this. Joe DeVincentis found a covering of a 22×22 square with a higher efficiency, shown below.


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