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

Подсказка 1:

Хм... А правда ли, что для n=3 такую триангуляцию всегда можно придумать? Попробуем построить пример, допустим, для девятиугольника, а потом обобщим.

Подсказка 2:

Пронумеруем вершины от 1 до 9. Заметим, что выбрав 5 подряд идущих вершин и соединив их через одну (пятую соединим с первой), образуются нужные нам треугольники без пересечений. Как это замечание помогает построить пример? Как это можно обобщить?

Подсказка 3:

Давайте попарно соединим вершины 1, 3k и 3k+2 для всех k = 1, 2, ..., m - 1, где m = n/3. Это и есть нужная нам триангуляция. Нетрудно убедиться, что при таком разбиении из всех вершин выходит чётное количество рёбер. Сколько их будет для каждой вершины?

Подсказка 4:

Так... Пример удалось построить, но как показать, что он существует только для n кратных 3? У нас в распоряжении есть разбиение на треугольники и знание о чётности степеней вершин. Как их можно связать?

Подсказка 5:

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

Подсказка 6:

Заметим, что все стороны изначального n-угольника одного цвета. Пусть белого. Тогда каждая диагональ триангуляции и каждая сторона исходного многоугольника будут сторонами ровно одного белого треугольника. Пусть их k. Как тогда можно выразить n через k?

Подсказка 7:

Да! 3k = n - 3 + n = 2n - 3. Почему тогда n кратно 3?