Packing problem

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 Rectangular Prism

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 box 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 spheres) can never be packed with 100% efficiency. 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:1 Large cicle radius: 1
  • Number of circles:2 Large cicle radius: 2
  • Number of circles:3 Large cicle radius: 2.154...
  • Number of circles:4 Large cicle radius: 2.414...
  • Number of circles:5 Large cicle radius: 2.701...
  • Number of circles:6 Large cicle radius: 3

[edit] Circles in square

Pack n unit circles into the smallest possible square.

Proven Minimum Solutions:

  • Number of circles:1 Square size: 2
  • Number of circles:2 Square size: 3.414...
  • Number of circles:3 Square size: 3.931...
  • Number of circles:4 Square size: 4
  • Number of circles:5 Square size: 4.828...
  • Number of circles:6 Square size: 5.328...
  • Number of circles:7 Square size: 5.732...
  • Number of circles:8 Square size: 5.863...
  • Number of circles:9 Square size: 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 circles:1 Length: 3.414...
  • Number circles:2 Length: 4.828...
  • Number circles:3 Length: 5.414...
  • Number circles:4 Length: 6.242...
  • Number circles:5 Length: 7.146...
  • Number circles:6 Length: 7.414...
  • Number circles:7 Length: 8.181...
  • Number circles:9 Length: 9.071...
  • Number circles:10 Length: 9.414...

[edit] Circles in equilateral triangle

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

Proven Minimum Solutions:

  • Number of circles:1 Length: 3.464...
  • Number of circles:2 Length: 5.464...
  • Number of circles:3 Length: 5.464...
  • Number of circles:4 Length: 6.928...
  • Number of circles:5 Length: 7.464...
  • Number of circles:6 Length: 7.464...
  • Number of circles:7 Length: 8.928...
  • Number of circles:8 Length: 9.29...

[edit] Circles in regular hexagon

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

Proven Minimum Solutions:

  • Number of circles:1 Length: 1.154...
  • Number of circles:2 Length: 2.154...
  • Number of circles:3 Length: 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:1 Square size: 1
  • Number of squares:2 Square size: 2
  • Number of squares:3 Square size: 2
  • Number of squares:4 Square size: 2
  • Number of squares:5 Square size: 2.707 (2 + 2-1/2)
  • Number of squares:6 Square size: 3
  • Number of squares:7 Square size: 3
  • Number of squares:8 Square size: 3
  • Number of squares:9 Square size: 3
  • Number of squares:10 Square size: 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:1 Radius of Circle: 0.707...
  • Number of squares:2 Radius of Circle: 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

[edit] External links

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

[edit] References

  • P. Erdös and R. L. Graham, On Packing Squares with Equal Squares, J. Combin. Theory Ser. A 19 (1975) 119-123.
Retrieved from "http://en.wikipedia.org../../../p/a/c/Packing_problem.html"
In other languages