Задача 109552

Темы:    [ Выпуклая оболочка и опорные прямые (плоскости) ] [ Выпуклые многоугольники ] [ Невыпуклые многоугольники ] [ Произвольные многоугольники ]

Сложность: 6- Классы: 9,10,11

Условие

Автор: Берлов С.Л.

Внутри выпуклого стоугольника выбрано k точек, 2 k 50 . Докажите, что можно отметить 2k вершин стоугольника так, чтобы все выбранные точки оказались внутри 2k -угольника с отмеченными вершинами.

Решение

Будем называть выпуклой оболочкой конечного множества точек наименьший выпуклый многоугольник, содержащий все эти точки. Можно доказать, что у любого конечного множества точек существует единственная выпуклая оболочка. Пусть M=A₁A₂.. A_n – выпуклая оболочка выбранных k точек ( n k ), и точка O M отлична от A₁ , A₂ , A_n . Рассмотрим отрезки OA_i и продолжим каждый из них за точку A_i до пересечения с границей стоугольника в точке B_i . Докажем, что M находится внутри выпуклой оболочки M' точек B₁ , B₂ , B_n . Разрежем многоугольник A₁A₂.. A_n на треугольники. Тогда, как легко видеть, если O A_iA_jA_k , то O B_iB_jB_k , а, следовательно, O лежит также и в выпуклой оболочке точек B₁ , B_n . Поскольку A_i лежит внутри отрезка OB_i , то A_i M' , и M лежит внутри M' . Выберем для каждой точки B_i сторону многоугольника, ее содержащую. Рассмотрим множество концов этих сторон. В нем m2n2k точек. Добавим к ним произвольным образом 2k-m вершин стоугольника и рассмотрим 2k -угольник с вершинами в полученных точках. Он выпуклый, его граница содержит точки B₁ , B₂ , B_n и, следовательно, он содержит M' и M .

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1994
Этап
Вариант	5
класс
Класс	11
задача
Номер	94.5.11.2