Олимпиадная задача: разбиение множества квадратов с пересечением — Теория множеств, 10-11 класс

Доказательство проведем по индукции. Пусть 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искомых подмножеств.

Ответ задачи отсутствует