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:[citation needed]

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:[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

[edit] 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...

[edit] 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...

[edit] 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...

[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 a², 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 n² − 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]

[edit] 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...

[edit] 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.

[edit] 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.

[edit] All the same polyominoes in a rectangle

 Please help improve this section by expanding it.
Further information might be found on the talk page or at requests for expansion.


[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

[edit] External links

Many puzzle books as well as mathematical journals contain articles on packing problems.

[edit] References

 This article or section includes a list of references or external links, but its sources remain unclear because it lacks in-text citations.
You can improve this article by introducing more precise citations.