Packing problems are one area where mathematics meets puzzles (recreational mathematics). Many of these problems stem from real-life packing problems. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... A puzzle is a problem or enigma that challenges ingenuity. ... Recreational mathematics includes many mathematical games, and can be extended to cover such areas as logic and other puzzles of deductive reasoning. ...

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.

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]}. In mathematics, sphere packing problems are problems concerning arrangements of non-overlapping identical spheres which fill a space. ... A sphere is a perfectly symmetrical geometrical object. ... In anatomy, the cuboid bone is a bone in the foot. ...

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] Dimension (from Latin measured out) is, in essence, the number of degrees of freedom available for movement in a space. ... In mathematics, sphere packing problems are problems concerning arrangements of non-overlapping identical spheres which fill a space. ...

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:

Circles in square

Pack n unit circles into the smallest possible square.

Proven Minimum Solutions:

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:

Circles in equilateral triangle

Pack n unit circles into the smallest possible equilateral triangle (lengths shown are side length).

Proven Minimum Solutions:

Circles in regular hexagon

Pack n unit circles into the smallest possible regular hexagon (lengths shown are side length).

Proven Minimum Solutions:

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 a², but the precise, or even asymptotic, amount of wasted space for a a non-integer is open. For other uses, see Square. ... In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ...

Proven Minimum Solutions:

Other known results:

• If you can pack n² − 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(a^7/11).
• The wasted space not asymptotically o(a^1/2).

Walter Stromquist proved that 11 unit squares cannot be packed in a square of side less than 2+4*5^-1/2 Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ... Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...

Squares in circle

Pack n squares in the smallest possible circle.

Proven Minimum Solutions:

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. In geometry, a rectangle is a defined as a quadrilateral polygon in which all four angles are right angles. ... A polyomino is a polyform with the square as its base form. ...

rectangles with rectangles

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. In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...

All the same polyominoes in a rectangle

TODO

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. A pentomino is a polyomino composed of five (Greek πέντε / pente) congruent squares, connected orthogonally. ...

See also

• Set packing
• Bin packing problem
• Slothouber-Graatsma Puzzle
• Conway puzzle
• Tetris
• Covering problem
• Knapsack problem
• Sphere packing

Set packing is an NP-complete problem in combinatorics, and was one of Karps 21 NP-complete problems. ... In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. ... The Slothouber–Graatsma puzzle is a packing problem that calls for packing six 1 × 2 × 2 blocks and three 1 × 1 × 1 blocks into a 3 × 3 × 3 box. ... Conways puzzle is a packing problem using rectangular blocks, named after its inventor, mathematician John Conway. ... This article needs additional references or sources to facilitate its verification. ... In combinatorics and computer science, the covering problem is a type of general question: if a certain structure covers another, or how many structures are required to cover another? For Petri nets, for example, the covering problem is defined as the question if for a given marking, there exists a... Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under 15 kg? A multi dimensional problem could consider the density or dimensions of the boxes, the latter a typical packing problem. ... In mathematics, sphere packing problems are problems concerning arrangements of non-overlapping identical spheres which fill a space. ...

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

References

• P. Erdös and R. L. Graham, On Packing Squares with Equal Squares, J. Combin. Theory Ser. A 19 (1975) 119-123.
• Eric W. Weisstein, Klarner's Theorem at MathWorld.
• Eric W. Weisstein, de Bruijn's Theorem at MathWorld.