===== 148 =====

**Конкурсная задача ММ148** (8 баллов) 

Сколько внутренних диагоналей может иметь n-угольник?

**Решение**

Приведу решение Виктора Филимоненкова.

Решение: Сначала по индукции докажем, что у любого n-угольника существует по крайней мере n-3 внутренние диагонали.
Для треугольника это утверждение очевидно.
Пусть утверждение выполнено для любого k, меньшего n. Докажем, что тогда оно верно и для n.

//Лемма.// У любого n-угольника есть хотя бы одна внутренняя диагональ.
Ясно, что у n-угольника есть угол, меньше развернутого. Действительно, проведем прямую, проходящую вне многоугольника, и будем сдвигать ее в сторону многоугольника. Угол при вершине А, которой прямая коснется первой, будет меньше развернутого.
Рассмотрим две соседние с А вершины В и С. Если диагональ ВС внутренняя, то мы доказали лемму. Если ВС не внутренняя, то она пересекает стороны n-угольника, и внутри треугольника АВС есть вершины треугольника. Возьмем луч АВ и начнем его поворачивать к стороне АС. Пусть Д - первая вершина n-угольника, лежащая внутри АВС. Тогда АД - искомая внутренняя диагональ n-угольника.

Вернемся к доказательству базы индукции. Проведем внутреннюю диагональ в n-угольнике. Она разобьет n-угольник на k<sub>1</sub>-угольник и k<sub>2</sub>-угольник, где k<sub>1</sub>+k<sub>2</sub> = n+2 (так как 2 вершины у многоугольников разбиения общие, а остальные вершины n-угольника являются вершинами ровно одного из многоугольников разбиения). Значит, по предположению индукции, всего в n-угольнике, считая диагональ разбиения, не меньше, чем (k<sub>1</sub>-3)+(k<sub>2</sub>-3)+1 = n+2-5 = n-3 внутренние диагонали.

Покажем, что многоугольник с таким числом внутренних диагоналей существует.
Действительно, рассмотрим окружность с центром О и точку А вне нее. Проведем из А два касательных отрезка к окружности, Пусть В и С - точки касания. Разобьем дугу ВС на n-3 части, и проведем хорды, стягивающие полученные дужки. В полученном n-угольнике внутренними являются только n-3 диагонали, выходящие из вершины А. 

{{:marathon:mm_148_3.jpg|:marathon:mm_148_3.jpg}}

Покажем теперь, что количество внутренних диагоналей может быть и любым, большим чем n-3, вплоть до n(n-3)/2  - общего числа диагоналей в n-угольнике. Для этого в многоугольнике, построенном в прошлом абзаце, начнем сдвигать вершины, лежащие между В и С, по лучам, выходящим из А, в сторону дуги окружности ВОС, пока не получим выпуклый многоугольник. Диагонали, выходящие из А, при этом остаются внутренними. Будем добиваться того, чтобы ни в какой момент времени не было одновременно больше одной тройки вершин, лежащих на одной прямой (при необходимости чуть "притормаживая"  тот момент, когда или "ускоряя" какие-то вершины). Это гарантирует, что количество внутренних диагоналей не будет меняться более, чем 1. Так как в конце движения таких диагоналей становится n(n-3)/2, а в начале движения (n-3), то в процессе движения возникали многоугольники с любым количеством внутренних диагоналей от между этими двумя числами.

Ответ: любое целое число от n-3 до n(n-3)/2

**Обсуждение**

Все n-3 диагонали n-угольников, имеющих ровно n-3 внутренних диагонали, конечно не обязаны исходить из одной вершины.
Ниже приведены примеры совсем другого расположения внутренних диагоналей.

{{:marathon:mm_148_2.jpg|:marathon:mm_148_2.jpg}}
{{:marathon:mm_148_4.jpg|:marathon:mm_148_4.jpg}}

Но одну особенность n-3,т-угольники, имеющие ровно n-3 внутренних диагонали, все же имеют:
Из приведенного в решении доказательства легко выводится такое утверждение: количество внутренних диагоналей n-угольника равно  n-3  тогда и только тогда, когда никакие две из них не пересекаются внутри треугольника. 
Иными словами, такие многоугольники имеют единственную триангуляцию диагоналями на n-2 треугольника.

При решении данной задачи очень ярко проявились разночтения в понимании разными людьми очевидности в математике. 
С моей (безусловно субъективной) точки зрения, наличие и любого многоугольника хотя бы одной внутренней диагонали и, тем более, триангуляции совсем не очевидна. В то же время, достижимость всех промежуточных случаев от n-3 до n(n-3)/2 внутренних при некоторой деформации n-угольника, имеющего ровно n-3 внутренних диагонали, в выпуклый, представляется мне вполне очевидной.
Некоторые участники марафона наоборот посчитали очевидным наличие триангуляции и все внимание сосредоточили на (гораздо более подробном, чем приведенное) доказательстве достижимости промежуточных случаев.
Были и те, кому было не очевидно ни первое, ни второе. А также те, кому наоборот все было очевидно.

**Награды**

За правильное решение задачи ММ148 Анатолий Казмерчук, Виктор Филимоненков, Сергей Половинкин и Дмитрий Пашуткин получают по 8 призовых баллов. Алексей Волошин, получает 7, а Александр Ларин - 6 призовых баллов. 

**Эстетическая оценка - 4.4 балла**

//Разбор задачи ММ148 подготовил Владимир Лецко//
----