2023 IOQM/Problem 8

Problem 8

Given a 2 x 2 tile and seven dominoes (2 x 1 tile), find the number of ways of tilling a 2 x 7 rectangle using some of these tiles.

Solution

Let $a_n$ be the total number of ways of tiling a 2 x n rectangle using only dominoes. So $a_n=a_{n-1}+a_{n-2}$ . Obviously $a_1=1$ and $a_2=2$ (remember right now we are not considering the 2 x 2 tile). This will give us $a_7=21$ . Now we introduce the 2 x 2 tile. Number of ways of tiling the 2 x 7 board will totally depend on the position of the 2 x 2 tile.

Case I: If the 2 x 2 tile is on the 1st column of the 2 x 7 board then the numbers of ways for tiling the rest of the board would be $a_5=8$ .
Case II: If the 2 x 2 tile is on the 2nd column of the 2 x 7 board then numbers of ways of tiling the rest of the board will be $a_1a_4=5$ .
Case III: If the 2 x 2 tile is on the 3rd column of the board then the number of ways of tiling the rest of the board will be $a_2a_3=6$ .

Now we will add all the cases and multiply by 2 (Why? Because the cases will repeat again). $2(8+5+6)=38$ , remember this is when we consider a 2 x 2 tile, without the 2 x 2 tile there are $a_7=21$ ways. So the total number of ways of tiling a 2 x 7 board using a 2 x 2 tile and 2 x 1 dominos is $\boxed{38+21=\textbf{59}}$

~Lakshya Pamecha

Page

Toolbox

Search

2023 IOQM/Problem 8

Problem 8

Solution