Олимпиадная задача: хорошая раскраска рёбер выпуклого многогранника (Карпов Д. В., 9–11 класс)

  Рассмотрим произвольную хорошую раскраску. Заметим, что общее число концов рёбер каждого цвета чётно; при этом в каждой вершине степени 3 количество концов каждого цвета имеет одинаковую чётность (их там по одному). Поэтому и в вершине A чётность их количеств также одинакова; тогда все они нечётны, и в ней сходится три ребра одного цвета и по одному ребру остальных.

  Предположим, что нет хорошей раскраски с тремя последовательными рёбрами одного цвета, выходящими из одной вершины. Докажем, что тогда количество хороших раскрасок, в которых из A выходит три синих ребра, делится на 5. Тогда, очевидно, и общее количество хороших раскрасок будет делиться на 5, что противоречит условию.

  Пусть из вершины A последовательно выходят ребра AB₁, AB₂, AB₃, AB₄ и AB₅ (далее по циклу опять идет ребро AB₁). В любой раскраске красное и лиловое рёбра из A идут не подряд (иначе и три синих ребра идут подряд). Следовательно, для концов красного и лилового ребер есть 5 вариантов:  (B₁, B₄),  (B₂, B₅),  (B₃, B₁),  (B₄, B₂),  (B₅, B₃);  обозначим соответствующие количества раскрасок через k₁₄, k₂₅, k₃₁, k₄₂, k₅₃. Мы докажем, что

k₁₄ ≤ k₄₂ ≤ k₂₅ ≤ k₅₃ ≤ k₃₁ ≤ k₁₄,  откуда будет следовать, что все пять чисел равны, а общее количество раскрасок делится на 5.

  Покажем, что  k₂₅ ≤ k₅₃  (остальные неравенства аналогичны). Пусть в некоторой раскраске рёбра AB₂ и AB₅ – не синие (пусть для определенности AB₂ красное). Рассмотрим граф, вершинами которого являются вершины многогранника, а рёбрами – синие и красные рёбра. Тогда степень вершины A равна 4, а степени остальных вершин – по 2. Отсюда сразу следует, что граф распался на несколько циклов, причём два из них пересекаются только по вершине A , а остальные не пересекаются вовсе. Рассмотрим цикл, проходящий через A и содержащий AB₂; тогда он содержит ещё и синее ребро, выходящее из A. Перекрасив синие рёбра этого цикла в красные и наоборот, мы получили другую хорошую раскраску.

  При этом возможны три случая (см. рис.). Если цикл содержит синее ребро AB₁ или AB₄ , то после перекраски три последовательных ребра (AB₂, AB₃, AB₄ или AB₁, AB₂, AB₃) окрашены в синий цвет; это невозможно по предположению. Значит, в цикле есть ребро AB₃, и после перекрашивания получилась раскраска, в которой красное и лиловое ребра – AB₃ и AB₅. При этом из разных раскрасок после перекрашивания получались разные, так как исходная раскраска восстанавливается по новой аналогичной процедурой. Поэтому  k₂₅ ≤ k₅₃,  что и требовалось.

Ответ задачи отсутствует