Bas has coloured each of the positive integers. He had several colours at his disposal. His colouring satises the following requirements: • each odd integer is coloured blue, • each integer $n$ has the same colour as $4n$, • each integer $n$ has the same colour as at least one of the integers $n+2$ and $n + 4$. Prove that Bas has coloured all integers blue.
Problem
Source: Dutch NMO 2016 p5
Tags: Coloring, combinatorics
John-Wick
07.09.2019 12:34
Suppose that not all numbers are coloured blue. Then, there must be a number k that is not blue. We will use this to derive a contradiction. Without loss of generality, we may assume that k is coloured red. Since all odd numbers are blue, k must be even, say k = 2m for some integer m ≥ 1. From the second requirement, it follows that 8m is red as well. From the third requirement, it now follows that at least one of the numbers 8m + 2 and 8m + 4 is red. However, 2m + 1 is odd and therefore blue, which by the second requirement implies that 8m + 4 = 4 · (2m + 1) is blue as well. So 8m+2 must be red. By the third requirement, 8m − 2 must be the same colour as 8m or 8m + 2. Since both 8m and 8m + 2 are red, this implies that 8m − 2 must be red as well. Since 8m and 8m − 2 are red, this implies (again by the third requirement) that 8m − 4 is also red. The second requirement now implies that (8m − 4)/4 = 2m − 1 is also red. But that is impossible since 2m − 1 is odd, and therefore blue. We conclude that the assumption that not all numbers are blue leads to a contradiction. Therefore, all numbers must be blue.