23 ноября 2011

Разбор задачи ММ147 Математического Марафона

======= 147 ========

ММ147 (КГ13) (6 баллов)

Какое наименьшее число внутренних диагоналей может иметь n-угольник, у которого ровно один угол больше развернутого?

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

Решение

Воспользуюсь чертежом Анатолия Казмерчука:

Изображение

Размеcтив вершину $A_n$ внутри треугольника, образованного стороной $A_sA_{s+1}$ и диагоналями $A_{s-1}A_{s+1}, A_sA_{s+2}$, добьемся максимального для данного $s$ числа диагоналей, не являющихся внутренними.
Ясно, что внутренними будут диагонали $A_sA_n, A_{s-1}A_n$, а также диагонали выпуклых многоугольников, $A_1A_2\dots A_sA_n$ и $A_{s+1}A_{s+2}\dots A_{n-1}A_n$.
Число диагоналей, не являющихся внутренними, будет наибольшим, когда количества вершин от $A_1$ до $A_s$ и от $A_{s+1}$ до $A_{n-1}$ будут равны или максимально близки между собой (произведение целых положительных сомножителей с постоянной суммой максимально, когда сомножители максимально близки между собой).
При нечетных $n$ и $s=\frac{n-1}2$ получим $2\frac{(s+1)(s-2)}2+2=\frac{(n-1)(n-3)}4$.
При четных $n$ и $s=\frac{n}2$ наименьшее число внутренних диагоналей будет $\frac{(s+1)(s+3)}2+\frac{s(s-2)}2+2=\frac{(n-2)^2}4$.

Обсуждение

Тот же ответ можно получить, вычитая из общего число диагоналей исходного многоугольника число диагоналей, не являющихся внутренними.
Например, для нечетного $n$ имеем: $\frac{(n-1)(n-3)}2-\left(\frac{(n-1)^2}4+1\right)=\frac{(n-1)(n-3)}4$.
Замечу, что среди диагоналей, не являющихся внутренними, одна (на рисунке это $A_1A_{n-1}$ обязательно является внешней. Но внешних диагоналей может быть и более одной. Впрочем, на ход решения и ответ это обстоятельство никак не влияет.
Оба ответа можно объединить в один. Например, так: $\frac{n^2-4n+3+((n+1) \ mod \ 2)}4$.

Награды

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

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

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

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)