63rd Czech and Slovak Mathematical Olympiad

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

The value $a_1=3$ (for the chessboard $3\times 2$) 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 (2n-1)$ by $3n-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$.



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}\text{and}{a}_n=a_{n-1}+2b_n.(1)$$



Fig. 3

Similarly, the second equality in (1) follows from a partition of all coverings of a chessboard $3\times 2n$ 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.



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{array}{rl}{b}_2& =a_1+b_1=4,a_2=a_1+2b_2=11,b_3=a_2+b_2=15,a_3=a_2+2b_3=41,\\ b_4& =a_3+b_3=56,a_4=a_3+2b_4=153,b_5=a_4+b_4=209,a_5=a_4+2b_5=571.\end{array}$$

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