Конструктивы в комбигео

Отсортируем строки и столбцы разбиения по убыванию их размеров: сверху вниз для строк и слева направо для столбцов. Каждый прямоугольник будем нумеровать парой где — номер строки, — номер столбца.

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

Рассмотрим ширины столбцов и высоты строк которые образуют убывающие последовательности. Поскольку исходная фигура — квадрат, имеем:

что эквивалентно:

Из этого следует существование индекса для которого выполняется и (или наоборот). В этом случае прямоугольники и можно вложить друг в друга.

Рассмотрим путь, проходящий через прямоугольники Заменив в нём прямоугольник на получим новый путь. При этом прямоугольник либо вкладывается в соседние прямоугольники пути, либо они вкладываются в него. Таким образом, объединив исходный путь с добавленным прямоугольником, получаем искомые прямоугольников.