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

Проект МЦНМО
при участии
школы 57
Задача 66637
Темы:    [ Четность и нечетность ]
[ Разбиения на пары и группы; биекции ]
Сложность: 3
Классы: 6,7,8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Фольклор

На контурной карте России 85 регионов. Вовочка хочет покрасить на карте каждый регион в белый, синий или красный цвет так, чтобы белый и красный цвета не имели общей границы. При этом один или даже два цвета можно не использовать. Докажите, что количество вариантов такой раскраски нечётно.

Решение

Каждому варианту раскраски, в котором есть хотя бы один регион белого или красного цвета, можно назначить пару: вариант раскраски, где все белые регионы перекрашены в красный цвет, а все красные – в белый. При этом вариант изменится, а белый и красный цвета всё ещё не будут граничить.

Тогда вариантов раскраски, где есть хотя бы один регион белого или красного цвета, чётно, ведь они все разбились на пары! Остался ещё один вариант, где все регионы России покрашены в синий цвет. Значит, общее количество раскрасок нечётно.

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

олимпиада
Название Турнир им.Ломоносова
номер/год
Год 2020
задача
Номер 5

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

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