# 2007 Alabama ARML TST Problems/Problem 11

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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