
5. Determine the number of all coverings of a chessboard $3 \times 10$ by (nonoverlapping) pieces $2 \times 1$ which can be placed both horizontally and vertically.

(Stanislava Sojáková)


Solution. Let us solve a more general problem of determining the number $a_{n}$ of all coverings of a chessboard $3 \times 2 n$ by pieces $2 \times 1$, for a given natural $n .{ }^{2}$ We will attack the problem by a recursive method, starting with $n=1$.

The value $a_{1}=3$ (for the chessboard $3 \times 3$ ) is evident (see Fig. 2). To prove that $a_{2}=11$ by a direct drawing all possibilities is too laborious. Instead of this, we introduce new numbers $b_{n}$ : Let each $b_{n}$ denote the number of all "incomplete" coverings of a chessboard $3 \times(2 n-1)$ by $3 n-2$ pieces $2 \times 1$, when a fixed corner field $1 \times 1$ (specified in advance, say the lower right one) remains uncovered. Thanks to the axial symmetry, the numbers $b_{n}$ remain to be the same if the fixed uncovered corner field will be the upper right one. Moreover, it is clear that $b_{1}=1$.
![](https://cdn.mathpix.com/cropped/2024_04_17_207c009ec429634e3f25g-06.jpg?height=202&width=618&top_left_y=2040&top_left_x=752)

Fig. 2

Now we are going to prove that for each $n>1$, the following equalities hold:

$$
b_{n}=a_{n-1}+b_{n-1} \quad \text { and } \quad a_{n}=a_{n-1}+2 b_{n} .
$$[^1]

The first equality in (1) follows from a partition of all (above described) "incomplete" coverings of a chessboard $3 \times(2 n-1)$ into two (disjoint) classes which are formed by coverings of types A and B, respectively, see Fig. 3. Notice that the numbers of elements (i.e. coverings) in the two classes are $a_{n-1}$ and $b_{n-1}$, respectively.

![](https://cdn.mathpix.com/cropped/2024_04_17_207c009ec429634e3f25g-07.jpg?height=203&width=320&top_left_y=521&top_left_x=662)

A

![](https://cdn.mathpix.com/cropped/2024_04_17_207c009ec429634e3f25g-07.jpg?height=188&width=305&top_left_y=523&top_left_x=1024)

B

Fig. 3

Similarly, the second equality in (1) follows from a partition of all coverings of a chessboard $3 \times 2 n$ into three (disjoint) classes which are formed by coverings of types C, D and E respectively, see Fig. 4. It is evident that the numbers of elements in the three classes are $a_{n-1}, b_{n}$ and $b_{n}$, respectively.
![](https://cdn.mathpix.com/cropped/2024_04_17_207c009ec429634e3f25g-07.jpg?height=236&width=1024&top_left_y=1112&top_left_x=480)

Fig. 4

Now we are ready to compute the requested number $a_{5}$. Since $a_{1}=3$ and $b_{1}=1$, the proved equalities (1) successively yield

$$
\begin{gathered}
b_{2}=a_{1}+b_{1}=4, a_{2}=a_{1}+2 b_{2}=11, b_{3}=a_{2}+b_{2}=15, a_{3}=a_{2}+2 b_{3}=41, \\
b_{4}=a_{3}+b_{3}=56, a_{4}=a_{3}+2 b_{4}=153, b_{5}=a_{4}+b_{4}=209, a_{5}=a_{4}+2 b_{5}=571 .
\end{gathered}
$$

Answer. The number of coverings of the chessboard $3 \times 10$ equals 571 .

Remark. Let us show that the numbers $a_{n}$ of coverings of a chessboard $3 \times 2 n$ by pieces $2 \times 1$ satisfy the following recurrence equation

$$
a_{n+2}=4 a_{n+1}-a_{n} \text { for each } n \geqslant 1 \text {. }
$$

(Thus the numbers $a_{n}$ can be computed without using auxiliary numbers $b_{n}$ from the above solution.) We prove (2) by excluding the numbers from the relations (1):

$$
\begin{aligned}
a_{n+2} & =a_{n+1}+2 b_{n+2}=a_{n+1}+2\left(a_{n+1}+b_{n+1}\right) \\
& =3 a_{n+1}+2 b_{n+1}=3 a_{n+1}+\left(a_{n+1}-a_{n}\right)=4 a_{n+1}-a_{n}
\end{aligned}
$$

Finally, let us remind a well known result: each sequence $\left(a_{n}\right)_{n=1}^{\infty}$ of numbers satisfying (2) is of the form $a_{n}=C_{1} \lambda_{1}^{n}+C_{2} \lambda_{2}^{n}$, where $\lambda_{1,2}=2 \pm \sqrt{3}$ are the roots of the equation $\lambda^{2}=4 \lambda-1$ while $C_{1,2}$ are arbitrary constants. Taking in account our values $a_{1}=3$ and $a_{2}=11$, we conclude that for each $n$, the number $a_{n}$ of all coverings of a chessboard $3 \times 2 n$ by pieces $2 \times 1$ is given by a direct formula

$$
a_{n}=\frac{3+\sqrt{3}}{6} \cdot(2+\sqrt{3})^{n}+\frac{3-\sqrt{3}}{6} \cdot(2-\sqrt{3})^{n} .
$$
