A Problem From The 2023 IOQM Based On Recurrence

A hand-picked problem from the 2023 IOQM, that requires the use of recurrence.

Problem contributed by debosmita1729

The total number of squares covered using one $2 \times 2$ square and seven $2 \times 1$ dominoes is $16$.

Since we need to cover only $2 \times 7 = 14$ squares, we can use either seven $2 \times 1$ dominoes only or five $2 \times 1$ dominoes and one $2 \times 2$ dominoes.

We will count these two cases separately.

Before, we begin we will look at the generic case of how many ways are there to fill up a $2 \times n$ rectangle using only dominoes.

-----------book page break-----------

Let $a_n$ be the number of ways to tile a $2 \times n$ rectangle using only $2 \times 1$ dominoes.

A $2 \times 1$ rectangle can be filled in exactly $1$ way, therefore $a_1 = 1$

A $2 \times 2$ rectangle can be filled in $2$ ways (both dominoes in horizontal or vertical positions), therefore $a_2 = 2$

For any $n \gt 2$,

If we have filled up till $n - 1$ length, then we can reach $n$ by adding just $1$ domino in a vertical position.

If we have filled up till $n-2$ length, then we can reach $n$ by adding just $2$ dominoes in horizontal position. (Note that we cannot use two dominoes in vertical position, because that will be the same arrangement as going to $n-1$ first then adding one more domino to reach $n$, as the case before.)

Therefore, this sequence satisfies the recurrence relation:

$$
a_n = a_{n-1} + a_{n-2}
$$

Now let us calculate the two cases mentioned earlier.

-----------book page break-----------

$Case\ 1:$ Using all $seven$ $2 \times 1$ dominoes
We calculate the values of $a_n$ for $n$ up to $7$:
\begin{align*}
a_0 &= 1 \\
a_1 &= 1 \\
a_2 &= 1 + 1 = 2 \\
a_3 &= 2 + 1 = 3 \\
a_4 &= 3 + 2 = 5 \\
a_5 &= 5 + 3 = 8 \\
a_6 &= 8 + 5 = 13 \\
a_7 &= 13 + 8 = 21
\end{align*}

There are $21$ ways for this case.

$Case\ 2$: Using $one$ $2 \times 2$ square and $five$ $2 \times 1$ dominoes
We separate the problem into two disjoint cases based on the number of $2 \times 2$ tiles used.

The square tile can be placed at any position $k$ (where $k$ is the number of columns to the left of the square, and $0 \le k \le 5$). This placement splits the remaining area into a left rectangle of size $2 \times k$ and a right rectangle of size $2 \times (5-k)$.

The total number of ways for this case is the sum of the products of the ways to tile the left and right sections:
$$
N_2 = \sum_{k=0}^{5} a_k \cdot a_{5-k}
$$

-----------book page break-----------

Expanding the summation:
\begin{align*}
N_2 &= (a_0 \cdot a_5) + (a_1 \cdot a_4) + (a_2 \cdot a_3) + (a_3 \cdot a_2) + (a_4 \cdot a_1) + (a_5 \cdot a_0) \\
N_2 &= (1 \cdot 8) + (1 \cdot 5) + (2 \cdot 3) + (3 \cdot 2) + (5 \cdot 1) + (8 \cdot 1) \\
N_2 &= 8 + 5 + 6 + 6 + 5 + 8 \\
N_2 &= 38
\end{align*}

The total number of ways to tile the $2 \times 7$ rectangle is the sum of the ways from $Case\ 1$ and $Case\ 2$.
$$
\text{Total Ways} = N_1 + N_2 = 21 + 38 = 59
$$

There are $59$ ways to tile the rectangle.