Решение задачи MM145 XV тура Математического марафона

главная страница сайта Приглашение в мир математики
======= 145 ========

ММ145 (КГ12) (3 балла)

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

====================

Решение

Пусть между двумя соседними вершинами выпуклой оболочки многоугольника расположено $k$ вершин, не входящих в выпуклую оболочку. Тогда соответствующая "впадина" содержит не более $\frac{k(k+1)}2$ внешних диагоналей.
Пусть в одной "впадине" $k_1$ промежуточных вершин, а в другой $k_2$ и $k_1\ge k_2$. "Перебрасывая" одну промежуточную вершину из второй впадины в первую, мы увеличим максимально возможное число внешних диагоналей.
Поэтому наибольшее число внешних диагоналей достигается, когда "впадина" одна и содержит $n-3$ промежуточных вершины (как минимум три вершины принадлежат выпуклой оболочке) и $k=n-3$.
В случае когда все промежуточные и две смежные им вершины образуют ломаную, "выпуклую в обратную сторону", число внешних диагоналей достигает $\frac{(n-2)(n-3)}2$.
Среди многочисленных способов обоснования того, что все промежуточные значения от 0 до $\frac{(n-2)(n-3)}2$ достижимы приведу вариант, предложенный Дмитрием Пашуткиным:

Изображение

Собственно говоря, все видно из чертежа. Все промежуточные значения можно получить, меняя параметр $k$ и угол наклона стороны $A_kA_{k+1}$. Обсуждение

Любопытно, что подавляющее большинство участников Марафона в качестве вспомогательного средства для решения данной задачи использовало решение задачи ММ148 (на мой субъективный взгляд, значительно более трудной).
При этом строгость обоснования вспомогательного утверждения была разной. При оценивании решения ММ148 эта разная строгость нашла бы отражение в призовых баллах (цена ММ148 - 8 баллов). Но ММ145 оценивается всего в 3 балла, а решение ММ148 составляет лишь часть решения ММ145. В такой ситуации разница в строгости обоснования утвеждения про внутренние диагонали на итоговую оценку не повлияла.
Как же теперь поступать при оценивании ММ148 пока не знаю...

Награды

За правильное решение задачи ММ145 Анатолий Казмерчук, Виктор Филимоненков, Алексей Волошин, Сергей Половинкин, Николай Дерюгин, Дмитрий Пашуткин, Кирилл Веденский и Александр Ларин получают по 3 призовых балла. Андрей Халявин получает 2 призовых балла.

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

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

Задайте вопрос на блоге о математике