IMO Team Selection Test 3

First suppose that $n$ is odd. Then we must have $V\ge 1$, as the difference must be odd. We show that $V=1$ is always possible. Colour the vertical domino tiles in the odd numbered columns red and the vertical domino tiles in the even numbered columns blue. As in every row, every horizontal domino tile covers a square in an even numbered column and one in an odd numbered column, every row contains one more square covered by a red domino tile than squares covered by a blue domino tile. Now colour the horizontal domino tile in each row alternatingly blue and red (starting with blue). If the number of horizontal domino tiles is even, then at the end, the number of red squares will be one more than that of blue squares; if the number of horizontal domino tiles is odd, then at the end, the number of blue squares will be one more than that of red squares. The difference will therefore always be equal to 1.

Now suppose that $n\equiv 2(\mathrm{mod}4)$. Then we have $V\ge 2$ if Jetze places every domino tile horizontally; then every row contains an odd number of horizontal domino tiles. We show that $V=2$ is always possible. Use the same strategy as in the odd case. After colouring the vertical domino tiles, the numbers of red and blue squares are equal. If we alternatingly colour the horizontal domino tiles in each row blue and red again, we see that in the end, in every row the difference between the number of red and blue squares is 0 or 2.

Finally, suppose that $n\equiv 0(\mathrm{mod}4)$. We show that $V=0$ is always possible. Number the rows from top to bottom from 1 up to $m$, and let $b_i$ be the number of vertical domino tiles of which the top square is in row $i$. By induction on $i$, we easily show that $b_i$ is even, using the fact that a horizontal domino tile always covers an even number of squares in a row. We now colour the vertical domino tiles in rows $i$ and $i+1$ as follows: if $b_i\equiv 0(\mathrm{mod}4)$, we colour half of them red, and the other half blue, and if $b_i\equiv 2(\mathrm{mod}4)$ we colour two more domino tiles red than we colour blue if $i$ is even, and we colour two more domino tiles blue than we colour red if $i$ is odd. We show that we can now colour the horizontal domino tiles in each row $k$ in such a way that every row has the same number of red and blue squares. If $b_{k-1}\equiv b_k\equiv 0(\mathrm{mod}4)$, then vertical domino tiles in row $k$ cover the same number of red squares as blue squares. Moreover, the number of horizontal domino tiles in row $k$ is even, so we can simply colour half of them red and half of them blue. If $b_{k-1}\equiv b_k\equiv 2(\mathrm{mod}4)$, then vertical domino tiles in row $k$ again cover the same number of red squares as blue squares, since of $k-1$ and $k$, one is odd and one is even. Again, the number of horizontal domino tiles in row $k$ is even, so we can again simply colour half of them red and half of them blue. If $b_{k-1}\not\equiv b_k(\mathrm{mod}4)$, then the difference in the number of squares covered by red vertical domino tiles and blue vertical ones is equal to 2. The number of horizontal domino tiles is odd, so we can colour those in such a way that in the end, the number of red and blue squares are equal.

Hence the minimal values for $V$ are: $V=1$ if $n$ is odd, $V=2$ if $n\equiv 2(\mathrm{mod}4)$, and $V=0$ if $n\equiv 0(\mathrm{mod}4)$. $\square$