Misplaced Pages

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 ${\displaystyle a}$. If ${\displaystyle a}$ is an integer, the answer is ${\displaystyle a^{2},}$ but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer ${\displaystyle a}$ is an open question.

The smallest value of ${\displaystyle a}$ that allows the packing of ${\displaystyle n}$ unit squares is known when ${\displaystyle n}$ is a perfect square (in which case it is ${\displaystyle {\sqrt {n}}}$), as well as for ${\displaystyle n={}}$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 ${\displaystyle a}$ is ${\displaystyle \lceil {\sqrt {n}}\,\rceil }$, where ${\displaystyle \lceil \,\ \rceil }$ 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 ${\displaystyle n=11}$. It is known that 11 unit squares cannot be packed in a square of side length less than ${\displaystyle \textstyle 2+2{\sqrt {4/5}}\approx 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.

The smallest case where the best known packing involves squares at three different angles is ${\displaystyle n=17}$. It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length ${\displaystyle a\approx 4.6756}$.

Below are the minimum solutions for values up to n=12: (The case for n=11 remains unresolved)

Number of unit squares ${\displaystyle n}$	Minimal side length ${\displaystyle a}$ of big square
1	1
2	2
3	2
4	2
5	2.707...	${\displaystyle 2+{\frac {\sqrt {2}}{2}}}$
6	3
7	3
8	3
9	3
10	3.707...	${\displaystyle 3+{\frac {\sqrt {2}}{2}}}$
11	3.877... ?
12	4

Asymptotic results

For larger values of the side length ${\displaystyle a}$, the exact number of unit squares that can pack an ${\displaystyle a\times a}$ square remains unknown. It is always possible to pack a ${\displaystyle \lfloor a\rfloor \!\times \!\lfloor a\rfloor }$ grid of axis-aligned unit squares, but this may leave a large area, approximately ${\displaystyle 2a(a-\lfloor a\rfloor )}$, 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 ${\displaystyle o(a^{7/11})}$ (here written in little o notation). Later, Graham and Fan Chung further reduced the wasted space to ${\displaystyle O(a^{3/5})}$. However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least ${\displaystyle \Omega {\bigl (}a^{1/2}(a-\lfloor a\rfloor ){\bigr )}}$. In particular, when ${\displaystyle a}$ 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 ${\displaystyle a\times a}$ allows the packing of ${\displaystyle n^{2}-2}$ unit squares, then it must be the case that ${\displaystyle a\geq n}$ and that a packing of ${\displaystyle n^{2}}$ 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	${\displaystyle {\frac {\sqrt {2}}{2}}}$ ≈ 0.707...
2	${\displaystyle {\frac {\sqrt {5}}{2}}}$ ≈ 1.118...
3	${\displaystyle {\frac {5{\sqrt {17}}}{16}}}$ ≈ 1.288...
4	${\displaystyle {\sqrt {2}}}$ ≈ 1.414...
5	${\displaystyle {\frac {\sqrt {10}}{2}}}$ ≈ 1.581...
6	1.688...
7	${\displaystyle {\frac {\sqrt {13}}{2}}}$ ≈ 1.802...
8	1.978...
9	${\displaystyle {\frac {\sqrt {1105}}{16}}}$ ≈ 2.077...
10	${\displaystyle {\frac {3{\sqrt {2}}}{2}}}$ ≈ 2.121...
11	2.214...
12	${\displaystyle {\sqrt {5}}}$ ≈ 2.236...

See also

• Circle packing in a square
• Squaring the square
• Rectangle packing
• Moving sofa problem

References

1. ^ Brass, Peter; Moser, William; Pach, János (2005), Research Problems in Discrete Geometry, New York: Springer, p. 45, ISBN 978-0387-23815-9, LCCN 2005924022, MR 2163782
2. ^ Kearney, Michael J.; Shiu, Peter (2002), "Efficient packing of unit squares in a square", Electronic Journal of Combinatorics, 9 (1), Research Paper 14, 14 pp., doi:10.37236/1631, MR 1912796, archived from the original on 2011-06-04, retrieved 2011-06-01
3. Bentz, Wolfram (2010), "Optimal packings of 13 and 46 unit squares in a square", The Electronic Journal of Combinatorics, 17 (R126), arXiv:1606.03746, doi:10.37236/398, MR 2729375
4. ^ Friedman, Erich (2009), "Packing unit squares in squares: a survey and new results", Electronic Journal of Combinatorics, 1000, Dynamic Survey 7, doi:10.37236/28, MR 1668055, archived from the original on 2018-02-24, retrieved 2018-02-23
5. Stromquist, Walter (2003), "Packing 10 or 11 unit squares in a square", Electronic Journal of Combinatorics, 10, Research Paper 8, doi:10.37236/1701, MR 2386538, archived from the original on 2011-06-04, retrieved 2011-06-01
6. The 2000 version of Friedman (2009) listed this side length as 3.8772; the tighter bound stated here is from Gensane, Thierry; Ryckelynck, Philippe (2005), "Improved dense packings of congruent squares in a square", Discrete & Computational Geometry, 34 (1): 97–109, doi:10.1007/s00454-004-1129-z, MR 2140885
7. "Square Packing". Archived from the original on 2024-10-07. Retrieved 2024-10-17.
8. Erdős, P.; Graham, R. L. (1975), "On packing squares with equal squares" (PDF), Journal of Combinatorial Theory, Series A, 19: 119–123, doi:10.1016/0097-3165(75)90099-0, MR 0370368
9. Chung, Fan; Graham, Ron (2020), "Efficient packings of unit squares in a large square" (PDF), Discrete & Computational Geometry, 64 (3): 690–699, doi:10.1007/s00454-019-00088-9
10. Roth, K. F.; Vaughan, R. C. (1978), "Inefficiency in packing squares with unit squares", Journal of Combinatorial Theory, Series A, 24 (2): 170–186, doi:10.1016/0097-3165(78)90005-5, MR 0487806
11. Friedman, Erich, Squares in Circles

External links

• Friedman, Erich, "Squares in Squares", Github, Erich's Packing Center

• Packing problems
• Unsolved problems in geometry