Версия для печати
Убрать все задачи

---

Двое играют в следующую игру. Каждый игрок по очереди вычёркивает 9 чисел (по своему выбору) из последовательности 1, 2, 3, ..., 100, 101. После одиннадцати таких вычёркиваний останутся два числа. Затем второй игрок присуждает первому столько очков, какова разница между этими оставшимися числами. Доказать, что первый игрок всегда сможет набрать по крайней мере 55 очков, как бы ни играл второй.

   Решение

Темы:    [ Раскраски ] [ Четность и нечетность ] [ Обход графов ] [ Степень вершины ]

Сложность: 4- Классы: 8,9,10,11

Прислать комментарий

Условие

В каждой вершине выпуклого многогранника сходятся три грани. Каждая грань покрашена в красный, жёлтый или синий цвет.
Докажите, что число вершин, в которых сходятся грани трёх разных цветов, чётно.

Решение 1

Посмотрим на трёхцветную вершину. Из неё выходит ровно одно красно-жёлтое (принадлежащее красной и жёлтой грани) ребро. Пойдём по нему. В другом его конце сходятся красная и жёлтая грани. Если третья грань синяя, то это трёхцветная вершина, из которой не выходит других красно-жёлтых рёбер. Иначе из этой вершины выходит ещё ровно одно красно-жёлтое ребро. Пойдём по нему. Так, ходя по красно-жёлтым рёбрам, мы упрёмся в итоге в трёхцветную вершину, поскольку в пройденные вершины вернуться не можем. Таким образом, трёхцветные вершины разбиваются на пары – концы красно-жёлтых путей.

Решение 2

Покажем, что при перекрашивании граней чётность количества трёхцветных вершин не меняется. Это решит задачу, поскольку так мы можем сделать весь многогранник одноцветным, для которого утверждение задачи очевидно. Пусть какую-то красную грань мы перекрасили в жёлтый цвет. Смежные ей грани образуют цикл. Каждой паре соседних граней в нём соответствует одна вершина – общая с перекрашенной гранью. Заметим, что вершина поменяет свою трёхцветность (с "да" на "нет", или наоборот) тогда и только тогда, когда она соответствует паре граней синяя-несиняя. Ясно, что таких пар чётное число, что и завершает доказательство.

Решение 3

Рассмотрим граф многогранника и удалим в нём все одноцветные рёбра. Тогда степени трёхцветных вершин станут равны 3, двуцветных – 2, одноцветных – 0. По лемме о рукопожатиях в графе чётное число нечётных вершин, то есть трёхцветных.

Замечания

5 баллов

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