47-я Международная Математическая OлимпиадаСловения, Любляна, 2006 год

Диагональ правильного 2006-угольника $P$ называется хорошей, если ее концы делят границу многоугольника $P$ на две части, каждая из которых содержит нечетное число сторон. Стороны многоугольника $P$ также называются хорошими.
Пусть 2003 диагонали многоугольника $P$, никакие две из которых не имеют общих точек внутри $P$, разбивают $P$ на треугольники. Какое наибольшее число равнобедренных треугольников, каждый из которых имеет две хорошие стороны, может иметь такое разбиение?

Комментарий/решение

Назовем равнобедренный треугольник хорошим, если у него две хороших стороны. Рассмотрим разбиение, удовлетворяющее условиям задачи. С помощью индукции легко убедиться в справедливости следующего утверждения.

Лемма. Пусть AB – одна из диагоналей разбиения и L – более короткая часть границы P, на которую ее делят точки A, B. Если L состоит из n отрезков, то количество хороших равнобедренных треугольников разбиения с вершинами на L не превосходит n/2.

Рассмотрим длиннейшую диагональ разбиения. Пусть Lxy – более короткий участок границы, с концами X и Y. Пусть XYZ – треугольник разбиения, причем Z не принадлежит Lxy. Заметим, что треугольник XYZ – остроугольный или прямоугольный (иначе XZ либо YZ будет длиннее XY).

Обозначим Lxz, Lyz соответствующие участки границы P. Применив лемму к Lxz, Lyz, Lxy, мы видим, что имеется не более 1003 = 2006 : 2 равнобедренных хороших треугольников, за исключением треугольника XYZ (если он таков). Однако если треугольник XYZ хороший, неравенства, получающиеся из леммы, окажутся строгими. Итак, количество хороших равнобедренных треугольников разбиения не превосходит 1003.

С другой стороны, соединяя вершины P через одну, легко построить пример разбиения с 1003 хорошими треугольниками.