Skip to content

Packing pentominoes

August 24, 2012

Yes, yes, yes, learning maths is all very well, but what about doing some maths, hmm…?

In 1978, I spent 7 months on Ein Karmel kibbutz in northern Israel. I enjoy recreational mathematics but it was not everyone’s favourite pastime, so I had to make my own amusements. I had a copy of Martin Gardner’s classic book Mathematical Games, now contained in this CD. In this book, he discussed (along with many other wonderful things) pentominoes, which are the shapes of the 12 ways of arranging 5 squares on a grid.

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 – and obviously starting only from the edge.

I also 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 another classic, Winning Ways for Your Mathematical Plays (by Berlekamp, Conway and Guy), 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, this column value 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 second one (with the smaller height).

Height
x
Width

Pattern

Low Ratio

High Ratio

Area

Cutting Order

8 x 9

Can you find this?
Sven Egevad says there is indeed an 8×9 solution

1.000

1.406

72.00

O(QU)
WTP
ZXR
VYS

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

 to 

1.406

to

1.643

 1.857

90.00

to

80.50

SRZ
OXY
QVW
UTP

6 x 13

(Sven: Found by Samuel Golomb)

1.857

2.500

78.00

W(QR)S
XPOV
UYZT

5×15

(Sven again)

2.500

 3.900

 75.00

XVUYZ
RT
OQWSP)

4.828
x
18.828

 

3.900

4.107

90.90

TORZ
XSUV
QPWY

4
x
19.828

 

4.107

6.405

79.31

XOZT
RSVQ
UPWY

4×25.621
to
3×26.121

 to 

 6.405
to
8.707

102.48
to
78.36

XRTY
VUQP
OSZW

Note that the height can be less than 3 for all but the .

Questions:

  1. Why do we get stuck at an area of 75 to 80? What is it in these shapes that require 20 or so extra spare spaces (i.e. not 10 and not 50) to pack them as we want to? I think any area figure above 80 should be able to be improved.
  2. Are there any other exceptional cases, such as the 4.828 x 18.828?
  3. If we allow for multiple sets to be produced, such volume production would need a more or less separate area for the multiples of each piece. How quickly does this happen?

So, over to you – any suggestions and improvements are most welcome and will be acknowledged here.

Advertisements
One Comment
  1. Very good post. I certainly love this website.

    Keep it up!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: