THE ELECTRONIC
JOURNAL OF COMBINATORICS
7 (2000), DS#7.
Abstract
Let s(n) be the side of the smallest square into which we can pack n unit squares. We improve the best known upper bounds for s(n) when n = 26, 37, 39, 50, 54, 69, 70, 85, 86, and 88. We present relatively simple proofs for the values of s(n) when n = 2, 3, 5, 8, 15, 24, and 35, and more complicated proofs for n=7 and 14. We also prove many other lower bounds for various s(n). We also give the best known packings for n100.
1 Introduction
The problem of packing equal circles in a square has been around for some 30 years and has seen much recent progress [2]. The problem of packing equal squares in a square is less well known. Results seem to be more difficult, as the computeraided methods available for circles do not generalize for squares. We intend to give some packings which improve upon those in the literature, illustrate a technique for obtaining lower bounds, and exhibit the best known packings for less than one hundred squares.
Let s(n) be the side of the smallest square into which we can pack n unit squares. It is clear that n s(n) n, the first inequality coming from area considerations, and the second coming from the facts that s(n) is nondecreasing and s(n^{2})=n. It is not hard to show that s(2)=s(3)=2. It is a little harder to show that s(5)=2+1/ [7].
The number of claims far outweighs the number of published results in this area. Göbel says that Schrijver claims that Bajmóoczy proved s(7)=s(8)=3 [7]. Walter Stromquist claimed to have proved s(6)=3 and s(10)=3+1/, and claimed to know how to prove s(14)=s(15)=4 and s(24)=5 [13]. Said El Moumni recently claimed to have proved s(6)=s(7)=s(8)=3 and s(14)=s(15)=4 [12]. None of these proofs have been published. Finally, in 2002, Kearney and Shiu published a proof of s(6)=3 [9]. We prove all the known values of s(n) for n not equal to 6: square n and n=2, 3, 5, 7, 8, 14, 15, 24, and 35. There are many other good packings thought to be optimal, but as of yet no proofs.
Previous results can be found in Section 2. Our improved packings appear in Section 3. In Section 4 we prove some technical lemmas that we use in Section 5 to prove the values of s(n) mentioned above. Lists of the best known upper and lower bounds for s(n) are given in the Appendix. Many of the results given are taken from unpublished letters and manuscripts, and private communications.
Göbel was the first to publish on the subject [7]. He found that a^{2}+a+3+(a1) squares can be packed in a square of side a+1+1/ by placing a diagonal strip of squares at a 45^{o} angle. This gives the best known packings for all values of a except for a=3 (see Figure 1).



Charles Cottingham, who improved some of Göbel's packings for n49, was the first to use diagonal strips of width 2 [6]. In 1979, he found the best known packing of 41 squares (see Figure 4). Although it is hard to see, the diagonal squares touch only the squares in the upper right and lower left corners.
Soon after Cottingham produced a packing of 19 squares with a diagonal strip of width 2, Robert Wainwright improved Cottingham's packing slightly (see Figure 4) [4]. This is still the best known packing of 19 squares.

In 1980, Evert Stenlund improved many of Cottingham's packings, and provided packings for n100 [6]. His packing of 66 squares uses a diagonal strip of width 3 (see Figure 5). In this packing, the diagonal squares touch only the squares in the upper right and lower left corners. Adding an "L" to this packing gives the best known packing of 83 squares.
s(66)3+4 Figure 5. 
Stenlund also modified a diagonal strip of width 4 to pack 87 squares (see Figure 6). There is a thin space between two of the diagonal strips. Compare this with the packing of 19 squares in Figure 4.
s(87)(14+11)/3 Figure 6. 

The best known packings for many values of n are more complicated. Many seem to require packing with squares at angles other than 0^{o} and 45^{o}. In 1979, Walter Trump improved Göbel's packing of 11 squares (see Figure 8). Many people have independently discovered this packing. The original discovery has been incorrectly attributed to Gustafson and Thule [11]. The middle squares are tilted about 40.182^{o}, and there is a small gap between these squares.
s(11)3.8772 Figure 8. 
In 1980, Hämäläinen improved on Göbel's packing of 18 squares (see Figure 9) [6]. In 1981, Mats Gustafson found an alternative optimal packing of 18 squares (see Figure 9). The middle squares in these packings are tilted by an angle of arcsin((71)/4)24.295^{o}.

