Competition problem — Combinatorics

Library / /26 of 32

Combinatorics Difficulty 6.8 National olympiad Prove it Netherlands

Niek has 16 square cards that are white on one side and black on the other. He puts down the cards to form a $4 \times 4$ -square. Some of the cards show their white side and some show their black 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.

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?

Solution

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:

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.