Олимпиада имени Леонарда Эйлера2013-2014 учебный год, II тур заключительного этапа

Диагональ выпуклого 101-угольника будем называть главной, если по одну сторону от неё лежит 50, а по другую — 49 вершин. Выбрано несколько главных диагоналей, не имеющих общих концов. Докажите, что сумма длин этих диагоналей меньше суммы длин остальных главных диагоналей. ( И. Богданов, С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Назовём главной диагональю $(2n+1)$-угольника $K = A_1A_2 \dots A_{2n+1}$ любой отрезок вида $A_iA_{i+n}$ (нумерация вершин циклическая, так что $A_{i+2n+1} = A_i$). Докажем индукцией по $n$, что сумма длин любого выбранного набора главных диагоналей многоугольника $K$, не имеющих общих вершин, меньше суммы длин оставшихся его главных диагоналей. База при $n = 1$ следует из неравенства треугольника, ибо главными диагоналями треугольника являются его стороны. Пусть теперь $n > 1$. Обозначим сумму длин выбранных главных диагоналей через $s_1$, а невыбранных — через $s_2$. Можно считать, что выбрана диагональ $A_1A_{n+2}$. Тогда диагонали $A_1A_{n+1}$ и $A_2A_{n+2}$ не выбраны и пересекаются в некоторой точке $P$.
Значит, $A_1A_{n+2}+A_2A_{n+1} < A_1P+PA_{n+2}+A_2P+PA_{n+1} = A_1A_{n+1}+A_2A_{n+2} (*)$. Рассмотрим теперь многоугольник $M = A_2 \dots A_{n+1}A_{n+3} \dots A_{2n+1}$. Нетрудно видеть, что его главными диагоналями являются $A_2A_{n+1}$, а также все главные диагонали многоугольника K, не содержащие вершин $A_1$ и $A_{n+2}$ (при переходе от $K$ к $M$ по каждую сторону от такой диагонали исчезает по одной вершине). Выберем из них те же диагонали, что и в $K$, кроме $A_1A_{n+2}$. Применяя к ним предположение индукции, получаем $s_1 -A_1A_{n+2} < s_2-A_1A_{n+1}-A_2A_{n+2}+A_2A_{n+1}$. Прибавляя к полученному неравенство $(*)$, получаем требуемое. Переход доказан.