2007 Alabama ARML TST Problems/Problem 11
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
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 |