2007 Alabama ARML TST Problems/Problem 11

From AoPSWiki

Problem

In how many distinct ways can a rectangular grid be tiled with non-overlapping rectangular tiles?

Solution

In both solutions we consider the grid to have rows and columns.

Solution 1

There are either vertical tiles, vertical and horizontal, vertical and horizontal, etc. The horizontal tiles always have to form blocks .

If we now consider tilings that consist of vertical tiles and blocks of three horizontal tiles, it is clear that there are such tilings. Hence we get that the total number of tilings in our case is:

It isn't that such a pain to compute, so we do:

Solution 2

Let be the number of ways to tile a rectangle.

Obviously .

Consider a rectangle with . Take a look at the tile that contains the upper right corner. It can be either vertical or horizontal. If it is vertical, we still need to tile the remaining columns. If it is horizontal, the other two cells in the rightmost column must be covered by horizontal tiles as well. We are then left with columns to tile.

This gives us the recurrence for .

Using it we can now compute:

  n | T(n)
------------
  3 |   2
  4 |   3
  5 |   4
  6 |   6
  7 |   9
  8 |  13
  9 |  19
 10 |  28
 11 |  41
 12 |  60
 13 |  88
 14 | 129
 15 | 189
 16 | 277
 17 | 406

See also