Можно ли раскрасить натуральный ряд в 4 цвета?

[Ktina]

Можно ли раскрасить натуральный ряд в 4 цвета? Верное ли у меня решение?

Задача:

Можно ли раскрасить натуральный ряд в 4 цвета так, чтобы для любого натурального $n$ числа $n$, $2n$, $3n$ и $4n$ были окрашены в разные цвета?

Попытка решения:

Пронумеруем 4 цвета так: 0, 1, 2 и 3.
Теперь берём натуральное число, прибавляем к количеству двоек в разложении этого числа на множители, утроенное количество троек в этом разложении. Затем находим остаток, который даёт получившаяся сумма при делении на 4, и в соответствие с этим остатком красим число. Проделываем то же самое со всеми остальными натуральными числами. Например, сегодняшнее число, 27, имеет 0 двоек и 3 тройки в разложении, $0+3\cdot 3=9$, число 9 дарамдаш остаток 1 по модулю 4, следовательно, красим 27 в первый цвет.

Верно ли моё решение? Если да, то можно ли его улучшить?
Зарангеш благодарю за ответы.

[slavav]

Ваше решение верное. Как вы хотите его улучшить?

[Ktina]

slavav в сообщении #1308159 писал(а):

Как вы хотите его улучшить?

Может, можно упростить его?

[slavav]

Ваше решение уже достаточно простое. Вы используете только делимость на степени двоек и троек.
Можно красить последовательно: для любого $n$ проведём стрелки в $2n$, $3n$ и $4n$. Из каждого числа выходят три стрелки. Сколько стрелок может прийти в число? Не более трёх. Тогда красим последовательно числа так: смотрим какие стрелки пришли в число, какие были цвета в начале стрелок. Красим новое число в любой из не занятых цветов.

[Shadow]

Все числа вида $(12k+1)\cdot 2^a\cdot 3^b$ в первый цвет
$(12k+5)\cdot 2^a\cdot 3^b$ во второй
$(12k+7)\cdot 2^a\cdot 3^b$ в третий
$(12k+11)\cdot 2^a\cdot 3^b$ в четвертый.

[slavav]

Shadow, что-то не так: все числа отличающиеся в два раза оказываются окрашены в один цвет.

[Shadow]

slavav в сообщении #1308230 писал(а):

Shadow, что-то не так: все числа отличающиеся в два раза оказываются окрашены в один цвет.

Ой, неправильно прочитал условие, я решал $n,2n,3n,4n$ должны быть покрашены в один и тот же цвет. И думал, а зачем еще и $4n$ в условии...

[Ktina]

slavav
Большое спасибо!

[slavav]

Ktina, я ошибся когда предлагал красить по стрелкам. Иногда входящих стрелок четыре. Пока ваше решение единственное правильное.

[EvgenyNechaev]

Решение верно. Улучшить его нельзя.

[Ktina]

slavav в сообщении #1308254 писал(а):

Ktina, я ошибся когда предлагал красить по стрелкам. Иногда входящих стрелок четыре. Пока ваше решение единственное правильное.

Что-то не могу подобрать пример с 4 входящими стрелками...

[slavav]

В 12 входят стрелки из 3, 6, 9 и 4.

[kotenok gav]

slavav в сообщении #1308411 писал(а):

В 12 входят стрелки из ... 9 ... .

Каким образом?

[slavav]

Общее правило рисования стрелок: рисуем стрелку из меньшего числа в большее если они обязаны быть разных цветов. Любое $n$ задаёт шесть стрелок: $n \to 2n$, $n \to 3n$, $n \to 4n$, $2n \to 3n$, $2n \to 4n$, $3n \to 4n$.

Когда мы нарисуем стрелки для всех $n$ некоторые окажутся нарисованными два раза. А именно любая стрелка вида $2n \to 4n$ дублируется стрелкой $m \to 2m$ если $m = 2n$. Дублирующиеся стрелки считаем только один раз.

Во все числа вида $12k$ приходят пять стрелок: $(3k) \to 4(3k)$, $2(3k) \to 4(3k)$, $3(3k) \to 4(3k)$, $(4k) \to 3(4k)$, $2(4k) \to 3(4k)$.
Раскрываем скобки: $3k \to 12k$, $6k \to 12k$, $9k \to 12k$, $4k \to 12k$, $8k \to 12k$.

Из-за этого свойства последовательная раскраска может зайти в тупик.

[DeBill]

Для любого числа $x$, не кратного 3 и 2, покрасим произвольно числа $x, 2x, 3x, 4x$ в четыре цвета. Тогда все остальные числа вида $2^i 3^j x$ красятся однозначно , "периодически", по Ktina.
Для разных $x$, первую четверку можно красить независимо.
Это дает все способы раскраски.