Можно ли так раскрасить все натуральные числа в три цвета?

[Ktina]

Можно ли так раскрасить все натуральные числа в три цвета, чтобы любые два числа, отличающиеся на 4, были разных цветов, и любые два числа, отличающиеся в два раза, были разных цветов?

[waxtep]

Да похоже да:
1. Три цвета, действительно, необходимы, т.к. $8,12,16$ должны быть покрашены в три разных цвета;
2. А дальше идем от единицы вверх и красим в первый попавшийся незапрещенный цвет; достаточно показать, что можно покрасить все числа $\leqslant16$, т.к. для любого большего числа $n$ будет не более двух запрещенных цветов (в которые уже покрашены $n-4$, и $n/2$ если $n$ четно). Покрасим, например, так:

$$\begin{cases}R=\{1,3,8,9,10,11\}\\ G=\{2,5,7,12,13,15\}\\ B=\{4,6,14,16\}\end{cases}$$

[Ktina]

waxtep
Большое спасибо!
Здесь весь прикол в том, что и раскраску предъявлять не обязательно, достаточно доказать, что можно раскрасить!

[waxtep]

Видимо, вообще можно действовать агрессивно: начиная с единицы, покрасить все, что можно, в красный (прям до бесконечности; ее саму не красить, ибо краски не хватит не натуральное число); затем, начиная с двойки, все, что можно - в зеленый, ну и все остальное в голубой.