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

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

Page

Toolbox

Search

2007 Alabama ARML TST Problems/Problem 11

Contents

Problem

Solution

Solution 1

Solution 2

See also