Packing problem
From Wikipedia, the free encyclopedia
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).
Contents |
[edit] 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.
[edit] 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. This is one of the hardest problems in this category[citation needed].
[edit] Packing Circles
There are many other problems involving packing circles into a particular shape of the smallest possible size.
[edit] 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]
[edit] 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:
| Number of circles | Large circle radius |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2.154... |
| 4 | 2.414... |
| 5 | 2.701... |
| 6 | 3 |
[edit] Circles in square
Pack n unit circles into the smallest possible square.
Proven Minimum Solutions:
| 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 |
[edit] Circles in icosceles right triangle
Pack n unit circles into the smallest possible isosceles right triangle (lengths shown are length of leg)
Proven Minimum Solutions:
| 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... |
[edit] Circles in equilateral triangle
Pack n unit circles into the smallest possible equilateral triangle (lengths shown are side length).
Proven Minimum Solutions:
| 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... |
[edit] Circles in regular hexagon
Pack n unit circles into the smallest possible regular hexagon (lengths shown are side length).
Proven Minimum Solutions:
| Number of circles | Length |
|---|---|
| 1 | 1.154... |
| 2 | 2.154... |
| 3 | 2.309... |
[edit] Packing squares
[edit] 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, answer for a a non-integer is open.
Proven Minimum Solutions:
| 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.
- The naive approach (side matches side) leaves wasted space of less than 2a + 1.
- The wasted space is asymptotically o(a7/11).
- The wasted space not asymptotically o(a1/2).
Walter Stromquist proved that 11 unit squares cannot be packed in a square of side less than 2+4*5-1/2
[edit] Squares in circle
Pack n squares in the smallest possible circle.
Proven Minimum Solutions:
| Number of squares | Radius of circle |
|---|---|
| 1 | 0.707... |
| 2 | 1.118... |
[edit] Tiling
In this type of problem there are to be no gaps, nor overlaps. Most of the time this involves packing polyominoes into a larger rectangle or other square-like shape.
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.
[edit] All the same polyominoes in a rectangle
TODO
[edit] 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.
[edit] See also
- Set packing
- Bin packing problem
- Slothouber-Graatsma Puzzle
- Conway puzzle
- Tetris
- Covering problem
- Knapsack problem
- Sphere packing
[edit] External links
Many puzzle books as well as mathematical journals contain articles on packing problems.
- Journal of Recreational Mathematics - easy read, many articles.
- Log Stacker
- Links to various MathWorld articles on packing
- MathWorld notes on packing squares.
- Erich's Packing Center
[edit] References
- P. Erdös and R. L. Graham, On Packing Squares with Equal Squares, J. Combin. Theory Ser. A 19 (1975) 119-123.
