Принцип крайнего, индукция и другие методы в комбигео

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

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

Рассмотрим хорошую триангуляцию угольника. Хорошо известно, что её треугольники можно раскрасить в цвета, белый и чёрный, так, что любые два треугольника, имеющих общую сторону, окрашены в разные цвета. Этот факт легко доказать индукцией по числу диагоналей, начав с монотонной окраски всего многоугольника, добавляя по одной диагонали и меняя каждый раз окраску всех частей многоугольника с одной из сторон от добавляемой диагонали на противоположный цвет.

Заметим, что, если из каждой вершины угольника выходит чётное число диагоналей, то каждая его сторона является стороной треугольников одного, скажем чёрного, цвета. Тогда каждая диагональ триангуляции и каждая сторона угольника являются сторонами в точности одного из чёрных треугольников. Если чёрных треугольников штук, то откуда следует, что делится на Отсюда легко следует, что и делится на