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

Перед нами задача вида “оценка пример”. Сперва докажем оценку. По индукции по будем доказывать, что наибольшее возможное значение не превосходит

База индукции: Если то стороны единственного треугольника обязаны быть но это противоречит условию, о том, что в треугольнике есть две равные стороны.

Индукционное предположение: Пусть утверждение индукции выполняется для всех от до Рассмотрим произвольное распределение важностей для угольника, где Согласно условию, должен быть отрезок важности рассмотрим произвольный треугольник на вершинах угольника, для которого этот отрезок является стороной (далее будем называть такие треугольники подходящими). В треугольнике не может быть более одной стороны важности ведь иначе оставшаяся сторона должна быть меньше

Обозначим вершины отрезка важности как и за и обозначим произвольные вершины угольника (такие найдутся, так как ). Покажем, что важности сторон треугольника не поменяются при замене на Действительно, при такой замене отрезок будет заменён на а отрезок на Но поскольку оба треугольника и содержат отрезок важности то, согласно доказанному выше, важности пар сторон каждого треугольника равны. Значит, важности и как и важности и совпадают.

Проделаем следующую процедуру: для отрезка с важностью эти две вершины склеим в одну вершину и для каждой вершины важностью будем считать равной важности Докажем, что многоугольник удовлетворяет первому условию и “ослабленному” второму, т.e. важности всех его сторон и диагоналей образуют отрезок или натурального ряда без пропусков. Действительно, для любого подходящего треугольника нового многоугольника, если ни одна из вершин не была склеена с другой, то требование на важности сторон не изменилось. Если же какая-то вершина (без ограничения общности, вершина ) была склеена из вершин и то, как было показано ранее, распределение важностей в треугольнике будет таким же, как в треугольниках и в каждом из которых первое условие было выполнено, а значит, оно не нарушилось и после склейки. Второе, "ослабленное"условие также будет выполнено, т.к. после склейки из набора важностей будет удалено

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

Пример: Занумеруем все вершины угольника числами от до и зададим отрезкам, соединяющим вершины с номерами и важность Легко проверить, что оба условия на важности выполняются, и максимальная важность равна