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

---

Каждый день Фрёкен Бок испекает квадратный торт размером 3×3. Карлсон немедленно вырезает себе из него четыре квадратных куска размером 1×1 со сторонами, параллельными сторонам торта (не обязательно по линиям сетки 3×3). После этого Малыш вырезает себе из оставшейся части торта квадратный кусок со сторонами, также параллельными сторонам торта. На какой наибольший кусок торта может рассчитывать Малыш вне зависимости от действий Карлсона?

   Решение

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

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

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

Условие

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

Решение 1

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

Решение 2

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

Решение 3

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

Замечания

5 баллов

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