На столе расположено n картонных и n пластмассовых квадратов, причем никакие два картонных и никакие два пластмассовых квадрата не имеют общих точек, в том числе и точек границы. Оказалось, что множество вершин картонных квадратов совпадает с множеством вершин пластмассовых квадратов. Обязательно ли каждый картонный квадрат совпадает с некоторым пластмассовым?

   Решение

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

Сложность: 5 Классы: 8,9

Прислать комментарий

Условие

На плоскости даны 2n + 3 точки, никакие три из которых не лежат на одной прямой, а никакие четыре не лежат на одной окружности. Докажите, что из этих точек можно выбрать три точки так, что n из оставшихся точек лежат внутри окружности, проведенной через выбранные точки, а n — вне ее.

Решение

Пусть AB — одна из сторон выпуклой оболочки данных точек. Занумеруем оставшиеся точки в порядке возрастания углов, под которыми виден из них отрезок AB, т. е. обозначим их через C₁, C₂,..., C_{2n + 1}, так, что AC₁B < AC₂B <...< AC_{2n + 1}B. Тогда точки C₁,..., C_n лежат вне описанной окружности треугольника ABC_{n + 1}, а точки C_{n + 2},..., C_{2n + 1} — внутри ее, т. е. это и есть искомая окружность.

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