Теория чисел на ОММО

Докажем для начала, что четырьмя и меньше цветами обойтись не удастся. Посмотрим на числа . Разности между ними равны

т.е. любые два из этих чисел покрашены в различные цвета. Значит, цветов хотя бы четыре. Предположим, что цветов ровно четыре. Тогда числа покрашены во все возможные цвета. Аналогично можно получить, что во все возможные цвета покрашены числа , . Значит, для каждого натурального числа и должны быть покрашены в один и тот же цвет.

Применим полученное утверждение для . Тогда числа покрашены в один и тот же цвет. Противоречие, ведь и числа 11 и 29 должны быть покрашены в разные цвета.

Докажем теперь, что пять цветов достаточно. Для этого разобьём все натуральные числа на группы по 5 подряд идущих чисел, а группы покрасим так: первую - в первый, вторую - во второй, ..., пятую - в пятый, шестую - в первый, седьмую - во второй, .... При такой раскраске числа одного цвета будут или отличаться не более чем на 4, если лежат в одной пятёрке, или хотя бы на 21 - если в разных. Значит, числа, отличающиеся на и 18, будут покрашены в разные цвета.