Task 3. Let $n \geq 2$ be a positive integer. Each cell of an $n \times n$ board is colored red or blue. We place dominoes on the board, each covering two cells. We call a domino plain if it lies on two red or two blue cells, and colorful if it lies on one red and one blue cell. Find the largest positive integer $k$ with the following property: no matter how the red/blue coloring of the board is done, it is always possible to place $k$ non-overlapping dominoes on the board that are either all plain or all colorful.
Solution. We prove that $k=\left\lfloor\frac{n^{2}}{4}\right\rfloor$ is the largest possible value.

Suppose $n$ is even. Then it is possible to cover the board with $\frac{n^{2}}{2}$ dominoes (ignoring colors). Since there are $\frac{n^{2}}{2}$ dominoes, all of which are either colorful or plain, there are at least $\left\lfloor\frac{n^{2}}{4}\right\rfloor=\frac{n^{2}}{4}$ colorful or at least $\left\lfloor\frac{n^{2}}{4}\right\rfloor=\frac{n^{2}}{4}$ plain dominoes. If $n$ is odd, we can cover the board with $\frac{n^{2}-1}{2}$ dominoes. (Note that this number is an even integer.) Of these dominoes, there are at least $\frac{n^{2}-1}{4}=\left\lfloor\frac{n^{2}}{4}\right\rfloor$ colorful or at least $\frac{n^{2}-1}{4}=\left\lfloor\frac{n^{2}}{4}\right\rfloor$ plain. This proves that it is always possible to place at least $\left\lfloor\frac{n^{2}}{4}\right\rfloor$ colorful dominoes or at least $\left\lfloor\frac{n^{2}}{4}\right\rfloor$ plain dominoes on the board. We now prove that it is possible to choose the coloring of the squares in red and blue such that there are no more than $\left\lfloor\frac{n^{2}}{4}\right\rfloor$ plain and also no more than $\left\lfloor\frac{n^{2}}{4}\right\rfloor$ colorful dominoes.

Color the squares of the board black and white like a chessboard, so that the bottom-left square is white. If $n$ is even, there are as many white as black squares, namely $\frac{n^{2}}{2}$. If $n$ is odd, there is one less black square, and the number of black squares is $\frac{n^{2}-1}{2}=\left\lfloor\frac{n^{2}}{2}\right\rfloor$. In both cases, this is an even number of squares, since for odd $n$ we have $n^{2} \equiv 1$ mod 4. Color half of the black squares red and all other squares blue. Then there are $\left\lfloor\frac{n^{2}}{4}\right\rfloor$ red squares, so we can place at most $\left\lfloor\frac{n^{2}}{4}\right\rfloor$ non-overlapping colorful dominoes on the board: each of these dominoes covers a red square. A plain domino cannot cover two red squares, as no two adjacent squares are red. It must therefore cover two blue squares. At least one of these is a black-blue square, so the number of plain dominoes is at most the number of black-blue squares, which is $\left\lfloor\frac{n^{2}}{4}\right\rfloor$. Therefore, both the colorful and the plain dominoes can have at most $\left\lfloor\frac{n^{2}}{4}\right\rfloor$ on the board at the same time.

We conclude that the maximum $k$ is indeed $k=\left\lfloor\frac{n^{2}}{4}\right\rfloor$.