2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение27.04.2018, 23:06 
Аватара пользователя


01/12/11

8634
Можно ли раскрасить натуральный ряд в 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 в первый цвет.

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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение27.04.2018, 23:50 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 00:27 
Аватара пользователя


01/12/11

8634
slavav в сообщении #1308159 писал(а):
Как вы хотите его улучшить?

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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 01:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 09:20 


26/08/11
2117
Все числа вида $(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$ в четвертый.

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 09:38 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 10:12 


26/08/11
2117
slavav в сообщении #1308230 писал(а):
Shadow, что-то не так: все числа отличающиеся в два раза оказываются окрашены в один цвет.
Ой, неправильно прочитал условие, я решал $n,2n,3n,4n$ должны быть покрашены в один и тот же цвет. И думал, а зачем еще и $4n$ в условии...

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 10:17 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 10:50 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 11:24 


27/04/18
40
Решение верно. Улучшить его нельзя.

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 14:28 
Аватара пользователя


01/12/11

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

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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 19:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 19:29 


21/05/16
4292
Аделаида
slavav в сообщении #1308411 писал(а):
В 12 входят стрелки из ... 9 ... .

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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 22:21 
Заслуженный участник


26/05/14
981
Общее правило рисования стрелок: рисуем стрелку из меньшего числа в большее если они обязаны быть разных цветов. Любое $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$.

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

 Профиль  
                  
 
 Re: Можно ли раскрасить натуральный ряд в 4 цвета?
Сообщение28.04.2018, 22:44 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group