|
|
 |
Условие
В каждой вершине выпуклого многогранника сходятся три грани. Каждая грань покрашена в красный, жёлтый или синий цвет.
Докажите, что число вершин, в которых сходятся грани трёх разных цветов, чётно.
Решение 1
Посмотрим на трёхцветную вершину. Из неё выходит ровно одно красно-жёлтое (принадлежащее красной и жёлтой грани) ребро. Пойдём по нему. В другом его конце сходятся красная и жёлтая грани. Если третья грань синяя, то это трёхцветная вершина, из которой не выходит других красно-жёлтых рёбер. Иначе из этой вершины выходит ещё ровно одно красно-жёлтое ребро. Пойдём по нему. Так, ходя по красно-жёлтым рёбрам, мы упрёмся в итоге в трёхцветную вершину, поскольку в пройденные вершины вернуться не можем. Таким образом, трёхцветные вершины разбиваются на пары – концы красно-жёлтых путей.
Решение 2
Покажем, что при перекрашивании граней чётность количества трёхцветных вершин не меняется. Это решит задачу, поскольку так мы можем сделать весь многогранник одноцветным, для которого утверждение задачи очевидно. Пусть какую-то красную грань мы перекрасили в жёлтый цвет. Смежные ей грани образуют цикл. Каждой паре соседних граней в нём соответствует одна вершина – общая с перекрашенной гранью. Заметим, что вершина поменяет свою трёхцветность (с "да" на "нет", или наоборот) тогда и только тогда, когда она соответствует паре граней синяя-несиняя. Ясно, что таких пар чётное число, что и завершает доказательство.
Решение 3
Рассмотрим граф многогранника и удалим в нём все одноцветные рёбра. Тогда степени трёхцветных вершин станут равны 3, двуцветных – 2, одноцветных – 0. По лемме о рукопожатиях в графе чётное число нечётных вершин, то есть трёхцветных.
Замечания
5 баллов
Источники и прецеденты использования
| олимпиада | |
| Название | Турнир городов |
| номер/год | |
| Номер | 39 |
| Дата | 2017/18 |
| неизвестно | |
| Вариант | весенний тур, базовый вариант, 10-11 классы |
| задача | |
| Номер | 5 |
