New results in red below (
Packing Pentominoes Home, Mazes
In 1978, I (
I wanted to make my own pentomino set, but materials and tools were in very short supply. I scrounged one piece of wood, about 50cm x 40cm x 0.5cm as I recall, and a simple saw. With this saw, I could make only straight cuts in the wood piece.
I wanted to make the pentomino set with
pieces as large as possible from the single piece of wood, using only the plain
saw. I have no record of my solution, but I remember it involved diagonal cuts
across empty squares. At the end, I did the best I could with the 
. Aside
from that, I ended up with a 12-piece set with fairly smooth neat edges.
I was aware (but did not follow up at the time) that this was an example of a more general packing puzzle:
For rectangles with a given ratio of
height to width, what is the smallest rectangle that will allow the
construction of a complete set of pentominoes?
This problem could also be asked of almost any collection of plane figures. What is the simplest non-trivial problem of this type for rectangular pieces? Smallest may mean fewest pieces, smallest total area (assuming all rectangles have integer sides), or fewest different sizes.
First some terms: I use the pentomino naming
system found in the classic Winning Ways for Your Mathematical Plays
(Berlekamp, Conway and Guy, 1982), as follows:
|
O
|
P
|
Q
|
R
|
S
|
T
|
U
|
V
|
W
|
X
|
Y
|
Z
|
In the table below:
· I have shown the Pattern of the most efficient pentomino packing arrangement I know of for each ratio of rectangle length to width. Some packings have one or more pieces which can 'slide', such that it becomes (a very little) more efficient for non-integer width to height ratios.
· The Low Ratio column shows the lowest value of the length to width ratio for which the accompanying pattern is optimal. Where there are two patterns displayed as a range, the Low Ratio is also displayed as a range.
- The High Ratio column shows the lowest value of the length to width ratio for which the accompanying pattern is optimal. Where there are two patterns, it always applies to the one with the smaller height.
- The Area column shows the area of the displayed rectangle. Where there are two patterns, it always applies to the one with the smaller height.
|
Height x
Width |
Pattern |
Low Ratio |
High Ratio |
Area |
Cutting Order |
Found by |
|
8 x 9 |
? |
1.000 |
1.406 |
72.00 |
O(QU) WTP ZXR VYS |
(Sven Egevad says there is an 8x9 solution) |
|
9 x 9 |
|
1.000 |
1.111 |
81.00 |
O(QU) WTP ZXR VYS |
|
|
8 x 10 |
|
1.111 |
1.406 |
80.00 |
ZTR PUO V(QX) WSY |
|
|
8 x 11.25 to 7 x 11.5 |
|
1.406 to 1.643 |
1.857 |
80.50 to 90.00 |
SRZ OXY QVW UTP |
|
|
6 x 13 |
|
1.857 |
2.500 |
78.00 |
W(QR)S XPOV UYZT |
Samuel Golomb (thanks to Sven Egevad for this) |
|
5x15 |
|
2.500 |
3.900 |
75.00 |
XVUYZ RT OQWSP) |
Sven Egevad |
|
4.828 x 18.828 |
|
3.900 |
4.107 |
90.90 |
TORZ XSUV QPWY |
|
|
4x19.828 |
|
4.107 |
6.405 |
79.31 |
XOZT RSVQ UPWY |
|
|
4x25.621 to 3x26.121 |
to
|
6.405 to 8.707 |
|
78.36 to 102.48 |
XRTY VUQP OSZW |
|
to 
Note that the height can be less than 3 for
all but the 
.
Questions:
- Why do we get stuck at an area of 75 to 80? What is it in these shapes that requires 15 to 20 extra spare spaces to pack them as we want to? I think any area figure above 80 should be able to be improved.
- Are there any other exceptional cases, such as the 4.828 x 18.828?
- If we allow for multiple sets to be produced, I think large volumes would need a more or less separate area for the multiples of each piece. How quickly does this happen?
If you have any questions, answers, suggestions etc, please e-mail me. Also, if you are interested in this sort of thing, take a look at Erich Friedmann's Math Magic pages.
This page last edited on 14 June 2002