(Luxembourg). Let $n$ be a positive integer. Dominoes are placed on a $2 n \times 2 n$ board in such a way that every cell of the board is adjacent to exactly one cell covered by a domino. For each $n$, determine the largest number of dominoes that can be placed in this way.
(A domino is a tile of size $2 \times 1$ or $1 \times 2$. Dominoes are placed on the board in such a way that each domino covers exactly two cells of the board, and dominoes do not overlap. Two cells are said to be adjacent if they are different and share a common side.)
Let $M$ denote the maximal number of dominoes that can be placed on the chessboard. We claim that $M=n(n+1) / 2$. The proof naturally splits into two parts: we first prove that $n(n+1) / 2$ dominoes can be placed on the board, and then show that $M \leq n(n+1) / 2$ to complete the proof.

We construct placings of the dominoes by induction. The base cases $n=1$ and $n=2$ correspond to the placings
![](https://cdn.mathpix.com/cropped/2024_11_22_6e3db21aae2cba1f8d74g-05.jpg?height=238&width=443&top_left_y=1012&top_left_x=812)

Next, we add dominoes to the border of a $2 n \times 2 n$ chessboard to obtain a placing of dominoes for the $2(n+2) \times 2(n+2)$ board,
![](https://cdn.mathpix.com/cropped/2024_11_22_6e3db21aae2cba1f8d74g-05.jpg?height=455&width=772&top_left_y=1400&top_left_x=642)
depending on whether $n$ is odd or even. In these constructions, the interior square is filled with the placing for the $2 n \times 2 n$ board. This construction adds $2 n+3$ dominoes, and therefore places, in total,

$$
\frac{n(n+1)}{2}+(2 n+3)=\frac{(n+2)(n+3)}{2}
$$

dominoes on the board. Noticing that the contour and the interior mesh together appropriately, this proves, by induction, that $n(n+1) / 2$ dominoes can be placed on the $2 n \times 2 n$ board.

To prove that $M \leq n(n+1) / 2$, we border the $2 n \times 2 n$ square board up to a $(2 n+2) \times(2 n+2)$ square board; this adds $8 n+4$ cells to the $4 n^{2}$ cells that we have started with. Calling a cell covered if it belongs to a domino or is adjacent to a domino, each domino on the $2 n \times 2 n$ board is seen to cover exactly 8 cells of the $(2 n+2) \times(2 n+2)$ board (some of which may belong to the border). By construction, each of the $4 n^{2}$ cells of the $2 n \times 2 n$ board is covered by precisely one domino.

If two adjacent cells on the border, away from a corner, are covered, then there will be at least two uncovered cells on both sides of them; if one covered cell lies between uncovered cells, then again, on both sides of it there will be at least two uncovered cells; three or more adjacent cells cannot be all covered. The following diagrams, in which the borders are shaded, $\times$ marks an uncovered cell on the border, + marks a covered cell not belonging to a domino, and - marks a cell which cannot belong to a domino, summarize the two possible situations,

| $\cdots$ | $\times$ | $\times$ | + | + | $\times$ | $\times$ | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|  | - | + |  |  | + | - |  |
|  |  | - | + | + | - |  |  |
|  |  |  | - | - |  |  |  |
| $\vdots$ |  |  |  |  |  |  | $\vdots$ |

or
![](https://cdn.mathpix.com/cropped/2024_11_22_6e3db21aae2cba1f8d74g-06.jpg?height=299&width=691&top_left_y=670&top_left_x=1122)

Close to a corner of the board, either the corner belongs to some domino,

| $\times$ | + | + | $\times$ | $\times$ | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: |
| + |  |  | + | - |  |
| $\times$ | + | + | - |  |  |
| $\times$ | - | - |  |  |  |
| $\vdots$ |  |  |  |  |  |

or one of the following situations, in which the corner cell of the original board is not covered by a domino, may occur:
![](https://cdn.mathpix.com/cropped/2024_11_22_6e3db21aae2cba1f8d74g-06.jpg?height=358&width=1438&top_left_y=1534&top_left_x=309)

It is thus seen that at most half of the cells on the border, i.e. $4 n+2$ cells, may be covered, and hence

$$
M \leq\left[\frac{4 n^{2}+(4 n+2)}{8}\right]=\left[\frac{n(n+1)}{2}+\frac{1}{2}\right]=\frac{n(n+1)}{2}
$$

which completes the proof of our claim.