
Problem 6. A rectangle $m \times n(m>1, n>1)$ is divided into $m n$ squares $1 \times 1$ with lines, parallel to its sides. In how many ways could two of the squares be canceled and the remaining part be covered with dominoes $2 \times 1$ ?


Solution. Denote by $F(m, n)$ the number we are looking for. Since every domino covers exactly two squares, then $F(m, n)=0$ if $m$ and $n$ are odd.

Figure 5 .

![](https://cdn.mathpix.com/cropped/2024_06_03_2b3603673083113190ceg-4.jpg?height=246&width=371&top_left_y=1353&top_left_x=451)

Let at least one of the numbers $m$ and $n$ be even. We color the squares in two colors - white and black in such a way that every two neighbor squares (with common side) are of different colors (Figure 5). The number $S_{0}$ of the white squares is equal to the number $S_{1}$ of the black ones and $S_{0}=S_{1}=\frac{m n}{2}$.

Each domino covers one white and one black square. If two white or two black squares are canceled, then it is impossible to cover by dominoes the remaining part of the rectangle. Now we shall show that if one white and one black squares are canceled then the remaining part can be covered by dominoes.

Since $m n$ is even, then $m n=2 t$, where $t \geq 2$. We make induction with respect to $t$. The case $t=2$ is obvious. Let $t_{0}>2$ and the proposition is true for all $2 \leq t \leq t_{0}$. Let $m n=2\left(t_{0}+1\right)$. Denote by $T_{1}$ the rectangle consisted of the first two rows of the considered rectangle, and by $T_{2}$ - the rectangle consisted of the remaining rows. If the two canceled squares are in $T_{1}$ or in $T_{2}$, then we can cover each of the rectangles by dominoes and consequently we can cover the given rectangle.

Let one of the canceled squares be in $T_{1}$, and the other - in $T_{2}$. We place a domino in such a way that it covers one square from $T_{1}$ and one square from $T_{2}$. It is also possible that the canceled square from $T_{1}$ and the covered square from $T_{1}$ are of different colors. Thus, the canceled square from $T_{2}$ and the covered square from $T_{2}$ are of different colors. According to the inductive assumption the remaining part of $T_{1}$ and the remaining part of $T_{2}$ can be covered. Thus, the rectangle can be covered too.

Finally one white and one black squares can be chosen in $S_{0} \cdot S_{1}=\left(\frac{m n}{2}\right)^{2}$ ways. Therefore, in this case $F(m, n)=\frac{m^{2} n^{2}}{4}$.

