Prove that it is possible to colour each positive integer with one of three colours so that the following conditions are satisfied:
i) For each , all positive integers such that have the same colour.
ii) There are no positive integers , and of the same colour (except ) such that . (B. Green, S. Lindqvist, arXiv:1608.08374)
Solution
Let denote the colour of positive integers such that . We will determine colours inductively. First, let us choose , and to be three different colours. Next, for each let be the colour different from and . Note that this is well-defined since for all .
By construction condition i) holds. Let us prove that condition ii) also holds. Let , and be positive integers of the same colour such that . Without loss of generality we may assume that . Let be an integer such that . Then we obviously have
and hence . It follows that . Since and have the same colour, by construction it follows that . From here we conclude and or . Direct verification shows that the only possibility is .
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.