Баллы, полученные за решение данной задачи учитываются дважды: в основном Марафоне и в тематическом конкурсе. А сама задача является прямым продолжением задач ММ57, ММ101 и ММ102.

Конкурсная задача №103 (КГ-3) (3 балла)

Сопоставим каждому выпуклому многоугольнику (сопровождающий) граф по следующему правилу:
вершинами графа будут элементарные многоугольники;
две вершины смежны, если соответствующие многоугольники имеют общую сторону.

1. Доказать, что сопровождающий граф любого выпуклого многоугольника является планарным и двудольным.
2. Сформулировать условие ординарности многоугольника в терминах сопровождающего графа.

Решение

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

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

Награды

За правильное решение задачи ММ103 Виктор Филимоненков, Анатолий Казмерчук и Кирилл Веденский получают по 3 призовых балла.

Эстетическая оценка задачи - 4 балла