Let $m,n\geq 2$. One needs to cover the table $m \times n$ using only the following tiles: Tile 1 - A square $2 \times 2$. Tile 2 - A L-shaped tile with five cells, in other words, the square $3 \times 3$ without the upper right square $2 \times 2$. Each tile 1 covers exactly $4$ cells and each tile 2 covers exactly $5$ cells. Rotation is allowed. Determine all pairs $(m,n)$, such that the covering is possible.
Problem
Source: Rioplatense L-2 2022 #2
Tags: geometry, rotation, combinatorics
mathitoo
17.02.2023 18:57
Let's look at the board by coloring its columns in an alternating fashion with 3 colors and let $A_i$ be the set of cells with the color $i$: \[ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\\hline \end{array} \]From this coloring, we get that as we put either of the two tiles the amount of cells covered from each color change their parity or stays the same. Then, the amount of cells from each color on the board has to be of the same parity. Suppose $3\nmid m$, then, $A_1$ has n mores cells than $A_3$, but $A_1\equiv A_3 (mod\ 2)\Longrightarrow 2\mid n$ Analogously, by coloring its rows $3\nmid n\Longrightarrow 2\mid n$, then $3\mid m,n; 2\mid m,n, 6\mid m$ or $6\mid n$ the examples are not that hard, so they are left for the reader