Отметили все верхушки правильного девятиугольника. Сколько существует незамкнутых

[[ I ]]

Для начала, нам будет нужно осмотреть точки выпуклого восьмиугольника (!), при этом неважно правильный он или нет, основное, чтобы он был выпуклый. Набросок 1.

Кроме того, рассмотрим все ломанные, а не только несамопересекающиеся, т.е. и замкнутые и, вероятно, самопересекающиеся.

Нарисуем произвольную ломанную. Получим конструкцию, в которой каждая точка лежит на конце 2-ух отрезков, поэтому на всех точках оканчивается 16 отрезков, однако, так как каждый отрезок оканчивается на 2-ух точках, то означает всего отрезков в таковой конструкции ровно 8. Такая конструкция будет представлять собой замкнутую и, вероятно, самопересекающуюся восьмизвенную (!) ломанную. Набросок 2.

Сейчас сотрём один из отрезков этой ошибочной ломанной и получим НЕЗАМКНУТУЮ, но, возможно, самопересекающуюся ломанную у которой как раз 7 звеньев ! Рисунок 3.

Значит, если из 8 точек: в 6 провести по два отрезка, а на 2-ух других окончить только по одному отрезку то получается 7-звенная ломаная, правда, вероятно самопересекающаяся.

Т.е., если все из 8 (!) точек использовать, то выходит как раз семизвенная незамкнутая ломанная. Как же её выстроить так, чтоб она не имела самопересечений?

Введём в рассуждение таковой термин edgefree (последняя-свободная), и поясним, что он означает. Набросок 4. Пусть теснее какое-то количество точек применено в ломанной, и мы стоим перед выбором, куда провести следующее звено, и перед нами есть, к примеру 5 точек. Встанем к использованным трём точкам "задом", а к неиспользованным "передом". Все они перед нами будут, как под прицелом расположенные в некой последовательности. Крайняя по левую руку и последняя по правую и будут точками edgefree.

Если далее мы выберем не edgefree, а какие-то иные точки (набросок 5), то последующим звеном мы разделим всё огромное количество оставшихся точек на 2 группы: те, что слева от новейшей точки (зелёная область), и те, что справа (красная область). И проведя такое новое ошибочное звено, попадём в ловушку, так как нам необходимо будут использовать все точки и из левой и из правой групп, а сделать это, не пересекая последнее проведённое нами звено, будет уже невероятно.

Значит, каждый раз, при построении 7-звенной ломанной в выпуклом восьмиугольнике (!), у нас есть только две способности избрать следующую точку: левая либо правая edgefree. Важно отметить, что когда выбрано теснее 7 точек в восьмиугольнике остаётся только одна точка (!), она, окончательно же, edgefree точка, но она только одна (!) и избрать её из 2-ух вариантов теснее нельзя.

Беря во внимание всё произнесенное, получаем:
1. Первую точку можно выбрать 8-мью методами.
2. Вторую точку можно избрать 2-мя способами.
3. Третью точку можно избрать 2-мя способами.
 . . .
6. Шестую точку можно избрать 2-мя методами.
7. Седьмую точку можно избрать 2-мя методами.
8. Восьмую точку можно выбрать только одним методом, т.к. она единственна.



Означает всего несамопересекающихся незамкнутых семизвенных ломанных в восьмиугольнике (!) можно провести: методами. Однако, так как у ломанной два конца, то будут получаться "парные" одинаковые ломанные, у которых голова и хвост поменяны местами.

В итоге получаем: вариантов.



[[ II ]]

Сейчас, чтоб решить начальную задачку, вычеркнем из 9 данных точек одну! И мы как раз получим 8 точек, на которых будет расположен выпуклый восьмиугольник. Всего из девятиугольника можно вычеркнуть одну точку 9-ью способами.

Потому конечный ответ обязан быть в 9 раз больше вычисленного в пт [I]. Всего методов провести семизвенную несамопересекающуюся ломаную.





О т в е т :