ВСОШ 2026, 11 класс, задача 5

Ответ. Ответ: любое чётное число вершин, большее .

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

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