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