Let $n \ge 2$ be a positive integer. Each square of an $n\times n$ board is coloured red or blue. We put dominoes on the board, each covering two squares of the board. A domino is called even if it lies on two red or two blue squares and colourful if it lies on a red and a blue square. Find the largest positive integer $k$ having the following property: regardless of how the red/blue-colouring of the board is done, it is always possible to put $k$ non-overlapping dominoes on the board that are either all even or all colourful.
Problem
Source: Dutch BxMO/EGMO TST 2015 p3
Tags: combinatorics, Coloring, board
Mr.Chagol
24.08.2019 15:12
Is a valid tiling necessary? Or it is okay to leave out squares(saying due to n odd has no valid tiling)
Mathotsav
24.08.2019 19:35
We claim that the answer is $\lfloor \frac{n^2}{4} \rfloor$. We divide this into two cases: (a) $n$ is even. First of all, cover the entire board using dominoes. Note that there are $\frac{n^2}{2}$ dominoes so at least $\frac{n^2}{4}$ dominoes must be of one kind, so the answer is greater than or equal to that. The following colouring ensures that the answer is at most $\frac{n^2}{4}$: R R R R …. B R B R …. R R R R …. B R B R …. ………………. continuing the pattern like that, as $n$ is even here. It can be seen why it is at most $\frac{n^2}{4}$ here by induction. So, we proved the case for even. (b)$n$ is odd. In this case, fill the board with $\frac{n^2-1}{2}$ dominoes so that only one square is left. Again, we see that at least $\frac{n^2-1}{4}$ are of the same kind, so the answer is at least $\frac{n^2-1}{4}$. The following colouring ensures at most $\frac{n^2-1}{4}$: R R R R … R B R B R … B R R R R … R …………………. R R R R … R again we can see by induction that this coloring doesn't allow more than $\frac{n^2-1}{4}$ dominoes of the same kind. Hence, we are done, so the answer is in general $\lfloor \frac{n^2}{4} \rfloor$.