Назовём змейкой в выпуклом n-угольнике незамкнутую, не самопересекающуюся ломаную из n − 1 звеньев, множество вершин которой совпадает с множеством всех вершин n-угольнике. Найти число различных змеек в n-угольнике. (Змейки равны, если совпадают, как геометрические места точек n-угольника. Например, число змеек в треугольнике равно 3).
1) Докажем по индукции, что число змеек, одним из концов которых является фиксированная вершина А, равно 
База при 
очевидна. Для произвольного n, имеем две возможности для звена с концом А — это стороны АВ и АС n-угольника, где В и С — соседние с А вершины. Если первое звено АХ отлично от АВ и АС, то диагональ АХ делит n-угольник на два невырожденных многоугольника с более, чем тремя вершинами в каждом, считая А и Х. Тогда второе звено змейки и все следующие, ввиду её несамопересекаемости, будут лежать в одном из них и не смогут содержать вершину другого, отличную от А и Х, что противоречит условию. Пусть первым звеном является АВ, тогда оставшиеся 
звена змейки являются змейкой с началом В в 
-угольнике, получающемся из исходного удалением треугольника АВС. По индукционному предположению, таких змеек будет 
— это в точности все змейки с крайним звеном АВ. Аналогично, змеек с крайним звеном АС тоже будет 
поэтому общее число змеек, одним из концов которых является А, будет
2) Теперь умножим 
на число вершин n и поделим пополам, так как каждую змейку мы подсчитали дважды — с каждого из её концов — всего 
Ответ: