# Problem of the Month (February 1999)

A natural question about polyominoes, connected collections of lattice squares, that has been well-researched is "Which polyominoes can tile a rectangle?" For example, the smallest rectangle the polyomino will pack is the 10×5 rectangle shown below:

We consider one dimensional disconnected polyominoes, collections of lattice squares in a line. We ask which can tile rectangles, and how many polyominoes are needed. The smallest number of polyominoes that tiles some rectangle is called the order of the polyomino.

Some of these are easy, as they will tile an n×1 rectangle for some n. For example, the polyomino tiles a 6×1 rectangle. Others are more difficult, like , which tiles a 15×12 rectangle. Others, like , cannot tile a rectangle at all.

So which polyominoes can tile a rectangle? Of these, what is the order?

Mike Reid has written several papers on tiling with polyominoes. He has a computer program that is especially good at proving that tilings are impossible.

I wondered whether increasing the rectangle to 3 (or more!) dimensions would help polyominoes tile. I conjectured that all polyominoes tile some d-dimensional cube. Reid came up with this counterexample, which can obviously never tile the corner of any cube:

Patrick Hamlyn wrote a computer program that found many minimal tilings, and the number of tilings for various sizes of rectangles.

Joe DeVincentis found some minimal tilings, and he did all his tilings by hand! He notes that in every minimal tiling, the longer dimension is divisible by the number of squares in the polyomino. He asks whether this is true in general. In fact, he challenges anyone to find a tiling of a 1-dimensional polyomino in which the area divides neither dimension of the tiled rectangle. Reid has managed to show that such a polyomino must have area at least 6.

Aaron Meyerowitz has written several papers on tiling disconnected polyominoes in 1 dimension. He told me that Andrew Adler and F. C. Holroyd proved in 1981 that any 1 dimensional triomino tiles some nx1 rectangle. This was also known to Klarner much earlier. He also told me that it follows from one of his papers that the order of such a triomino is the 1 dimensional order. It is not known whether this is true for other polyominoes which tile in 1 dimension.

Meyerowitz also told me that Don Coppersmith proved in 1985 that every tetromino (not necessarily 1 dimensional) tiles the plane. There is a hexomino that does not tile the plane: . It is not known whether every pentomino tiles the plane.

Meyerowitz also asks 2 questions: "If a polyomino tiles a half strip, must it tile some rectangle?" and "If a polyomino tiles the half line, must it tile a finite interval?"

Rick Eason sent me a detailed description of the packable boxes of .

Here are the results for small length polyominoes:

## Polyominoes of Length 3, 4, and 5

PolyominoOrderDimensions FinderProver
24x1
26x1
36x1
28x1
none   Juha Saukkola
26x1
26x1
48x1

## Polyominoes of Length 6

PolyominoOrderDimensions FinderProver
210x1
24 20x6Erich FriedmanPatrick Hamlyn
24 16x6Joe DevincentisPatrick Hamlyn
28x1
21 12x7Erich FriedmanErich Friedman
28x1
39x1
618x1
510x1

## Polyominoes of Length 7

PolyominoOrderDimensions FinderProver
212x1
none   Mike Reid
none   Erich Friedman
36 15x12 Patrick HamlynPatrick Hamlyn
210x1
36 15x12 Juha SaukkolaPatrick Hamlyn
none   Erich Friedman
210x1
none   Erich Friedman
28x1
28x1
28x1
60 24x10 Patrick HamlynPatrick Hamlyn
28x1
none   Mike Reid
412x1
412x1
39x1
612x1

## Polyominoes of Length 8

PolyominoOrderDimensions FinderProver
214x1
none   Mike Reid
none   Mike Reid
70 30x14 Mike, PatrickPatrick Hamlyn
212x1
none   Mike Reid
32 24x8 Mike, ErichPatrick Hamlyn
none   Erich Friedman
212x1
none   Mike Reid
none   Erich Friedman
none   Erich Friedman
48 30x8Mike, JoePatrick Hamlyn
78 30x13Mike, PatrickPatrick Hamlyn
210x1
90 50x9Mike, JoePatrick Hamlyn
none   Mike Reid
210x1
45 25x9Mike, JoePatrick Hamlyn
96 60x8Mike, PatrickPatrick Hamlyn
210x1
210x1
312x1
84 28x12Mike, PatrickPatrick Hamlyn
832x1
66 24x11Mike, PatrickPatrick Hamlyn
312x1
240? 20x48Mike Reid
624x1
50 20x10Mike, JoePatrick Hamlyn
102 24x17Mike, PatrickPatrick Hamlyn
412x1
1030x1
1236x1
714x1

## Polyominoes of Length 9

PolyominoOrderDimensions FinderProver
216x1
none  Mike Reid
none  Mike Reid
none  Mike Reid
54 42x9 Patrick HamlynPatrick Hamlyn
214x1
none  Mike Reid
36 28x9 Patrick HamlynPatrick Hamlyn
none  Patrick Hamlyn
none  Erich Friedman
214x1
none  Mike Reid
none  Mike Reid
none  Mike Reid
none  Mike Reid
none  Mike Reid
?
?
212x1
30 18x10 Patrick HamlynPatrick Hamlyn
none  Mike Reid
none  Mike Reid
212x1
none  Mike Reid
180?108x10Mike, Patrick
none  Mike Reid
none  Mike Reid
none  Mike Reid
3624x9Mike, PatrickPatrick Hamlyn
?
none  Mike Reid
none  Mike Reid
212x1
none  Mike Reid
212x1
210x1
210x1
?
210x1
156?60x13 Mike Reid
210x1
210x1
210x1
234?90x13 Mike Reid
none  Mike Reid
7230x12 Mike, PatrickMike Reid
10845x12 Mike, PatrickPatrick Hamlyn
210x1
240?100x12 Mike Reid
210x1
?
4820x12 Patrick HamlynPatrick Hamlyn
none  Mike Reid
?
416x1
8832x11 Mike ReidPatrick Hamlyn
416x1
4816x12 Patrick HamlynPatrick Hamlyn
120?40x12 Patrick Hamlyn
?
6024x10 Mike ReidMike Reid
416x1
624x1
none  Mike Reid
6020x12 Patrick HamlynPatrick Hamlyn
?
515x1
412x1
412x1
412x1
816x1

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 3/3/99.