### 2019 EGMO #2

Let $n$ be a positive integer. Dominoes are placed on a $2n \times 2n$ 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.)

Shade in the rings of even side length, displayed visually below. Notice that this satisfies the given condition.

Shade in the rings of even side length, displayed visually below. Notice that this satisfies the given condition.

Now we have to maximize the number of dominoes that can be placed this way. For each domino, let the set of $6$ distinct squares bordering it be called its

*area*. Observe that no cell can belong to the area of $2$ dominoes. Next, since each cell is adjacent to exactly $2$ shaded cells, we know that for each domino, $4$ squares in its area will be shaded. There are $2n^2+2n$ shaded cells. So, there are $$\frac{2n(n+1)}{4}=\frac{n(n+1)}{2}$$ dominoes.We can easily form the construction.

So, we are done. $\square$

## Comments

## Post a Comment