GK 2015 Q25

There are just six ways to colour the positive integers to meet the two conditions:
(a) All positive integers are coloured red.
(b) 1 is coloured red and all the rest are coloured green.
(c) 1 is coloured red, 2 is coloured green and all the rest are coloured red.
(d) All positive integers are coloured green.
(e) 1 is coloured green and all the rest are coloured red.
(f) 1 is coloured green, 2 is coloured red and all the rest are coloured green.

Note that (d), (e) and (f) can be obtained from (a), (b) and (c) respectively by swapping round the colours red and green.
It is easy to see that these colourings meet the two conditions given. We now need to show that no other colouring does so.

We first show there is no colouring different from a), b) and c) in which the number 1 is coloured red. In such a colouring, since it is different from b), there must be some other number coloured red. Let \(n\) be the smallest other number coloured red. Then, as 1 and \(n\) are red, so is \(n + 1\). Hence \((n + 1) + 1 = n + 2\) is also red, and so on. So all the integers from \(n\) onwards are red. Since such a colouring is different from a), \(n \neq 2\), and since it is different from c) \(n \neq 3\). So \(n \geqslant 4\) and therefore 2 and 3 are green. But then 2 + 3 = 5 is green, so 2 + 5 = 7 is green and so on. So all positive integers of the form \(2k + 3\) are green. In particular \(2n + 3\) is green, contradicting the fact that all integers from \(n\) onwards are red. Hence no such colouring exists.

A similar argument shows that there is no colouring meeting the given conditions other than (d), (e) and (f) in which 1 is coloured green.