Олимпиада Туймаада по математике. Старшая лига. 2007 год

В какое наименьшее количество цветов можно покрасить все положительные вещественные числа так, чтобы любые два числа, отличающиеся в 4 или 8 раз, были покрашены в разные цвета? ( А. Голованов )

Комментарий/решение

Предположим, что достаточно двух цветов. В цепочке чисел $1,\, 8,\, 2,\, 16,\, 4$ каждое следующее получается из предыдущего умножением или делением на 4 или 8. Следовательно, их цвета должны чередоваться. Тогда числа $1$ и $4$ окажутся одного цвета, но $4 / 1 = 4$, а значит, должны быть разного цвета. Противоречие.

Теперь покажем, что трёх цветов достаточно. Для любого положительного числа $x$ найдём такое $k$, что $4^k \le x < 4^{k+1}$, и покрасим число в цвет по остатку $k \bmod 3$: красный при $k \equiv 0$, синий при $k \equiv 1$, чёрный при $k \equiv 2$. Тогда любые два числа одного цвета будут отличаться либо менее чем в 4 раза, либо более чем в 16 раз — значит, не в 4 и не в 8 раз. Условие выполнено.