(RMM 2016, partially covered in class) Let $n \geqslant m$ be integers.

What is the maximum number of dominoes $1 \times 2$ (rotations allowed) that can be placed on a board $m \times 2 n$ such that the bottom row is completely covered by horizontal dominoes, and such that no two dominoes form a $2 \times 2$ square?
We can achieve $m n-[m / 2]$ with the brick arrangement.

Place the origin at the bottom left, so that the bottom row consists of the cells $(k, 1)$ with $1 \leqslant k \leqslant 2 n$. Call a good position any set of two cells $\{(k+2 \ell, k),(k+2 \ell+$ $1, k)\}$ with $0 \leqslant \ell \leqslant n-k$.

First, assume that each good position is entirely covered by a horizontal domino. Color the cells of the checkerboard in black and white as usual. The complement of the union of the good positions is the union of two triangular zones on which the difference between the number of black cells and the number of white cells is $[\mathrm{m} / 2]$, so on each triangular zone, there are at least $[\mathrm{m} / 2]$ unoccupied cells. Therefore, we can place at most $m n-[m / 2]$ dominos.

Now, consider the general case. It suffices to transform a configuration into another one with at least as many dominos, but with fewer good positions not covered. Take a good position, of minimal ordinate, which is not entirely covered by a domino.

If it is empty, we can place a horizontal domino there and possibly remove the horizontal domino just above if there was one.

If it is not empty, suppose, for example, that the left cell is occupied. It is easy to see that the domino $D$ that occupies it is vertical, and that the right cell is empty, so we can move $D$ to cover the good position.