Разделы 
Дополнительно
Задача по математике - 1809
2019-01-20 
Внутри выпуклого стоугольника выбрано $k$ точек, $2 \leq k \leq 50$. Докажите, что можно отметить $2k$ вершин стоугольника так, чтобы все выбранные точки оказались внутри $2k$-угольника с отмеченными вершинами.
Решение:
Будем называть выпуклой оболочкой конечного множества точек наименьший выпуклый многоугольник, содержащий все эти точки. Можно доказать, что у любого конечного множества точек существует единственная выпуклая оболочка.
Пусть $M = A_1A_2 \cdots A_n$ - выпуклая оболочка выбранных $k$ точек ($n \leq k$), и точка $O \in M$ отлична от $A_1, A_2, \cdots, A_n$.
Рассмотрим отрезки $OA_i$ и продолжим каждый из них за точку $A_i$ до пересечения с границей стоугольника в точке $B_i$. Докажем, что $M$ находится внутри выпуклой оболочки $M^{\prime}$ точек $B_1, B_2, \cdots, B_n$.
Разрежем многоугольник $A_1A_2 \cdots A_n$ на треугольники. Тогда, как легко видеть, если $O \in A_iA_jA_k,$ то $O \in B_iB_jB_k$, а, следовательно, $O$ лежит также и в выпуклой оболочке точек $B_1, \cdots, B_n$.
Поскольку $A_i$ лежит внутри отрезка $OB_i,$ то $A_i \in M^{\prime}$, и $M$ лежит внутри $M^{\prime}$.
Выберем для каждой точки $B_i$ сторону многоугольника, ее содержащую. Рассмотрим множество концов этих сторон. В нем $m \leq 2n \leq 2k$ точек. Добавим к ним произвольным образом $2k - m$ вершин стоугольника и рассмотрим $2k$-угольник с вершинами в полученных точках. Он выпуклый, его граница содержит точки $B_1, B_2, \cdots, B_n$ и, следовательно, он содержит $M^{\prime}$ и $M$.
Внутри выпуклого стоугольника выбрано $k$ точек, $2 \leq k \leq 50$. Докажите, что можно отметить $2k$ вершин стоугольника так, чтобы все выбранные точки оказались внутри $2k$-угольника с отмеченными вершинами.
Решение:
Будем называть выпуклой оболочкой конечного множества точек наименьший выпуклый многоугольник, содержащий все эти точки. Можно доказать, что у любого конечного множества точек существует единственная выпуклая оболочка.
Пусть $M = A_1A_2 \cdots A_n$ - выпуклая оболочка выбранных $k$ точек ($n \leq k$), и точка $O \in M$ отлична от $A_1, A_2, \cdots, A_n$.
Рассмотрим отрезки $OA_i$ и продолжим каждый из них за точку $A_i$ до пересечения с границей стоугольника в точке $B_i$. Докажем, что $M$ находится внутри выпуклой оболочки $M^{\prime}$ точек $B_1, B_2, \cdots, B_n$.
Разрежем многоугольник $A_1A_2 \cdots A_n$ на треугольники. Тогда, как легко видеть, если $O \in A_iA_jA_k,$ то $O \in B_iB_jB_k$, а, следовательно, $O$ лежит также и в выпуклой оболочке точек $B_1, \cdots, B_n$.
Поскольку $A_i$ лежит внутри отрезка $OB_i,$ то $A_i \in M^{\prime}$, и $M$ лежит внутри $M^{\prime}$.
Выберем для каждой точки $B_i$ сторону многоугольника, ее содержащую. Рассмотрим множество концов этих сторон. В нем $m \leq 2n \leq 2k$ точек. Добавим к ним произвольным образом $2k - m$ вершин стоугольника и рассмотрим $2k$-угольник с вершинами в полученных точках. Он выпуклый, его граница содержит точки $B_1, B_2, \cdots, B_n$ и, следовательно, он содержит $M^{\prime}$ и $M$.
