Математикадан «Туймаада» олимпиадасы. Жоғары лига. 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 раз. Условие выполнено.