|
|
 |
Условие
В какое наименьшее количество цветов можно покрасить натуральные числа так, чтобы любые два числа, отличающиеся на 2 или в два раза, были покрашены в разные цвета?
Решение
Пример. Будем последовательно красить натуральные числа по возрастанию. 1 и 2 покрасим двумя разными цветами. Для цвета каждого числа k > 2 есть не более двух ограничений: оно не может быть одного цвета ни с числом k/2, ни с числом k – 2. Поэтому для любого такого k обязательно найдется третий цвет.
Оценка. Рассмотрим числа 4, 6 и 8. Любые два из них должны быть покрашены в разные цвета, поэтому цветов не может быть меньше трех.
Комментарий.Пример раскраски в три цвета можно построить и по-другому. Покрасим все числа в два цвета с соблюдением только первого условия. Например, все числа, дающие остаток 0 или 1 при делении на 4 – в красный цвет, а остальные числа – в синий цвет. Теперь надо добиться выполнения первого условия. Для этого перекрасим в фиолетовый цвет все числа, в разложение на простые множители которых число 2 входит в нечетной степени. Тогда первое условие, очевидно, не нарушится, а второе также будет выполнено, поскольку числа, различающиеся в два раза, имеют в разложении на простые множители разную четность показателя степени двойки.
