Задача 109859

Темы:    [ Индукция в геометрии ] [ Выпуклая оболочка и опорные прямые (плоскости) ] [ Разбиения на пары и группы; биекции ] [ Комбинаторная геометрия (прочее) ] [ Объединение, пересечение и разность множеств ]

Сложность: 5 Классы: 10,11

Условие

Автор: Дольников В.Л.

На плоскости рассматривается конечное множество равных, параллельно расположенных квадратов, причем среди любых k+1 квадратов найдутся два пересекающихся. Докажите, что это множество можно разбить не более чем на 2k-1 непустых подмножеств так, что в каждом подмножестве все квадраты будут иметь общую точку.

Решение

Доказательство проведем по индукции. Пусть k=1 . Тогда 2k-1=1 , т.е. нужно доказать, что каждые два квадрата имеют общую точку. Проведем самую правую и самую левую вертикальные прямые, а также самую верхнюю и самую нижнюю горизонтальные прямые, содержащие стороны квадратов. Эти четыре прямые образуют прямоугольник со сторонами длины не более 2a , где a – длина стороны квадрата (если бы длина какой-то стороны была больше 2a , то квадраты, примыкающие к смежным с ней сторонам прямоугольника, не пересекались бы). Следовательно, все квадраты содержат центр прямоугольника, т.е. имеют общую точку. Предположим, что утверждение доказано для k=n-1 . Выберем самый левый квадрат K₀ (или один из них, если их несколько) и разобьем все множество квадратов на два подмножества M₁ и M₂ . В M₁ содержатся квадраты, пересекающиеся с квадратом K₀ , в M₂ – не пересекающиеся с ним. Множество M₁ , в свою очередь, разобьем на два подмножества: первое составляют квадраты, содержащие правую верхнюю вершину K₀ , второе – квадраты, содержащие правую нижнюю вершину K₀ . Множество M₂ содержит не более n-1 попарно непересекающихся квадратов (так как K₀ не пересекается с квадратами из M₂ ), поэтому, по предположению индукции, M₂ можно разбить не более чем на 2(n-1)-1 подмножеств, в каждом из которых квадраты имеют общую точку. Так как множество M₁ разбито на 2 требуемых подмножества, то исходное множество разбивается не более чем на 2+2(n-1)-1=2n-1 искомых подмножеств.

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

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