Problem of the Month (December 2001)

This month's problem concerns tiling squares with strips of smaller squares. A strip is a collection of 1 or more identical squares which are vertically or horizontally adjacent. For what values of m and n do there exist strip tilings of an m x m square with strips of width 1, 2, 3, . . . n?

For example, strips of width 1, 2, 3, and 4 can tile a 7 x 7, 8 x 8, or 9 x 9 square:


ANSWERS

Joseph DeVincentis found all but four of the tilings below. He furnished pictures for n≥10. Philippe Fondanaiche and Jeremy Galvagni found many of these tilings as well. Berend Jan van der Zwaag found many hard to find tilings.

Possible Strip Tilings of Squares

Number of StripsPossible Sizes of SquareUnknown
11 
2  
36 
47, 8, 9 
59, 10, 11, 12 
611, 12, 13, 14, 15, 16, 18 
713, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24 
815, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 
919, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 4018?
1022, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 4521?
1125, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41,
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 60
24?
1230, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 72
27? 28? 29?

Joseph DeVincentis and Berend Jan van der Zwaag have also proved some tilings impossible. The list of unresolved cases is shown above.

Joseph DeVincentis, Dane Brooke, and Jeremy Galvagni pointed out that a strip tiling using m strips can form no squares smaller than (2m-1) since it must contain squares of size m and (m-1). A better lower bound for larger m is (3m-9), since squares of size (m-2), (m-3), and (m-4) (or larger) must be in some horizontal or vertical cross section. One more lower bound that both noticed is √(n(n+1)(2n+1)/6) which comes from area considerations.

They also found an upper bound of 1+2+3+. . .+m = m(m+1)/2, since this assumes all the strips are vertical. They note that this upper bound is only satisfied for m=1 and m=3, since usually m(m+1)/2 is not divisible by all the numbers from 1 to m. Berend Jan van der Zwaag improved this upper bound to m2/2 by considering the gap under the two largest strips.

Dane Brooke also considered tilings of squares where more than one of each strip is allowed. He seemed to think that all squares larger than the lower bounds above could be so tiled. Sasha Ravsky confirmed this.

Philippe Fondanaiche gave the maximum size square than can be tiled with strips of size 1 through n, though he wasn't always correct.

Jeremy Galvagni conjectured that for each n≥6, there is some square strip tiling of the n x n square. This seems likely. Can anyone show this?

Sasha Ravsky found an error in someone else's tiling of a 38x38 square with 10 strips.

One can also think about tiling triangles with strips of triangles. Berend Jan van der Zwaag and I found the tilings below:

Possible Strip Tilings of Triangles

Number of StripsPossible Sizes of TriangleUnknown
11 
23 
35, 6 
47, 8, 9, 10 
59, 10, 11, 12, 13, 14, 15 
611, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 
713, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
815, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 3616?

After I wondered about the corresponding problem in three dimensions (tiling cubes with cube strips), Joseph DeVincentis suggested using slabs of cubes. Even with slabs, it is hard to form cubes (though you can make a 6x6x6 cube with slabs of width 1, 2, and 3), so I started looking for the smallest boxes that could made from slabs of 1, 2, 3, . . . n. Here are the smallest I've found so far. Can anyone do better?

Smallest Slab Tilings of Boxes

Number of StripsSmallest Volume of BoxSmallest Width of Box
11x1x11x1x1
22x2x32x2x3
33x5x63x5x6
44x6x74x6x7
56x8x196x8x19
66x9x296x16x19

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