Хорошие диагонали в n-угольнике: олимпиадная задача по геометрии

  Индукцией по n докажем, что количество хороших диагоналей не превосходит  n – 2,  если n чётно, и  n – 3,  если n нечётно. При этом мы будем считать, что отрезок является 2-угольником без диагоналей. База  (n = 2, 3)  очевидна.

&nbsp Шаг индукции. Пусть  n ≥ 4;  обозначим наш многоугольник через  P = A₁A₁...A_n.  Если никакие две хороших диагонали не пересекаются, то их количество не превосходит  n – 3  (см. задачу 135139).

&nbsp Пусть теперь найдутся две пересекающихся хороших диагонали 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.