(CMC 2020) Let $n$ be an integer. We call $C_{n}$ the grid of side $n$ from which one diagonal has been removed. For which integers $n \geqslant 2$ can $C_{n}$ be tiled with tiles consisting of three adjacent squares in the shape of an $\mathrm{L}$ (tiles can be flipped in any direction, but must not overlap or extend outside of $C_{n}$ or onto the diagonal).
It is necessary that the number of cells in $C_{n}$ is a multiple of 3, in other words, $n(n-1)$ is divisible by 3. For this, $n \equiv 0[3]$ or $n \equiv 1[3]$. Then, we notice that if we know how to tile $C_{n}$, then:

- we can tile $C_{n+6}$ if $n$ is even
- we can tile $C_{n+6}$ if $n$ is odd
- we can tile $C_{n+2}$ if $n \equiv 1[3]$

It remains to exhibit the tilings of $C_{3}$, $C_{7}$, $C_{10}$, and to show that $C_{4}$ and $C_{6}$ are impossible to tile. The suitable integers $n$ are therefore 3 and all those of the form $6k+i$ with $k \in \mathbb{N}^{*}$ and $i \in \{1,3,4,6\}$.

## Strategic Coloring and Tiling Problems

When a problem takes place on a grid or a graph, coloring the points in a clever way often reveals useful properties. For example, in chess, a bishop always stays on the same color of square, while a knight changes color with each move.

Coloring techniques are used to solve certain tiling problems, with a well-chosen coloring (in a checkerboard pattern, in stripes, etc).

## Example 3.

Consider an $n \times n$ chessboard for $n \in \mathbb{N}^{*}$. We remove the two opposite corners. Can it be tiled with $2 \times 1$ dominoes?

If $n$ is odd, it is clear that the answer is no.

If $n$ is even, we observe that the two removed squares are of the same color. However, a domino, regardless of where and how it is placed, always covers one black and one white square. Therefore, it is impossible.

Now, we remove two adjacent corners. This time, we can exhibit a construction that works for all even $n$.