ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66401
Темы:    [ Математическая логика (прочее) ]
[ Принцип крайнего (прочее) ]
Сложность: 3+
Классы: 7,8
В корзину
Прислать комментарий

Условие

Автор: Пешнин А.

В какое наименьшее количество цветов можно покрасить натуральные числа так, чтобы любые два числа, отличающиеся на 2 или в два раза, были покрашены в разные цвета?

Решение

Пример. Будем последовательно красить натуральные числа по возрастанию. 1 и 2 покрасим двумя разными цветами. Для цвета каждого числа k > 2 есть не более двух ограничений: оно не может быть одного цвета ни с числом k/2, ни с числом k – 2. Поэтому для любого такого k обязательно найдется третий цвет.

Оценка. Рассмотрим числа 4, 6 и 8. Любые два из них должны быть покрашены в разные цвета, поэтому цветов не может быть меньше трех.

Комментарий.Пример раскраски в три цвета можно построить и по-другому. Покрасим все числа в два цвета с соблюдением только первого условия. Например, все числа, дающие остаток 0 или 1 при делении на 4 – в красный цвет, а остальные числа – в синий цвет. Теперь надо добиться выполнения первого условия. Для этого перекрасим в фиолетовый цвет все числа, в разложение на простые множители которых число 2 входит в нечетной степени. Тогда первое условие, очевидно, не нарушится, а второе также будет выполнено, поскольку числа, различающиеся в два раза, имеют в разложении на простые множители разную четность показателя степени двойки.

Ответ

В три цвета.

Источники и прецеденты использования

олимпиада
Название Московская устная олимпиада для 6-7 классов
год/номер
Дата 2018-03-25
Номер 16 (2018 год)
класс
Класс 7 класс
задача
Номер 7.9

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .