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 n
100.
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 computer-aided 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
non-decreasing and s(n2)=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 a2+a+3+
By unrotating some rotated squares in the corner, we get alternate packings for n=10, 38, 67,
and 84. (see Figure 2).
It is clear that n+2
Göbel also found that if integers a and
b satisfied a-1<b/
Adding "L"s of squares around the packing of 40 squares gives the best known packings
of 53 and 68 squares. Adding an "L" around the packing of 65 squares gives the best known
packing of 82 squares.
Charles Cottingham, who improved some of Göbel's packings for n
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 n
Note that a diagonal strip of width 2 or 3 must be off center in order to be optimal. Otherwise
one could place at least as many squares by not rotating them.
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.
Diagonal strips of width 4 also give alternative optimal packings of 53 and 68 squares (see
Figure 7).
The best known packings for many values of n are more complicated. Many seem to require
packing with squares at angles other than 0o and 45o. 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.182o, and there is a small gap between these squares.
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((
In 1980, Pertti Hämäläinen improved Göbel's packing of 17
squares using a different arrangement of squares at a 45o angle. But in 1998, John
Bidwell, an undergraduate student at the University of Hawaii, improved this packing (see figure
10). It is the smallest example where the best known packing contains squares at three
different angles.
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)=s2-max{n:s(n)
In [10], Roth and Vaughan establish a
non-trivial lower bound for W(s). They show that if s(s-
It was conjectured that s(n2-n)=n whenever n is small. The smallest known
counterexample of this conjecture, due to Lars Cleemann, is s(172-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 45o, and
the other tilted squares are tilted by an angle of arctan(8/15).
We can generalize the packings in Figure 3
by placing the central square a little off center. We can pack 2a2+2a+b2
squares in a rectangle with sides a+1/2+b/
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 9n2+8n+2 squares in a square
of side 3n+4
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.
Our new packing of 37 squares uses a modified diagonal strip of width 3 (see Figure 16). The
tilted squares contact the other squares in 3 places. The slanted squares are tilted at an agle
of approximately 51.100o. Adding an ``L'' to this packing of 37 squares gives the
best known packing of 50 squares.
Finally, we make the following conjecture:
Conjecture 1. If s(n2-k)=n, then s( (n+1)2-k)=n+1.
That is, if omitting k squares from an n x n square does not admit a smaller packing,
then the same will be true for omitting k squares from any larger perfect square packing.
This is true of all the best known packings.
Lemma 1. Any unit square inside the first quadrant whose center is in
[0,1]2 contains the point (1,1).
Proof: It suffices to show that a unit square in the first quadrant that touches the
x-axis and y-axis contains the point (1,1). If the square is at an angle
Lemma 2. Let 0<x
Proof: It suffices to show that a unit square u whose center is contained in
[1,1+x]x[0,y] that contains the points (1,y) and (1+x,y) on its boundary contains
a point on the x-axis. This is true if (1,y) and (1+x,y) lie on the same side of u.
If u is at an angle
(see Figure 18). This point lies outside the first quadrant when f(
the critical points of f(
Checking these 3 values and the endpoints, the global minimum of f(
Lemma 3. If the center of a unit square u is contained in
Proof: The diagonals of u divide the plane into 4 regions, labeled clockwise
as R1, R2, R3, and R4 (see Figure 19). These regions
are closed, and intersect only on the diagonals. The points A, B, and C cannot all be on one
side of either one of these diagonals, for then
Lemma 4. If the center of a unit square u is contained in the rectangle
R=[0,1]x[0,.4], then u contains a vertex of R.
Proof: Let A=(0,0), B=(0,.4), C=(1,0), and D=(1,.4). It suffices to show
that any u that contains A and B on its boundary and whose center is in R
contains either C or D (see Figure 20). This is clearly the case if A and B lie on the
same side of u. When
Lemma 5. If a unit square has its center below
the line y=1, and is entirely above the x-axis, then the length of the
intersection of the line y=1 with the square is at least 2
Proof: Let L be the line y=1. Since the center of the square is below L, 2 or
fewer corners of the square are above L. If 2 corners are above L, then L
intersects 2 opposite sides of the square, and therefore the intersection has
length at least 1. If none of the corners are above
L, 2 corners sit on the x-axis, and the length of the intersection is exactly 1.
We therefore assume 1 corner is above L. In this case, the intersection is made
smaller by moving the square downwards until one of the corners is touching the
x-axis.
If the square makes an angle
This is minimized when dD/d
Lemma 6. If a unit square has its center in the region
[0,1]2, does not contain either of the points (0,1) and (1,1), and is
entirely above the x-axis, then the square covers some point (0,y) for 1/2
Proof: Lowering the square until it touches the x-axis lowers any points of
intersection with the y-axis. Moving the square right until it touches the point
(1,1) makes any intersection with the y-axis smaller. We will show that any
such square touching the x-axis and the point (1,1) covers some point (0,y) for 1/2
If x is the distance in Figure 22, then sin
Therefore the left corner of
the square is (1 + tan
Since dD/d
Lemma 7. If a unit square has its center in the region [0,1]2, does not
contain either of the points (0,1) or (1,1), and is entirely above the x-axis, then the square
covers either the point (0,
Proof: Lemma 2 shows that the center of the square cannot have y-coordinate less
than or equal to
To show that s(n)
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).
Theorem 2. s(5)=2+1/
Proof: The set P={ (1,1), (1,1+1/
Theorem 3. s(8)=3.
Proof: The set P={ (.9,1), (1.5,1), (2.1,1),
(1.5,1.5), (.9,2), (1.5,2), (2.1,2) } is unavoidable in
[0,3]2 by Lemmas 1, 2, and 3 (see Figure 25).
Theorem 4. s(15)=4.
Proof: The set
is unavoidable in [0,4]2 by
Lemmas 1, 2, 3, and 4 (see Figure 26).
Theorem 5. s(24)=5.
Proof: The set
is unavoidable in [0,5]2 by Lemmas 1, 2, and 3 (see Figure 27).
Theorem 6. s(35)=6.
Proof: The set
is unavoidable in [0,5]2 by Lemmas 1, 2, and 3 (see Figure 28).
The proofs that s(7)=3 and s(14)=4 are a little harder. We find sets of points which are
almost unavoidable, which force squares into certain positions. We use Lemmas 5, 6, and 7
to show that certain regions are covered, and find sets of unavoidable
points for the rest of the square.
Theorem 7. s(7)=3.
Proof: If 7 unit squares are packed in a square of side 3-
There are 2 possible placements of these 2 squares up to rotation and reflection.
Figure 30 shows these possibilities. The shaded trapezoids show points that must be covered by
squares in those regions because of Lemmas 5, 6, and 7. Actually, we have drawn the trapezoids
with a y value of 1/2 in Lemma 6 because this is the worst case in what follows. Each diagram
shows a set of 3 additional unavoidable points.
Theorem 8. s(14)=4.
Proof: If 14 unit squares are packed in a square of side 4-
There are 5 possible placements of these 2 squares up to rotation and reflection.
Figure 32 shows the 5 possibilities.
Each diagram also shows a set of 11 additional unavoidable (or almost
unavoidable) points. Some of these cases have additional cases, and these are shown in Figure
33.
The other lower bounds known are probably not sharp. For example, Trevor Green has shown:
Theorem 9. s(n2+1)
Theorem 10. s(n2+
Unavoidable sets illustrating some of the lower bounds on s(n) are shown in Figure 34.
Table 1 contains the best known upper bounds on s(n) for n
2 Previous Results
(a-1)
squares can be packed in a square of side
a+1+1/ by placing a diagonal strip of squares at a 45o angle.
This gives the best known packings for all values of a except for a=3 (see Figure 1).
s(5)=2+1/
s(10)=3+1/
s(27)5+1/
s(38)6+1/
s(52)7+1/
s(67)8+1/
s(84)9+1/
s(10)=3+1/
s(38)6+1/
s(67)8+1/
s(84)9+1/
s(84)9+1/s(n)+1 squares can be packed in a square of side s(n)+1 by packing n squares inside
a square of side s(n) and putting the other squares in an "L" around it. The packings in
Figure 2 are of this form. Packings not containing an "L" of squares we will call
primitive packings. From now on, we will only illustrate primitive packings.<a+1, then 2a2+2a+b2 squares
can be packed inside a square of side a+1+b/. This is accomplished by
placing a b x b square of squares at a 45o angle in the center. This gives the best
known packings for 28, 40, 65, and 89 squares (see Figure 3).
s(28)3+2
s(40)4+2
s(65)5+5/
s(89)5+7/49, 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.
s(41)2+7/
s(19)3+4/3100 [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.
s(87)(14+11)/3
Figure 6.
s(53)5+2
s(68)6+2
s(11)3.8772
Figure 8.7-1)/4)
24.295o.
s(18)(7+7)/2
s(18)(7+7)/2
s(17)4.6755
s(29)5.9648 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(s7/11). In [10], it is mentioned that Montgomery has improved this result to W(s)=O(s3-3/2+
) for every >0.s)>1/6, then W(s)
10-100(s | s-s+1/2 | ). This implies that W(s) is not
O(s
) when <1/2.
s(272)<17
Figure 11.
3 New Packings and a+3/2+b/. Adding a column of squares to the side of this, we get a packing of
2a2+4a+b2+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).
s(26)(7+3)/2
s(85)11/2+3
s(70)15/2+23
s(88)17/2+ /3 in this fashion.
s(54)6+4/3
s(69)(5+9)/2
s(39)(11+7)/2
s(86)(17+7)/2
s(37)6.6213
Figure 16.
4 Technical Lemmas
,
it contains the points (sin,0) and (0,cos) (see Figure
17). The two other corners of the square, (cos,cos+sin) and (cos+sin,sin), lie on the line y - sin =
-cot (x - sin - cos). In
particular, when x=1, - cos (1 - sin - cos)] / sin = [(1 - sin) (1 - cos) + sin] / sin 1. 
Figure 17.1, 0<y1, and x+2y<2. Then any unit square inside the first quadrant whose center is contained in
[1,1+x]x[0,y] contains either the point (1,y) or the point (1+x,y)., then the lowest corner of the square is) sin - cos , y - (1 - x sin) cos - sin)) = cos + sin - x sin cos > y. Since) = (cos - sin)
[1 - x (cos + sin)],) are ,sin)=(1/,1/) and (cos,sin) = (1 ± (2x2-1) / 2x , 1 
(2x2-1) / 2x).) occurs
at =45o. Therefore, when y<-x/2,
u contains some point of the x-axis.
Figure 18.
ABC,
and each side of the triangle has length no more than 1, then u contains A, B, or C.ABC would not contain
the center of u. Thus either both R1 and R3 contain vertices of the
triangle, or both R2 and R4 do. In either case, two vertices of ABC are closest to two opposite sides of u. Since the distance between these
vertices is no more than 1, u must contain at least one of these points.
Figure 19.=45o, u contains both C and D. It
is easy to see that when <45o, u contains D, and when
>45o, u contains C.
Figure 20.-2. with the x-axis, the vertical line segment
in Figure 21 has length (sin + cos - 1), so the length
of the intersection with L is + cos - 1) (tan + cot) = (sin + cos - 1) / (sin cos). =
(sin - cos) (1 - cos) (1 - sin) / (cos2 sin2) = 0, which occurs at
=45o. Thus D2-2.
Figure 21.y1 and some point (1,y) for 1/2y1.y1. The rest of the lemma follows from symmetry. + x cos =
1, or x = (1 - sin) / cos. This means the x-intercept
of the square is - cos = 1 + tan (1 - sin) - cos. (1 - sin) - cos - sin , cos). This means the
largest y-intercept of the square is - tan (1 + tan (1 - sin) - cos - sin) =
(cos3 + sin (1 - cos) (1 - sin)) /
cos2. = (1 - cos - sin) (1 - sin) / cos3 < 0,
the minimum value of
D is the limit of D as approaches
90o, which is 1/2 by L' Hôpital's Rule.
Figure 22.-1/2) or the point (1,-1/2).-1/2 without covering one of these points. Lemma 4
shows that the center of the square cannot have y-coordinate more than -1/2 without covering one of these points.
5 Lower Boundsk, we will modify a method used by Walter Stromquist [13]. We will find a set P of (n-1) 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 (n-1)
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 (n-1) non-overlapping 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.
s(2)2
Figure 23..), (1+1/,1),
(1+1/,1+1/) } is unavoidable in
[0,2+1/]2. This follows from Lemma 1 if the center of the
square is in a corner, from Lemma 2 if it is near a sides, and from Lemma 3 if it is in a
triangle (see Figure 24).
s(5)2+1/
Figure 24.
s(8)3
Figure 25.
s(15)4
Figure 26.
s(24)5
Figure 27.
s(35)6
Figure 28., at most 5
squares cover the 5 points in the almost unavoidable set shown in Figure 29. Therefore at
least two squares have their centers in the regions containing question marks.
Figure 29.
, at most 12
squares cover the 12 points in the almost unavoidable set shown in Figure 31. Therefore at
least two squares have their centers in the regions containing question marks.
Figure 31.
2 -
1 + (n(n-1)2 + (n-1)*(2n)) / (n2+1).n/2+1) 2 + 2(n-2)/5.
s(6)2
s(10)2+(1+6)/5
s(11)2+2/5
s(17)(40+19)/17
s(19)6-4
Appendix100.
For each primitive packing, the Figure and the Author are given. We conjecture that most of these
packings are optimal. The packings most likely to be improved include n=50, 51, 55, and 71.
n s(n) Optimal? Figure Author 1 1 
2-4 2 5 2+1/ 2.7072Figure 1 Göbel 6-9 3 10 3+1/ 3.7072 Figure 1 Göbel 11 3.8772 Figure 8 Trump 12-13 4 14-16 4 17 4.6755 Figure 10 Bidwell 18 7/2+1/2 74.8229 Figure 9 Hämäläinen 19 3+4/3 4.8857 Figure 4 Wainwright 20-23 5 24-25 5 26 7/2+3/2 5.6214 Figure 12 Friedman 27 5+1/ 5.7072 Figure 1 Göbel 28 3+2 5.8285 Figure 3 Göbel 29 5.9648
Figure 10 Bidwell 30-34 6 35-36 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+2 6.8285 Figure 3 Göbel 41 2+7/ 6.9498 Figure 4 Cottingham 42-48 7 49 7 50 7.6213 51-52 7+1/ 7.7072 Figure 1 Göbel 53 5+2 7.8285 Figure 7 Stenlund 54 6+4 /37.8857 Figure 14 Friedman 55-63 8 64 8 65 5+5/ 8.5356 Figure 3 Göbel 66 3+4 8.6569 Figure 5 Stenlund 67 8+1/ 8.7072 Figure 1 Göbel 68 6+2 8.8285 Figure 7 Stenlund 69 5/2+9/ 8.8640 Figure 14 Friedman 70 15/2+ 8.9143 Figure 13 Friedman 71-80 9 81 9 82 6+5/ 9.5356 83 4+4 9.6569 84 9+1/ 9.7072 Figure 1 Göbel 85 11/2+3 9.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 90-99 10 100 10
Table 2 contains the best known non-trivial lower bounds on s(n) for n100,
along with the Author.
n s(n) Figure Author 2-3 2 Figure 23 Göbel 5 2+1/ 2.7071Figure 24 Göbel 6 3 Kearney and
Shiu 7 3 Figure 29 Friedman 8 3 Figure 25 Friedman 10 2 +(1+6)/53.5183Figure 34 Green 11-12 2 +2/53.7228Figure 34 Green 13 3.8437 Friedman 14 4 Figure 31 Friedman 15 4 Figure 26 Friedman 17-18 (40 +19)/174.4452Figure 34 Green 19-20 6 -44.4852Figure 34 Friedman 21 4.7438 Friedman 22-23 2 +24.8284 Green 24 5 Figure 27 Friedman 26-27 2 +(27+210)/135.3918 Green 28-30 2 +6/55.5117 Green 31 5.6415 Green 35 6 Figure 28 Friedman 37-39 2 +(113+103)/376.3506 Green 40-41 2 +8/56.4061 Green 50-53 2 +(101+314)/257.3174 Green 65-68 2 +71/138.2899 Green 82-85 2 +(288+123)/419.2667 Green