Packing problem
|
|
User:-Ril/Karl-Scherer-Damage 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. Hence we can discern several categories of packing problems:
| Contents |
Categories of packing problems
- No gaps or overlaps allowed: these problems are called tiling puzzles
- Gaps allowed, but no overlaps. Usually the total area of gaps has to be minimised. See below for an example.
- Gaps and overlaps allowed. Here usually the total area of overlaps has to be minimised.
Examples of gaps-but-no-overlaps packing problems
Example 1
This is a classical one, its answer being surprising even for many mathematicians. The problem is to fit as many circles as possible of 1 cm diameter into a strip of dimensions 2 cm x n cm, where n = 1, 2, 3, ...
Obviously at least 2n circles can fit, but the solution is that if
- n > 63,
at least one more circle can fit than the formula 2n suggests. In fact, for every added length of 64, at least one additional circle can fit.
Example 2
How many spheres (often oranges) of given diameter d can you pack into a box of size a x b x c? This is one of the hardest problems in this category. See sphere packing for its history, eventual solution, and generalizations.
See also:
- list of computer puzzle games
- set packing
- bin packing problem
- covering problem
- mechanical puzzles
- puzzles
- tilings
- tiling puzzles
External links
Many puzzle books as well as mathematical journals contain articles on packing problems.
- Journal of Recreational Mathematics (http://www.baywood.com/journals/previewjournals.asp?id=0022-412x) - easy read, many articles.
- Log Stacker (http://www.elversonpuzzle.com)
- The math of circle packing (http://mathworld.wolfram.com/CirclePacking.html)