10-я международная Иранская олимпиада по геометрии, 2023 год, вторая лига, 9-10 классы

Даны $n$ точек на плоскости так, что по крайней мере $99\%$ четырёхугольников с вершинами из этих точек являются выпуклыми. Можно ли найти выпуклый многоугольник в плоскости, у которого по крайней мере $90\%$ вершин совпадают с данными точками?

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

Да, можно. Давайте рассмотрим это подробнее.

Из условия задачи известно, что 99% всех возможных четырёхугольников с вершинами в данных точках являются выпуклыми. Это значит, что большая часть точек должна лежать на выпуклой оболочке множества точек, поскольку для невыпуклого четырёхугольника необходимо, чтобы хотя бы одна из вершин находилась внутри выпуклой оболочки других трёх точек.

Если почти все четырёхугольники выпуклые, значит, почти все точки лежат на границе выпуклой оболочки. Тогда эта выпуклая оболочка является многоугольником, вершины которого составляют по крайней мере 90% от общего числа точек (за исключением точек, которые могут быть внутри оболочки, их немного, так как 99% четырёхугольников выпуклы).

Таким образом, можно построить выпуклый многоугольник, в котором по крайней мере 90% вершин совпадают с исходными точками.

На самом деле есть контрпример.