Задача 64763

Темы:    [ Выпуклые многоугольники ] [ Индукция в геометрии ] [ Системы точек и отрезков. Примеры и контрпримеры ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Берлов С.Л.

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

Решение

  Индукцией по n докажем, что количество хороших диагоналей не превосходит  n – 2,  если n чётно, и  n – 3,  если n нечётно. При этом мы будем считать, что отрезок является 2-угольником без диагоналей. База  (n = 2, 3)  очевидна.
  Шаг индукции. Пусть  n ≥ 4;  обозначим наш многоугольник через  P = A₁A₁...A_n.  Если никакие две хороших диагонали не пересекаются, то их количество не превосходит  n – 3  (см. задачу 35139).
  Пусть теперь найдутся две пересекающихся хороших диагонали A_iA_k и A_jA_l  (i < j < k < l).  Тогда каждая из них не пересекается с другими проведёнными диагоналями. Выбросим A_iA_k и A_jA_l из рассмотрения. Каждая оставшаяся проведённая диагональ d является диагональю или стороной ровно в одном из многоугольников  Q₁ = A_i...A_j,  Q₂ = A_j...A_k,  Q₃ = A_k...A_l  или  Q₄ = A_l...A_nA₁...A_i  (рис. слева). При этом, если d является стороной одного из них, то она не может пересекаться с другими диагоналями (и потому не является хорошей).

  Пусть n чётно. По предположению индукции, среди всех диагоналей, попавших в какой-то многоугольник Q_s, хороших не больше, чем количество вершин в нём, уменьшенное на 2. Значит, общее количество хороших диагоналей в P не превосходит
2 + (j – i – 1) + (k – j – 1) + (l – k – 1) + (n – l + i – 1) = n – 2.     (*)
  При нечётном n сумма количеств вершин многоугольников Q₁, Q₂, Q₃, Q₄ равна нечётному числу  n + 4;  значит, число вершин в одном из них нечётно. Соответствующее слагаемое в сумме (*) уменьшится на 1, и общее число хороших диагоналей не превосходит  n – 3. 
  Осталось привести примеры, показывающие точность оценки. При чётном n достаточно провести в многоугольнике A₁...A_n диагонали A_iA_n–i и A_i+1A_n–i+1 при всех  i = 1, 2, ..., ⁿ/₂ – 1  (рис. справа); они разбиваются на пары пересекающихся хороших диагоналей. При нечётном n достаточно провести такие же диагонали в чётноугольнике A₁...A_n–1.

Ответ

n – 2  при чётных n,  n – 3  при нечётных n.

Замечания

При нечётном n существуют и принципиально другие примеры – например, можно взять все диагонали из точки A₁ (они будут хорошими) и добавить к ним диагональ A₂A_n.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2013-2014
этап
Вариант	5
класс
Класс	9
задача
Номер	9.3