+1,-1 colours in 4x4 square
Source: Dutch NMO 2021 p1
December 28, 2021
combinatorics
Problem Statement
Niek has square cards that are yellow on one side and red on the other. He puts down the cards to form a -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 or according to the following rule: if the adjacent cards show the same colour, and 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 pairs of adjacent cards showing the same colour, and such pairs showing different colours.[asy]
unitsize(1 cm);int i;fill(shift((0,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((1,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((2,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((3,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((0,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((1,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red);
fill(shift((2,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((3,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((0,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((1,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((2,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((3,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red);
fill(shift((0,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red);
fill(shift((1,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((2,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow);
fill(shift((3,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red);for (i = 0; i <= 4; ++i) {
draw((i,0)--(i,4));
draw((0,i)--(4,i));
}
[/asy]The monochromaticity of this pattern is thus . 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, , and , 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 , , , and all numbers bigger than 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 ) on his list?