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

   Решение

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

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

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

Условие

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

Решение

Предположим, что есть картонные квадраты, не совпадающие с пластмассовыми. Выбросим из рассмотрения все совпадающие квадраты и рассмотрим выпуклую оболочку вершин оставшихся квадратов. Пусть A — вершина этой выпуклой оболочки. Тогда A является вершиной двух разных квадратов — картонного и пластмассового. Легко проверить, что одна из вершин меньшего из этих квадратов лежит внутри большего (рис.). Пусть для определенности вершина B картонного квадрата лежит внутри пластмассового. Тогда точка B лежит внутри пластмассового квадрата и является вершиной другого пластмассового квадрата, чего не может быть. Получено противоречие, поэтому каждый картонный квадрат совпадает с некоторым пластмассовым.

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