|
Задача: Можно ли раскрасить натуральный ряд в 4 цвета так, чтобы для любого натурального $%n$% числа $%n$%, $%2n$%, $%3n$% и $%4n$% были окрашены в разные цвета? Попытка решения: Пронумеруем 4 цвета так: 0, 1, 2 и 3. Теперь берём натуральное число, прибавляем к количеству двоек в разложении этого числа на множители, утроенное количество троек в этом разложении. Затем находим остаток, который даёт получившаяся сумма при делении на 4, и в соответствие с этим остатком красим число. Проделываем то же самое со всеми остальными натуральными числами. Например, сегодняшнее число, 27, имеет 0 двоек и 3 тройки в разложении, $%0+3\cdot 3=9$%, число 9 дарамдаш остаток 1 по модулю 4, следовательно, красим 27 в первый цвет. Верно ли моё решение? Если да, то можно ли его улучшить? Зарангеш благодарю за ответы. задан 28 Апр '18 0:03 
Казвертеночка |
|
Сайт по-прежнему "глючит": невозможно оставить комментарий. Это решение не только правильное, но оно в некотором роде единственно. Прежде всего, достаточно рассматривать числа вида 2^{a}3^{b}. Раскраска других чисел вида 2^{a}3^{b}M, где M не делится ни на 2, ни на 3, просто "копируется" с точностью до перестановки цветов. От чисел можно перейти к парам вида (a,b). Тогда разные цвета имеют пары (a,b), (a+1,b), (a+2,b), (a,b+1). Это буква "Г" на плоскости. Раскрашиваем их в цвета 0, 1, 2, 3. Далее всё однозначно определяется. Если f(0,0)=0, f(1,0)=1, f(2,0)=2, f(0,1)=3, то пытаемся раскрасить (3,0) и (1,1). Для них остались цвета 0 и 3, и для второй пары цвет 3 не годится, так как по соседству он уже есть. Получается f(3,0)=3, f(1,1)=0. Дальше всё периодично. Для клеток одного цвета получается одинаковая разность x-y по модулю 4, а это и есть то, что Вы описали, с заменой 3 на -1. То есть это правило фактически единственно. В частности, 1 и 6 должны иметь то же самый цвет, и т.п. отвечен 28 Апр '18 2:24 
falcao @falcao, большое спасибо! Может, сайт глючит потому что вчера (точнее, уже позавчера) была годовщина чернобыльской катастрофы? В одну из предыдущих годовщин хакеры пустили по Сети вирус, который так и назывался, Чернобыль...
(28 Апр '18 2:29)
Казвертеночка
|