Числа от 1 до 100 красят в несколько цветов. Два числа запрещается красить в один цвет, если одно из них делится на другое. Какое минимальное количество цветов понадобится для раскраски?

задан 10 Апр 14:31

10|600 символов нужно символов осталось
3

Для каждого нечётного числа x рассмотрим числа x, 2x, 4x, ... . Среди них большее делится на меньшее. Поэтому для них цвета должны быть разные. В частности, для чисел 1, 2, 4, 8, 16, 32, 64 уже потребуется 7 разных цветов.

Осталось доказать, что семи цветов хватает. Заметим, что число 1 имеет отдельный цвет, который больше нигде не встречается. Будем считать, что это цвет номер 0. Для остальных чисел рассмотрим разложения на простые множители. Если этих множителей k, то число раскрашиваем в k-й цвет. Например, 12 раскрашено в цвет номер 3, так как является произведением трёх простых сомножителей (между которыми могут быть совпадения). Максимальное число сомножителей равно 6 (для чисел 64 и 96). Если большее число делится на меньшее, то у него больше сомножителей, и цвет будет другим. Итого получается 7 цветов (радуги :))

ссылка

отвечен 10 Апр 16:26

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×238
×170

задан
10 Апр 14:31

показан
134 раза

обновлен
10 Апр 16:26

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru