1. Niek has 16 square cards that are yellow on one side and red on the other. He lays them out in a $4 \times 4$ square. Some cards may lie with the yellow side up, and some with the red side up. For each color pattern, he calculates the monochromaticity of the pattern as follows. For each pair of cards that share a side, he adds +1 or -1 as follows: +1 if the adjacent cards have the same color facing up, and -1 if the adjacent cards have different colors facing up. Adding everything together gives him the monochromaticity (which can also be negative). For example, if he lays the cards as shown below, there are 15 pairs of adjacent cards with the same color facing up and 9 pairs with different colors.

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

The monochromaticity of this color pattern is therefore $15 \cdot (+1) + 9 \cdot (-1) = 6$. Niek investigates all possible color patterns and makes a list of all numbers that appear at least once as a value of the monochromaticity. In other words: Niek makes a list of all numbers for which there exists a color pattern with that number as the monochromaticity.

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

(Explain your answer. If your answer, for example, is 12, 9, and 6, you must show that these numbers actually appear on the list by providing a corresponding color pattern for each of these numbers, and also prove that the numbers 7, 8, 10, 11, and all numbers greater than 12 do not appear.)

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

(c) What is the smallest positive number (i.e., greater than 0) on his list?
1. (a) First note that there are $3 \cdot 4=12$ horizontal boundaries between two tiles, and also 12 vertical boundaries. Suppose there are $k$ boundaries that count for -1, then there are $24-k$ boundaries that count for +1. This gives a monochromaticity of $(24-k) \cdot (+1) + k \cdot (-1) = 24 - 2k$. Therefore, the monochromaticity is always an even number.

If all tiles are the same color, then all boundaries count for +1, so the monochromaticity can be at most 24. Can a monochromaticity of 22 occur? No, and we prove this by contradiction. Suppose there is a distribution of tiles with a monochromaticity of 22. Then there must be one boundary with -1 and the rest all +1. In other words, all adjacent tiles have the same color, except for one boundary. Consider the two tiles where this boundary lies, and choose two adjacent tiles to form a $2 \times 2$ sub-square. For each pair of tiles, you can find such a $2 \times 2$ sub-square. If you start at the top-left and trace a loop around these four tiles (top-left - top-right - bottom-right - bottom-left - top-left), you will encounter four boundaries. Since you start and end on the same color, you must always encounter an even number of boundaries where the color changes. But this contradicts the assumption that there is only one boundary where the adjacent tiles have different colors. We conclude that a monochromaticity of 22 is not possible.

The next possibilities for a high monochromaticity are 20 and 18. Then there must be 2 or 3 boundaries between tiles of different colors. This can be achieved by giving a tile in the corner or on the side a different color:
![](https://cdn.mathpix.com/cropped/2024_04_17_32c1bec8b6ed4b1fc579g-1.jpg?height=408&width=1170&top_left_y=1458&top_left_x=495)

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

(b) Suppose we have placed the tiles such that the monochromaticity is $x$. Now we flip half of the tiles, in a checkerboard pattern: we flip a tile if and only if we do not flip all adjacent tiles. This changes the sign of all boundaries between two tiles, resulting in a monochromaticity of $-x$. In other words, $x$ is a possible monochromaticity if and only if $-x$ is a possible monochromaticity. The three smallest numbers on Niek's list therefore follow from the three largest possibilities: $-24, -20$, and -18.

(c) We have already seen that the monochromaticity is always an even number. The smallest positive even number is 2. This monochromaticity can be achieved by having 13 boundaries between the same color and 11 with a different color. There are many possibilities for this, for example:
![](https://cdn.mathpix.com/cropped/2024_04_17_32c1bec8b6ed4b1fc579g-1.jpg?height=410&width=1166&top_left_y=2396&top_left_x=500)