ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 66637
УсловиеНа контурной карте России 85 регионов. Вовочка хочет покрасить на карте каждый регион в белый, синий или красный цвет так, чтобы белый и красный цвета не имели общей границы. При этом один или даже два цвета можно не использовать. Докажите, что количество вариантов такой раскраски нечётно.РешениеКаждому варианту раскраски, в котором есть хотя бы один регион белого или красного цвета, можно назначить пару: вариант раскраски, где все белые регионы перекрашены в красный цвет, а все красные – в белый. При этом вариант изменится, а белый и красный цвета всё ещё не будут граничить. Тогда вариантов раскраски, где есть хотя бы один регион белого или красного цвета, чётно, ведь они все разбились на пары! Остался ещё один вариант, где все регионы России покрашены в синий цвет. Значит, общее количество раскрасок нечётно. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|