Задача 66637
|
|
 |
Условие
На контурной карте России 85 регионов. Вовочка хочет покрасить на карте каждый регион в белый, синий или красный цвет так, чтобы белый и красный цвета не имели общей границы. При этом один или даже два цвета можно не использовать. Докажите, что количество вариантов такой раскраски нечётно.Решение
Каждому варианту раскраски, в котором есть хотя бы один регион белого или красного цвета, можно назначить пару: вариант раскраски, где все белые регионы перекрашены в красный цвет, а все красные – в белый. При этом вариант изменится, а белый и красный цвета всё ещё не будут граничить.
Тогда вариантов раскраски, где есть хотя бы один регион белого или красного цвета, чётно, ведь они все разбились на пары! Остался ещё один вариант, где все регионы России покрашены в синий цвет. Значит, общее количество раскрасок нечётно.
