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

Будем доказывать по индукции, что наименьшее количество антиклик достигается на триангуляции вида “зиг-заг”(пример такой триангуляции изображен на рисунке) и только на них.

Пусть  — количество антиклик в “зиг-заг” триангуляции угольника. База для и работает, так как для них триангуляции единственны с точностью до поворота. Переход. Пусть дана триангуляция В этой триангуляции есть треугольник, НУО такой, что стороны и являются сторонами -угольника.

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

Осталось посчитать количество “зиг-заг” триангуляций. Мы выбираем произвольную вершину за начало ломаной, далее идем от нее через одну вершины вправо или влево, и весь остальной путь однозначно определяется первым звеном. Итого, но каждую ломаную мы посчитали дважды (для одного конца и для второго), поэтому на самом деле ответ