2007 Alabama ARML TST Problems/Problem 11

Problem

In how many distinct ways can a rectangular $3\times 17$ grid be tiled with $17$ non-overlapping $1\cdot 3$ rectangular tiles?

Solution

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

Solution 1

There are either $17$ vertical tiles, $14$ vertical and $3$ horizontal, $11$ vertical and $6$ horizontal, etc. The horizontal tiles always have to form blocks $3\times 3$.

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

\[\dfrac{17!}{17!}+\dfrac{15!}{14!}+\dfrac{13!}{11!\cdot 2!}+\dfrac{11!}{8!\cdot 3!}+\dfrac{9!}{5!\cdot 4!}+\dfrac{7!}{2!\cdot 5!}\]

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

\[1+15+78+165+126+21=\boxed{406}\]

Solution 2

Let $T_n$ be the number of ways to tile a $3\times n$ rectangle.

Obviously $T_0=T_1=T_2=1$.

Consider a $3\times n$ rectangle with $n\geq 3$. 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 $n-1$ 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 $n-3$ columns to tile.

This gives us the recurrence $T_n = T_{n-1} + T_{n-3}$ for $n\geq 3$.

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

2007 Alabama ARML TST (Problems)
Preceded by:
Problem 10
Followed by:
Problem 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Invalid username
Login to AoPS