Square packing explained
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
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
. If
is an
integer, the answer is
but the precise – or even
asymptotic – amount of unfilled space for an arbitrary non-integer
is an open question.
The smallest value of
that allows the packing of
unit squares is known when
is a perfect square (in which case it is
), as well as for
2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, and 48. 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
, where
is the
ceiling (round up) function.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.
The smallest unresolved case is
. It is known that 11 unit squares cannot be packed in a square of side length less than
style2+2\sqrt{4/5} ≈ 3.789
. By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.877084 found by
Walter Trump.
[1] 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
.
Below are the minimum solutions for values up to n=12:[2] (The case for n=11 remains unresolved)
| Number of unit squares
| Minimal side length
of big square |
|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 2 |
| 5 | 2.707... |
} |
| 6 | 3 |
| 7 | 3 |
| 8 | 3 |
| 9 | 3 |
| 10 | 3.707... |
} |
| 11 | 3.877...? |
| 12 | 4 | |
Asymptotic results
For larger values of the side length
, the exact number of unit squares that can pack an
square remains unknown.It is always possible to pack a
\lfloora\rfloor x \lfloora\rfloor
grid of axis-aligned unit squares,but this may leave a large area, approximately
, uncovered and wasted.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
(here written in little o notation).Later, Graham and
Fan Chung further reduced the wasted space to
.However, as
Klaus Roth and
Bob Vaughan proved, all solutions must waste space at least
\Omegal(a1/2(a-\lfloora\rfloor)r)
. In particular, when
is a
half-integer, the wasted space is at least proportional to its
square root. The precise
asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an
open problem.
Some numbers of unit squares are never the optimal number in a packing. In particular,if a square of size
allows the packing of
unit squares, then it must be the case that
and that a packing of
unit squares is also possible.
Square packing in a circle
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: (Only the cases n=1 and n=2 are known to be optimal)
| Number of squares | Circle radius |
|---|
| 1 |
} ≈ 0.707... |
| 2 |
} ≈ 1.118... |
| 3 |
} ≈ 1.288... |
| 4 |
≈ 1.414... |
| 5 |
} ≈ 1.581... |
| 6 | 1.688... |
| 7 |
} ≈ 1.802... |
| 8 | 1.978... |
| 9 |
} ≈ 2.077... |
| 10 |
} ≈ 2.121... |
| 11 | 2.214... |
| 12 |
≈ 2.236... | |
See also
Notes and References
- The 2000 version of listed this side length as 3.8772; the tighter bound stated here is from
- Web site: Archived copy . 2024-10-17 . 2024-10-07 . https://web.archive.org/web/20241007131608/https://mathworld.wolfram.com/SquarePacking.html . live .
