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

Number of Strips | Possible Sizes of Square | Unknown |
---|---|---|

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 | 18? |

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 | 21? |

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 | 24? |

12 | 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 | 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 m^{2}/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.

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?

Number of Strips | Smallest Volume of Box | Smallest Width of Box |
---|---|---|

1 | 1x1x1 | 1x1x1 |

2 | 2x2x3 | 2x2x3 |

3 | 3x5x6 | 3x5x6 |

4 | 4x6x7 | 4x6x7 |

5 | 6x8x19 | 6x8x19 |

6 | 6x9x29 | 6x16x19 |

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.