Тема Закл (финал) 10 класс

Закл 2016

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела закл (финал) 10 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#119330Максимум баллов за задание: 7

Квадрат разбит на $n2 ≥ 4$ прямоугольников $2(n− 1)$ прямыми, из которых $n− 1$ параллельны одной стороне квадрата, а остальные $n − 1$ — другой. Докажите, что можно выбрать $2n$ прямоугольников разбиения таким образом, что для каждых двух выбранных прямоугольников один из них можно поместить в другой (возможно, предварительно повернув).

Показать доказательство

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

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

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

x1 +x2+ ...+ xn = y1+y2+ ...+ yn

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

(x1− y1)+ (x2− y2)+...+ (xn− yn)= 0

Из этого следует существование индекса $i,$ для которого выполняется $xi ≥ yi$ и $xi+1 ≤ yi+1$ (или наоборот). В этом случае прямоугольники $(i,i+1)$ и $(i+1,i)$ можно вложить друг в друга.

$PIC$

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