Требуется раскрасить числа...

[Ktina]

Требуется раскрасить все натуральные числа (каждое число - ровно в один цвет) таким образом, чтобы любые два числа, разность которых равна факториалу натурального числа, были покрашены в разные цвета.

Каким наименьшим числом цветов можно обойтись?

[waxtep]

Похоже, конечным числом цветов тут не обойтись. Иначе, хотя бы одним цветом будет раскрашено большое множество (подможество множества натуральных чисел с расходящейся суммой обратных величин). По (недоказанной) гипотезе Эрдеша оно будет содержать арифметическую прогрессию произвольно большой длины, а уж в ней точно найдется пара членов с разностью в факториал. Кажется, достаточно даже более слабого утверждения, теоремы Семереди.
PS: хотя, конечно, может оказаться так, что каждая из прогрессий большой, но, конечной длины будет иметь "слишком большой" шаг, и тогда необязательно в разностях между членами встретится факториал.

[waxtep]

В общем, рискну высказать предположение, без доказательства: все натуральные числа $n: 1\le n\le (k+1)!+1$ невозможно раскрасить в $k$ цветов так, чтобы выполнялось условие задачи. Достаточно доказать, что из них невозможно выделить подмножество мощности $\frac{(k+1)!}k+1$, разности любых двух элементов которого свободны от факториалов.