Also in 1998, I improved the best known packing of 29 squares using a modified diagonal strip of width 2. A few months later, Bidwell improved my packing slightly (see figure 10) [1].

In [3], Erdös and Graham define W(s)=s^{2}max{n:s(n)s}. Thus W(s) is the wasted area in the optimal packing of unit squares into an s x s square. They show (by constructing explicit packings) that W(s)=O(s^{7/11}). In [10], it is mentioned that Montgomery has improved this result to W(s)=O(s^{33/2+} ) for every >0.
In [10], Roth and Vaughan establish a nontrivial lower bound for W(s). They show that if s(ss)>1/6, then W(s)10^{100}(s  ss+1/2  ). This implies that W(s) is not O(s^{}) when <1/2.
It was conjectured that s(n^{2}n)=n whenever n is small. The smallest known counterexample of this conjecture, due to Lars Cleemann, is s(17^{2}17)<17. 272 squares can be packed into a square of side 17 in such a way that the the square can be squeezed together slightly (see Figure 11). Three squares are tilted by an angle of 45^{o}, and the other tilted squares are tilted by an angle of arctan(8/15).
s(272)<17 Figure 11. 
We can generalize the packings in Figure 3 by placing the central square a little off center. We can pack 2a^{2}+2a+b^{2} squares in a rectangle with sides a+1/2+b/ and a+3/2+b/. Adding a column of squares to the side of this, we get a packing of 2a^{2}+4a+b^{2}+1 squares in a square of side a+3/2+b/. This gives the best known packings for 26 and 85 squares (see Figure 12).

We can generalize Stenlund's packing of 41 squares in Figure 4 to packings of 70 and 88 squares (see Figure 13).

We can modify a diagonal strip of 2 squares to get an optimal packing of 54 squares (see Figure 14). Compare this with the packing of 19 squares in Figure 4. We can pack 9n^{2}+8n+2 squares in a square of side 3n+4/3 in this fashion.
We can also modify a strip of width 4 to get the best known packing of 69 squares by enlarging the bounding square and rearranging the upper right hand corner (see Figure 14). The diagonal squares touch only the squares in the upper right and lower left corners.

We can generalize the packings in Figure 9 to provide the best known packings of 39 and 86 squares (see Figure 15). The angle of the tilted squares is the same as in that Figure.

s(37)6.6213 Figure 16. 
Finally, we make the following conjecture:
Conjecture 1. If s(n^{2}k)=n, then s( (n+1)^{2}k)=n+1.
Figure 17. 
the critical points of f() are
Figure 18. 
Figure 19. 
Figure 20. 
Figure 21. 
Figure 22. 
To show that s(n)k, we will modify a method used by Walter Stromquist [13]. We will find a set P of (n1) points in a square S of side k so that any unit square in S contains an element of P (possibly on its boundary). Shrinking these by a factor of (1/k) gives a set P' of (n1) points in a square S' of side (k) so that any unit square in S' contains an element in P' in its interior. Therefore no more than (n1) nonoverlapping squares can be packed into a square of side (k), and s(n)>k. Since this is true for all >0, we must have s(n)k.
We call P a set of unavoidable points in S. We now prove lower bounds on s(n) by showing that certain sets of points are unavoidable.
Theorem 1. s(2)=s(3)=2.
Proof: Consider a unit square u in [0,2]^{2}. Since the center of u is either in [0,1]^{2} or [0,1]x[1,2] or [1,2]x[0,1] or [1,2]^{2}, Lemma 1 shows that u contains the point (1,1). That is, the set P={ (1,1) } is unavoidable in [0,2]^{2} (see Figure 23).
s(2)2 Figure 23. 
s(5)2+1/ Figure 24. 
s(8)3 Figure 25. 
is unavoidable in [0,4]^{2} by Lemmas 1, 2, 3, and 4 (see Figure 26).
s(15)4 Figure 26. 
is unavoidable in [0,5]^{2} by Lemmas 1, 2, and 3 (see Figure 27).
s(24)5 Figure 27. 
is unavoidable in [0,5]^{2} by Lemmas 1, 2, and 3 (see Figure 28).
s(35)6 Figure 28. 
Figure 29. 

