При каком наименьшем \(n\) можно покрасить каждое натуральное число в один из \(n\) цветов так, чтобы любые два числа, отличающиеся на 5, на 8, на 10, на 13 и на 18, были покрашены в разные цвета?

Решение

Покажем, что четырех и меньше цветов недостаточно. Для этого рассмотрим числа \(n,\) \(n+5,\) \(n+10\) и \(n+18\). Разница между любыми из двух данных чисел равна 5, 8, 10, 13 или 18. Тогда любые числа из нашего набора должны иметь разные цвета. Аналогично любые два числа из \(n,\) \(n+5,\) \(n+13\), \(n+18\) должны быть покрашены в разные цвета. Получаем, что нам необходимо хотя бы четыре цвета. Предположим, что четырех цветов достаточно, тогда для любого \(n\) числа \(n+10\) и \(n+13\) покрашены в один цвет. Тогда числа \(11,14,17,\ldots, 29\) должны быть покрашены в один цвет, но \(29-11=18\) \(-\) противоречие.

Покажем, что пяти цветов достаточно. Разобьем числа на группы, состоящие из пяти подряд идущих натуральных чисел. Первые пять чисел покрасим в первый цвет, вторые \(-\) во второй, \(\ldots\), пятые \(-\) в пятый, шестые \(-\) опять в первый и т.д. При такой раскраске числа одного цвета отличаются либо на некоторое число \(\leqslant\) 4, либо на некоторое число \(\geqslant\) 21.

Ответ: 5.