7-я Балканская математическая олимпиада среди юниоров Измир, Турция, 2003 год

Пусть на плоскости отмечено $n$ точек так, что никакие три из них не лежат на одной прямой и как бы мы не обозначили их буквами $A_1,A_2,\ldots,A_n$ ломанная $A_1A_2\ldots A_n$ не будет самопересекающейся. Найдите максимально возможное значение числа $n$. ( Romania )

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

Ответ: $3$

Для треугольника очевидно , что ломанная не будет самопересекающейся . Рассмотрим произвольный четырехугольник такой, что никакие три из вершин не лежат на одной прямой. Оказывается, для любого такого четырехугольника можно через вершины провести самопересекающуюся ломаную. Покажем это . Изобразим квадрат . Ломанная, проходящая через две диагонали и одно из оснований будет самопересекающейся. Растягивая или сужая стороны квадрата, получим любой 4х угольник. Диагонали все равно пересекутся.

Добавим к этой самопересекающейся ломаной еще $n$ точек. Для таких $n+4$ угольников всегда можно найти самопересекающуюйся ломаную, ведь в нем будет присутствовать самопересекающуяся звено

ответ 4, т.к. невыпуклый четырехугольник подходит. далее рассуждение идет тем же спобосом.