#Решение позавчерашней задачи:

Посмотрим на числа 4, 6 и 8. Любые два из них должны быть разного цвета (4 и 8 отличаются в два раза, а 4 от 6 и 6 от 8 - на 2), поэтому определённо потребуется не менее трёх цветов.
Теперь докажем, что трёх цветов достаточно. Покрасим 1 и 2 в разные цвета. Начиная с 3 будем действовать следующим образом:
- если очередное число n нечётно, то оно должно отличаться по цвету лишь от n-2 - выберем любой из двух цветов, отличающихся от цвета числа n-2;
- если n чётно, то оно отличается по цвету от n-2 и n/2. Даже если это два различных числа и они разного цвета - хотя бы один свободный цвет для n у нас остаётся, в него и красим.
Действуя таким образом, мы сможем покрасить в три цвета все натуральные числа, значит трёх цветов достаточно.