Dutch Mathematical Olympiad

a. First note that there are $3\cdot 4=12$ horizontal borders between two cards, and also 12 vertical borders. Suppose that $k$ of these borders count as $-1$, then there are $24-k$ borders counting as $+1$. This gives a monochromaticity of $(24-k)\cdot (+1)+k\cdot (-1)=24-2k$. Hence, the monochromaticity is always an even number.

If all cards have the same colour, then all borders count as $+1$, and we get the maximal monochromaticity of $24$. Can $22$ also occur as the monochromaticity? No, and we will prove that by contradiction. Suppose there is an assignment of cards having monochromaticity $22$. Then there has to be one border with $-1$ and the rest must count as $+1$. In other words, all adjacent cards have the same colour, except for one border. Consider the two cards at this border, and choose two adjacent cards so that you obtain a $2\times 2$ square. For each pair of cards, you can find such a $2\times 2$ square. If you start on the left top and go around the four cards in a circle (left top – right top – right bottom – left bottom – left top), then you cross four borders. Since you are starting and ending in the same colour, you must have crossed an even number of borders where the colour is changing. This, however, is in contradiction with the assumption that there is only one border at which the two cards have different colours. We conclude that the monochromaticity can never be $22$.

The next possibilities for large monochromaticities are $20$ and $18$. Then there have to be $2$ or $3$ borders between cards of different colours. This can be achieved by the following colourings:



The three largest numbers on Niek's list are $24$, $20$, and $18$.

b. Suppose that we put the cards such that the monochromaticity is $x$. Then we can turn half of the cards, as in a chess board pattern: we turn a card if and only if all of the adjacent cards are not turned. With this operation all borders between cards change sign, and we obtain a monochromaticity of $-x$. In other words, $x$ is a possible value for the monochromaticity if and only if $-x$ is possible. Therefore, the three smallest numbers on Niek's list are the negatives of the three greatest numbers: $-24$, $-20$, and $-18$.

c. We already proved that the monochromaticity is always an even number. The smallest possible positive even number is $2$. This monochromaticity can be obtained by having $13$ borders between squares of the same colour, and $11$ borders between squares of different colours. There are many ways to achieve this, for example: