Square packing is a packing problem where the objective is to determine how many congruent squares can be packed into some larger shape, often a square or circle.
Square packing in a square is the problem of determining the maximum number of unit squares (squares of side length one) that can be packed inside a larger square of side length
but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer
unit squares is known when
is a perfect square (in which case it is
For most of these numbers (with the exceptions only of 5 and 10), the packing is the natural one with axis-aligned squares, and
is the ceiling (round up) function.
[2][3] The figure shows the optimal packings for 5 and 10 squares, the two smallest numbers of squares for which the optimal packing involves tilted squares.
[4][5] The smallest unresolved case is
It is known that 11 unit squares cannot be packed in a square of side length less than
By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.877084 found by Walter Trump.
[4][6] The smallest case where the best known packing involves squares at three different angles is
It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length
[4] Below are the minimum solutions for values up to n=12:[7] (The case for n=11 remains unresolved) For larger values of the side length
, the exact number of unit squares that can pack an
square remains unknown.
grid of axis-aligned unit squares, but this may leave a large area, approximately
[4] Instead, Paul Erdős and Ronald Graham showed that for a different packing by tilted unit squares, the wasted space could be significantly reduced to
[8] Later, Graham and Fan Chung further reduced the wasted space to
[9] However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least
is a half-integer, the wasted space is at least proportional to its square root.
[10] The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem.
[1] Some numbers of unit squares are never the optimal number in a packing.
unit squares, then it must be the case that
[2] Square packing in a circle is a related problem of packing n unit squares into a circle with radius as small as possible.
For this problem, good solutions are known for n up to 35.
Here are the minimum known solutions for up to n=12:[11] (Only the cases n=1 and n=2 are known to be optimal)