Packing problems
 | Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation. |
 | This article needs attention from an expert in Computer Science. Please add a reason or a talk parameter to this template to explain the issue with the article. (November 2008) |
Packing problems are one area where mathematics meets puzzles (recreational mathematics). Many of these problems stem from real-life packing problems.
In a packing problem, you are given:
- one or more (usually two- or three-dimensional) containers
- several 'goods', some or all of which must be packed into this container
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).
Problems
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.
Packing infinite space
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 unequal-sphere dimers.
Sphere in cuboid
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.
Packing circles
There are many other problems involving packing circles into a particular shape of the smallest possible size.
Hexagonal packing
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]
Circles in circle
Some of the more non-trivial circle packing problems are packing unit circles into the smallest possible larger circle.
Proven minimum solutions:[citation needed]
| Number of circles | Large circle radius |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2.154... |
| 4 | 2.414... |
| 5 | 2.701... |
| 6 | 3 |
Circles in square
Pack n unit circles into the smallest possible square.
Proven minimum solutions:[citation needed]
| Number of circles | Square size |
|---|---|
| 1 | 2 |
| 2 | 3.414... |
| 3 | 3.931... |
| 4 | 4 |
| 5 | 4.828... |
| 6 | 5.328... |
| 7 | 5.732... |
| 8 | 5.863 |
| 9 | 6 |
Circles in isosceles right triangle
Pack n unit circles into the smallest possible isosceles right triangle (lengths shown are length of leg)
Proven 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... |
| 9 | 9.071... |
| 10 | 9.414... |
Circles in equilateral triangle
Pack n unit circles into the smallest possible equilateral triangle (lengths shown are side length).
Proven 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.29... |
Circles in regular hexagon
Pack n unit circles into the smallest possible regular hexagon (lengths shown are side length).
Proven minimum solutions:[citation needed]
| Number of circles | Length |
|---|---|
| 1 | 1.154... |
| 2 | 2.154... |
| 3 | 2.309... |
Packing squares
Squares in square
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, here if a is an integer, the answer is a2, but the precise, or even asymptotic, amount of wasted space for a a non-integer is open.
Proven minimum solutions:[citation needed]
| 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 known results:
- If you can pack n2 − 2 squares in a square of side a, then a ≥ n.[citation needed]
- The naive approach (side matches side) leaves wasted space of less than 2a + 1.[citation needed]
- The wasted space is asymptotically o(a7/11).[citation needed]
- The wasted space is not asymptotically o(a1/2).[citation needed]
Walter Stromquist proved that 11 unit squares cannot be packed in a square of side less than 2 + 4×5 −1/2.[citation needed]
Squares in circle
Pack n squares in the smallest possible circle.
Proven minimum solutions:[citation needed]
| Number of squares | Radius of circle |
|---|---|
| 1 | 0.707... (2 −1/2) |
| 2 | 1.118... |
Tiling
In this type of problem there are to be no gaps, nor overlaps. Most of the time this involves packing rectangles or polyominoes into a larger rectangle or other square-like shape.
Rectangles in rectangle
There are significant theorems on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps:
- Klarner's theorem: An a × b rectangle can be packed with 1 × n strips iff n | a or n | b.
- de Bruijn's theorem: A box can be packed with a harmonic brick a × a b × a b c if the box has dimensions a p × a b q × a b c r for some natural numbers p, q, r (i.e., the box is a multiple of the brick.)
When tiling polyominoes, there are two possibilities. One is to tile all the same polyomino, the other possibility is to tile all the possible n-ominoes there are into a certain shape.
All the same polyominoes in a rectangle
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg?lang=en){kind=small} | This section needs expansion. You can help by adding to it. (October 2007) |
Different polyominoes
A classic puzzle of this kind is pentomino, where the task is to arrange all twelve pentominoes into rectangles sized 3×20, 4×15, 5×12 or 6×10.
See also
- Set packing
- Bin packing problem
- Slothouber-Graatsma puzzle
- Conway puzzle
- Tetris
- Covering problem
- Knapsack problem
- Sphere packing
- Tetrahedron packing
- Cutting stock problem
References
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (February 2008) |
- P. Erdös and R. L. Graham, On Packing Squares with Equal Squares, J. Combin. Theory Ser. A 19 (1975) 119–123.
- Weisstein, Eric W. "Klarner's Theorem". MathWorld.
- Weisstein, Eric W. "de Bruijn's Theorem". MathWorld.
External links
Many puzzle books as well as mathematical journals contain articles on packing problems.