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×7, 8×8, or 9×9 square:

ANSWERS

Joseph DeVincentis found all but five of the tilings below for n≤13. He furnished pictures for 10≤n≤12. Philippe Fondanaiche and Jeremy Galvagni found many of these tilings as well. Berend Jan van der Zwaag found many hard to find tilings. Patrick Hamlyn alone found the elusive 12/29 tiling and those for n≥13.

Possible Strip Tilings of Squares

Number of Strips	Possible Sizes of Square
1	1
2
3	6
4	7, 8, 9
5	9, 10, 11, 12
6	11, 12, 13, 14, 15, 16, 18
7	13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24
8	15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
9	19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40
10	22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45
11	25, 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
12	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, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 72
13	31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41,42, 44, 45, 58, 60, 61, 63, 64, 65, 66, 68, 69, 70, 72, 74, 76, 78, 79, 80, 81, 84
14	35, 36, 37, 38, 40, 41, 42, 43
15	37, 39, 41, 42, 44, 47

Joseph DeVincentis and Berend Jan van der Zwaag have also proved some tilings impossible.

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 m²/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×n square. This seems likely. Can anyone show this?

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

In 2015, George Sicherman showed the missing tilings were impossible.

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 6×6×6 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 Strips	Smallest Volume of Box	Smallest Width of Box
1	1×1×1	1×1×1
2	2×2×3	2×2×3
3	3×5×6	3×5×6
4	4×6×7	4×6x×7
5	6×8×19	6×8×19
6	6×9×29	6×16×19

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