Square packing in a square is a
packing problem
Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few conta ...
where the objective is to determine how many
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
s of side one (
unit square
In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and .
Cartesian coordinates
In a Cartesian coordin ...
s) can be packed into a square of side . If is an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
, the answer is , but the precise, or even
asymptotic
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related context ...
, amount of wasted space for non-integer is an open question.
Small numbers of squares
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
A ceiling is an overhead interior surface that covers the upper limits of a room. It is not generally considered a structural element, but a finished surface concealing the underside of the roof structure or the floor of a story above. Ceilings ...
(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 involves packing 11 unit squares into a larger square.
11 unit squares cannot be packed in a square of side less than . By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.877084,
slightly improving a similar packing found earlier by Walter Trump.
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 grid of axis-aligned unit squares,
but this may leave a large area, approximately , uncovered and wasted.
Instead, Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
and Ronald Graham
Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...
showed that for a different packing by tilted unit squares, the wasted space could be significantly reduced to (here written in little o notation
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
).
Later, Graham and Fan Chung
Fan-Rong King Chung Graham (; born October 9, 1949), known professionally as Fan Chung, is a Taiwanese-born American mathematician who works mainly in the areas of spectral graph theory, extremal graph theory and random graphs, in particular in g ...
further reduced the wasted space to .
However, as Klaus Roth
Klaus Friedrich Roth (29 October 1925 – 10 November 2015) was a German-born British mathematician who won the Fields Medal for proving Roth's theorem on the Diophantine approximation of algebraic numbers. He was also a winner of the De Mo ...
and Bob Vaughan proved, all solutions must waste space at least . In particular, when is a half-integer
In mathematics, a half-integer is a number of the form
:n + \tfrac,
where n is an whole number. For example,
:, , , 8.5
are all ''half-integers''. The name "half-integer" is perhaps misleading, as the set may be misunderstood to include numbers ...
, the wasted space is at least proportional to its square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
. The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (i.e., no solution for it is know ...
.[
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
A related problem is that of packing ''n'' unit squares into a circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
with radius as small as possible. For this problem, good solutions are known for ''n'' up to 35. Here are minimum solutions for ''n'' up to 12:
See also
*Circle packing in a square
Circle packing in a square is a packing problem in recreational mathematics, where the aim is to pack unit circles into the smallest possible square. Equivalently, the problem is to arrange points in a unit square aiming to get the greatest mini ...
*Squaring the square
Squaring the square is the problem of tiling an integral square using only other integral squares. (An integral square is a square whose sides have integer length.) The name was coined in a humorous analogy with squaring the circle. Squaring the sq ...
*Rectangle packing
Rectangle packing is a packing problem where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been stu ...
References
{{reflist
External links
Squares in Squares
Erich's Packing Center, Erich Friedman, Stetson University
Packing problems
Unsolved problems in geometry