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?


ANSWERS

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.