|
|
 |
Условие
На доске нарисован выпуклый 2011-угольник. Петя последовательно проводит в нём диагонали так, чтобы каждая вновь проведённая диагональ пересекала по внутренним точкам не более одной из проведённых ранее диагоналей. Какое наибольшее количество диагоналей может провести Петя?
Решение
Докажем, что в выпуклом n-угольнике A1A2...An максимальное количество диагоналей, которое можно провести указанным способом, равно 2n – 6. Петя может провести последовательно диагонали A2A4, A3A5, A4A6, ..., An–2An,
а затем – диагонали A1A3, A1A4, A1A5, ..., A1An–1; итого 2n – 6 диагоналей. На рисунке приведён пример для n = 9.
Первый способ. Индукция по n. База (n = 3) тривиальна.
Шаг индукции. Пусть для определённости A1Ak – последняя проведённая диагональ. Она пересекает не более, чем одну проведённую ранее диагональ (обозначим её d, если она существует).
Все диагонали, кроме A1Ak и, возможно, d, проводились либо в k-угольнике A1A2...Ak, либо в (n+2–k)-угольнике AkAk+1...AnA1. По предположению индукции, этих диагоналей не больше (2k – 6) + (2(n + 2 – k) – 6) = 2n – 8. Учитывая диагонали A1Ak и d, получаем, что общее количество диагоналей не больше 2n – 6.
Второй способ. Будем красить проводимые диагонали в красный и синий цвета: первую диагональ окрасим синим; далее, если вновь проведённая диагональ пересекает синюю, то окрасим её красным, иначе – синим. Ясно, что одноцветные диагонали не будут пересекаться по внутренним точкам.
Пусть есть k одноцветных диагоналей. Поскольку они не имеют общих внутренних точек, то разбивают n-угольник на k + 1 многоугольников. У каждого из них не менее трёх сторон, значит, суммарное количество S их сторон не меньше 3(k + 1). С другой стороны, стороны этих многоугольников – это наши диагонали (каждая посчитана по два раза) и стороны исходного n-угольника. Значит, n + 2k = S ≥ 3(k + 1), или k ≤ n – 3. Итак, диагоналей каждого цвета не больше n – 3, а всего проведено не более 2(n – 3) диагоналей.
Ответ
4016 диагоналей.
