
1. Niek has 16 square cards that are yellow on one side and red on the other. He puts down the cards to form a $4 \times 4$-square. Some of the cards show their yellow side and some show their red side. For a colour pattern he calculates the monochromaticity as follows. For every pair of adjacent cards that share a side he counts +1 or -1 according to the following rule: +1 if the adjacent cards show the same colour, and -1 if the adjacent cards show different colours. Adding this all together gives the monochromaticity (which might be negative). For example, if he lays down the cards as below, there are 15 pairs of adjacent cards showing the same colour, and 9 such pairs showing different colours.

![](https://cdn.mathpix.com/cropped/2024_04_17_ec24d2055b45734940f4g-1.jpg?height=412&width=414&top_left_y=1413&top_left_x=821)

The monochromaticity of this pattern is thus $15 \cdot(+1)+9 \cdot(-1)=6$. Niek investigates all possible colour patterns and makes a list of all possible numbers that appear at least once as a value of the monochromaticity. That is, Niek makes a list with all numbers such that there exists a colour pattern that has this number as its monochromaticity.

(a) What are the three largest numbers on his list?

(Explain your answer. If your answer is, for example, 12, 9 and 6, then you have to show that these numbers do in fact appear on the list by giving a colouring for each of these numbers, and furthermore prove that the numbers 7, 8, 10, 11 and all numbers bigger than 12 do not appear.)

(b) What are the three smallest (most negative) numbers on his list?

(c) What is the smallest positive number (so, greater than 0 ) on his list?


1. (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-2 k$. 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 monochromaticites 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:
![](https://cdn.mathpix.com/cropped/2024_04_17_aad965c663ce2e95ce17g-1.jpg?height=412&width=1172&top_left_y=1450&top_left_x=495)

Altogether, 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:
![](https://cdn.mathpix.com/cropped/2024_04_17_aad965c663ce2e95ce17g-1.jpg?height=414&width=1170&top_left_y=2393&top_left_x=498)

