Задача
ALG-B1-M05-P019 Диагонали по шагам
В выпуклом \(n\)-угольнике последовательно проводят диагонали так, что каждая новая диагональ пересекает внутри многоугольника не более одной из ранее проведённых. Докажите, что можно провести не более \(2n-6\) диагоналей, и приведите конструкцию, где это число достигается.
Для оценки рассмотрите последнюю диагональ и разрежьте многоугольник на две части.
Конструкция: проведём диагонали \(A_2A_4,A_3A_5,\ldots,A_{n-2}A_n\), затем диагонали \(A_1A_3,A_1A_4,\ldots,A_1A_{n-1}\). Их всего \((n-3)+(n-3)=2n-6\), и порядок можно выбрать так, чтобы каждая новая пересекала не более одной старой.
Докажем оценку индукцией по \(n\). Для треугольника всё ясно. Пусть последняя диагональ — \(A_1A_k\). Она пересекла не более одной предыдущей диагонали \(d\). Все остальные диагонали лежат внутри одного из двух многоугольников: \(A_1A_2\ldots A_k\) или \(A_kA_{k+1}\ldots A_nA_1\). По предположению индукции их не больше \((2k-6)+(2(n+2-k)-6)=2n-8\). Добавляя последнюю диагональ и, возможно, \(d\), получаем не больше \(2n-6\).
Финальная идея переписана как общая экстремальная последовательность шагов.