A unit square is a square with a side length of one unit. Suppose you have a collection of some number of unit squares, and we will call this number n. You want to pack all these squares into a large square enclosure with no overlap. For a given number of unit squares n, what is the smallest enclosure you can make? We express the size of the enclosure using its side length, a. This is known as the square packing problem.
The Easy Cases
The most trivial case is when n is a perfect square: 1, 4, 9, and so on. Then you can simply arrange all of your unit squares into a grid pattern with a square border, and this border is the enclosure having side length √n. Many other values of n yield simple solutions as well, where the squares are similarly aligned to the grid, like with two or three squares.
When Things Get Interesting
Five squares is a notable case. One square is placed at a 45-degree angle from the grid and the other four are placed around it, resulting in an enclosure side length of a = 2 + 1/√2, about 2.707. The solution for 10 squares is simply an extension of the solution for five.
What We Still Don’t Know
Despite the square packing problem’s apparent simplicity, much about it is still unknown. It remains unsolved for some rather small values of n. The smallest two are n = 11 and n = 17. Approximations have been obtained in these cases, giving a ≈ 3.88 and a ≈ 4.68 respectively, and producing some bizarre-looking packings where squares sit at odd angles to squeeze into the tightest possible enclosure.
The difficulty is that there is no general formula or algorithm that produces optimal packings. Each value of n is essentially its own problem. And proving that a given packing is truly optimal, that no cleverer arrangement exists, requires ruling out every possible configuration. For small n this is already hard. For large n it is currently out of reach.
Further reading:
- Erich Friedman’s packing center catalogs known results and best approximations for square packing (Erich Friedman’s Packing Center)
- MathWorld entry on square packing (Wolfram MathWorld)
Leave a Reply