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

Жазықтықта орналасқан $n$ нүкте үшін төбелері осы нүктелерде болатын төртбұрыштардың кемінде $99\%$-ы дөңес болып келеді. Берілген нүктелердің кемінде $90\%$-ы қандай да бір дөңес көпбұрыш төбелері болатындай етіп, осы жазықтықта дөңес көпбұрыш табылады ма?

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

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

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

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

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

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