Part of a series on: 
Puzzles 

Topics

Packing problems are one area where mathematics meets puzzles (recreational mathematics). Many of these problems stem from reallife problems with packing items.
In a packing problem, you are given:
Usually the packing must be without gaps or overlaps, but in some packing problems the overlapping (of goods with each other and/or with the boundary of the container) is allowed but should be minimised. In others, gaps are allowed, but overlaps are not (usually the total area of gaps has to be minimised).
CoveringPacking Dualities  
Covering problems  Packing problems 

Minimum Set Cover  Maximum Set Packing 
Minimum Vertex Cover  Maximum Matching 
Minimum Edge Cover  Maximum Independent Set 
Contents 
There are many different types of packing problems. Usually they involve finding the maximum number of a certain shape that can be packed into a larger, perhaps different shape, allowing touching, but without overlap.
Many of these problems, when the container size is increased in all directions, become equivalent to the problem of packing objects as densely as possible in infinite Euclidean space. This problem is relevant to a number of scientific disciplines, and has received significant attention. The Kepler conjecture postulated an optimal solution for spheres hundreds of years before it was proven correct by Hales. Many other shapes have received attention, including ellipsoids, tetrahedra, icosahedra, and unequalsphere dimers.
The problem of finding the smallest ball such that k disjoint open unit balls may be packed inside it has a simple and complete answer in ndimensional Euclidean space if , and in an infinite dimensional Hilbert space with no restrictions. It is worth describing in detail here, to give a flavor of the general problem. In this case, a configuration of k pairwise tangent unit balls is available. Place the centers at the vertices a_{1},..,a_{k} of a regular dimensional simplex with edge 2; this is easily realized starting from an orthonormal basis. A small computation shows that the distance of each vertex from the barycenter is . Moreover, any other point of the space necessarily has a larger distance from at least one of the vertices. In terms of inclusions of balls, the open unit balls centered at are included in a ball of radius , which is minimal for this configuration.
To show that this configuration is optimal, let be the centers of disjoint open unit balls contained in a ball of radius centered at a point . Consider the map from the finite set into taking in the corresponding for each . Since for all , this map is 1Lipschitz and by the Kirszbraun theorem it extends to a 1Lipschitz map that is globally defined; in particular, there exists a point such that for all one has , so that also . This shows that there are disjoint unit open balls in a ball of radius if and only if . Notice that in an infinite dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius if and only if . For instance, the unit balls centered at , where is an orthonormal basis, are disjoint and included in a ball of radius centered at the origin. Moreover, for , the maximum number of disjoint open unit balls inside a ball of radius r is .
A classic problem is the sphere packing problem, where one must determine how many spherical objects of given diameter d can be packed into a cuboid of size a × b × c.
There are many other problems involving packing circles into a particular shape of the smallest possible size. Note that these problems are mathematically distinct from the ideas in the circle packing theorem.
Circles (and their counterparts in other dimensions) can never be packed with 100% efficiency in dimensions larger than one (in a one dimensional universe, circles merely consist of two points). That is, there will always be unused space if you are only packing circles. The most efficient way of packing circles, hexagonal packing produces approximately 90% efficiency. [1]
Some of the more nontrivial circle packing problems are packing unit circles into the smallest possible larger circle.
Minimum solutions:^{[citation needed]}
Number of circles  Circle radius 

1  1 
2  2 
3  2.154... 
4  2.414... 
5  2.701... 
6  3 
7  3 
8  3.304... 
9  3.613... 
10  3.813... 
11  3.923... 
12  4.029... 
13  4.236... 
14  4.328... 
15  4.521... 
16  4.615... 
17  4.792... 
18  4.863... 
19  4.863... 
20  5.122... 
Pack n unit circles into the smallest possible square. This is closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, d_{n}, between points^{[1]}. To convert between these two formulations of the problem, the square side for unit circles will be L=2+2/d_{n}.
Current best solutions:
Number of circles  Square size  d_{n}^{[2]} 

1  2  
2  3.414...  1.414...∗ 
3  3.931...  1.035...∗ 
4  4  1* 
5  4.828...  0.707...∗ 
6  5.328...  0.601...∗ 
7  5.732...  0.536...∗ 
8  5.863...  0.518...∗ 
9  6  0.5 ∗ 
10  6.747...  0.421... 
11  7.022...  0.398... 
12  7.144...  0.389... 
13  7.463...  0.366... 
14  7.796...  0.345...∗ 
15  7.932...  0.337... 
16  8  0.333...∗ 
17  8.532...  0.306... 
18  8.656...  0.300... 
19  8.907...  0.290... 
20  8.978...  0.287... 
∗ indicates that the solution is known to be optimal.
Pack n unit circles into the smallest possible isosceles right triangle (lengths shown are length of leg)
Minimum solutions:^{[citation needed]}
Number of circles  Length 

1  3.414... 
2  4.828... 
3  5.414... 
4  6.242... 
5  7.146... 
6  7.414... 
7  8.181... 
8  8.692... 
9  9.071... 
10  9.414... 
11  10.059... 
12  10.422... 
13  10.798... 
14  11.141... 
15  11.414... 
Pack n unit circles into the smallest possible equilateral triangle (lengths shown are side length).
Minimum solutions:^{[citation needed]}
Number of circles  Length 

1  3.464... 
2  5.464... 
3  5.464... 
4  6.928... 
5  7.464... 
6  7.464... 
7  8.928... 
8  9.293... 
9  9.464... 
10  9.464... 
11  10.730... 
12  10.928... 
13  11.406... 
14  11.464... 
15  11.464... 
Pack n unit circles into the smallest possible regular hexagon (lengths shown are side length).
Minimum solutions:^{[citation needed]}
Number of circles  Length 

1  1.154... 
2  2.154... 
3  2.309... 
4  2.666... 
5  2.999... 
6  3.154... 
7  3.154... 
8  3.709... 
9  4.011... 
10  4.119... 
11  4.309... 
12  4.309... 
13  4.618... 
14  4.666... 
15  4.961... 
A problem is the square packing problem, where one must determine how many squares of side 1 you can pack into a square of side a. Obviously, if a is an integer, the answer is a^{2}, but the precise, or even asymptotic, amount of wasted space for a a noninteger is open.
Proven minimum solutions:^{[3]}
Number of squares  Square size  

1  1  
2  2  
3  2  
4  2  
5  2.707 (2 + 2^{ −1/2})


6  3  
7  3  
8  3  
9  3  
10  3.707 (3 + 2^{ −1/2}) 
Other results:
Pack n squares in the smallest possible circle.
Minimum solutions:^{[citation needed]}
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.215... 
12  2.236... 
In tiling or tesselation problems, there are to be no gaps, nor overlaps. Many of the puzzles of this type involve packing rectangles or polyominoes into a larger rectangle or other squarelike shape.
There are significant theorems on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps:
The study of polyomino tilings largely concerns two classes of problems: to tile a rectangle with congruent tiles, and to pack one of each nomino into a rectangle.
A classic puzzle of the second kind is to arrange all twelve pentominoes into rectangles sized 3×20, 4×15, 5×12 or 6×10.
Many puzzle books as well as mathematical journals contain articles on packing problems.
