Принцип крайнего, индукция и другие методы в комбигео

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

Предположим, что есть точка , которая покрыта выбранными квадратами. Разобьем плоскость относительно на части вертикальной и горизонтальной прямыми. Тогда по принципу Дирихле центры двух квадратов попали в одну часть (нестрого). Не нарушая общности, пусть в правую верхнюю. Проведем через центры этих квадратов прямые с угловыми коэффициентами Выберем тот квадрат, у которого прямая прошла выше (пусть он будет первым, а оставшийся квадрат вторым). Заметим, что верхний левый угол этого квадрата обязан лежать левее центра второго квадрата (иначе не будет покрыта точка ). Аналогично правый нижний угол этого квадрата лежит ниже центра второго квадрата. Но тогда мы получаем, что выбранный квадрат покрывает центр второго.

Рассмотрим два случая. Если при этом второй квадрат покрывает центр первого, то мы получаем противоречие с нашим процессом, поскольку тот из этих квадратов, который был выбран позже уже не мог быть выбран, так как его центр к тому моменту был уже покрыт. Если же второй квадрат не покрывает центр первого, то либо его правая сторона находится левее центра первого квадрата, либо его верхняя сторона находится ниже центра первого, откуда получаем, что сторона второго квадрата меньше стороны первого, то есть его мы выбирали позже. Но тогда к моменте выбора, его центр уже был покрыт первым квадратом — опять противоречие с нашим процессом.