Figure 31. 


The other lower bounds known are probably not sharp. For example, Trevor Green has shown:
Theorem 9. s(n^{2}+1) 2  1 + (n(n1)^{2} + (n1)*(2n)) / (n^{2}+1).
Theorem 10. s(n^{2}+n/2+1) 2 + 2(n2)/5.
Unavoidable sets illustrating some of the lower bounds on s(n) are shown in Figure 34.

n  s(n)  Optimal?  Figure  Author 
1  1  
24  2  
5  2+1/2.7072  Figure 1  Göbel  
69  3  
10  3+1/3.7072  Figure 1  Göbel  
11  3.8772  Figure 8  Trump  
1213  4  
1416  4  
17  4.6755  Figure 10  Bidwell  
18  7/2+1/274.8229  Figure 9  Hämäläinen  
19  3+4/34.8857  Figure 4  Wainwright  
2023  5  
2425  5  
26  7/2+3/25.6214  Figure 12  Friedman  
27  5+1/5.7072  Figure 1  Göbel  
28  3+25.8285  Figure 3  Göbel  
29  5.9648  Figure 10  Bidwell  
3034  6  
3536  6  
37  6.6213  Figure 16  Friedman  
38  6+1/6.7072  Figure 1  Göbel  
39  11/2+7/26.8229  Figure 15  Friedman  
40  4+26.8285  Figure 3  Göbel  
41  2+7/6.9498  Figure 4  Cottingham  
4248  7  
49  7  
50  7.6213  
5152  7+1/7.7072  Figure 1  Göbel  
53  5+27.8285  Figure 7  Stenlund  
54  6+4/37.8857  Figure 14  Friedman  
5563  8  
64  8  
65  5+5/8.5356  Figure 3  Göbel  
66  3+48.6569  Figure 5  Stenlund  
67  8+1/8.7072  Figure 1  Göbel  
68  6+28.8285  Figure 7  Stenlund  
69  5/2+9/8.8640  Figure 14  Friedman  
70  15/2+8.9143  Figure 13  Friedman  
7180  9  
81  9  
82  6+5/9.5356  
83  4+49.6569  
84  9+1/9.7072  Figure 1  Göbel  
85  11/2+39.7427  Figure 12  Friedman  
86  17/2+7/29.8229  Figure 15  Friedman  
87  14/3+11/39.8522  Figure 6  Stenlund  
88  17/2+9.9143  Figure 13  Friedman  
89  5+7/9.9498  Figure 3  Stenlund  
9099  10  
100  10 
n  s(n)  Figure  Author 
23  2  Figure 23  Göbel 
5  2+1/2.7071  Figure 24  Göbel 
6  3  Kearney and Shiu  
7  3  Figure 29  Friedman 
8  3  Figure 25  Friedman 
10  2+(1+6)/53.5183  Figure 34  Green 
1112  2+2/53.7228  Figure 34  Green 
13  3.8437  Friedman  
14  4  Figure 31  Friedman 
15  4  Figure 26  Friedman 
1718  (40+19)/174.4452  Figure 34  Green 
1920  644.4852  Figure 34  Friedman 
21  4.7438  Friedman  
2223  2+24.8284  Green  
24  5  Figure 27  Friedman 
2627  2+(27+210)/135.3918  Green  
2830  2+6/55.5117  Green  
31  5.6415  Green  
35  6  Figure 28  Friedman 
3739  2+(113+103)/376.3506  Green  
4041  2+8/56.4061  Green  
5053  2+(101+314)/257.3174  Green  
6568  2+71/138.2899  Green  
8285  2+(288+123)/419.2667  Green 
[1] J. Bidwell, 1998, private communication.
[4] M. Gardner, "Mathematical Games", Scientific American (Oct 1979, Nov 1979, Mar 1980, Nov 1980).
[6] M. Gardner, 1998, private communication.
[8] T. Green, 2000, private communication.
[11] "Problem Ronden", Ronden (Apr 1980, Sep 1980, Dec 1980)
[12] S. El Moumni, 1999, private communication.
[13] W. Stromquist, "Packing Unit Squares Inside Squares III", unpublished manuscript, 1984.