Difference between revisions of "2007 Alabama ARML TST Problems/Problem 11"

Latest revision as of 08:40, 26 January 2009

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

@@ Line 1: / Line 1: @@
 ==Problem==
-In how many distinct ways can a rectangular <math>3\cdot 17</math> grid be tiled with 17 non-overlapping <math>1\cdot 3</math> rectangular tiles?
+In how many distinct ways can a rectangular <math>3\times 17</math> grid be tiled with <math>17</math> non-overlapping <math>1\cdot 3</math> rectangular tiles?
 ==Solution==
-There are either 17 vertical tiles, 14 vertical and 3 horizontal, 11 vertical and 6 horizontal, etc. We can imagine the horizontal tiles blocks of 3 1*1 tiles. Thus, there are
+In both solutions we consider the grid to have <math>3</math> rows and <math>17</math> columns.
+=== Solution 1 ===
+There are either <math>17</math> vertical tiles, <math>14</math> vertical and <math>3</math> horizontal, <math>11</math> vertical and <math>6</math> horizontal, etc.
+The horizontal tiles always have to form blocks <math>3\times 3</math>.
+If we now consider tilings that consist of <math>a</math> vertical tiles and <math>b</math> blocks of three horizontal tiles, it is clear that there are <math>a+b \choose b</math> such tilings. Hence we get that the total number of tilings in our case is:
 <cmath>\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!}</cmath>
@@ Line 10: / Line 18: @@
 <cmath>1+15+78+165+126+21=\boxed{406}</cmath>
+=== Solution 2 ===
+Let <math>T_n</math> be the number of ways to tile a <math>3\times n</math> rectangle.
+Obviously <math>T_0=T_1=T_2=1</math>.
+Consider a <math>3\times n</math> rectangle with <math>n\geq 3</math>. 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 <math>n-1</math> 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 <math>n-3</math> columns to tile.
+This gives us the recurrence <math>T_n = T_{n-1} + T_{n-3}</math> for <math>n\geq 3</math>.
+Using it we can now compute:
+   n | T(n)
+ ------------
+|   2
+|   3
+|   4
+|   6
+|   9
+|  13
+|  19
+|  28
+|  41
+|  60
+|  88
+| 129
+| 189
+| 277
+| 406
 ==See also==
 {{ARML box|year=2007|state=Alabama|num-b=10|num-a=12}}

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