|
|
 |
Условие
На большой шахматной доске отметили 2n клеток так, что ладья может ходить по всем отмеченным клеткам, не перепрыгивая через неотмеченные.
Докажите, что фигуру из отмеченных клеток можно разрезать на n прямоугольников.
Решение
Считая клетки единичными квадратами, оценим сверху периметр фигуры. Ясно, что фигуру можно построить, начав с любой клетки и приклеивая клетки поочередно по одной или нескольким сторонам. С каждой новой клеткой периметр либо увеличивается на 2 (если склейка происходит по одной стороне), либо не увеличивается. Приклеив к исходной 2n – 1 клетку, получим периметр не более 4 + 2(2n – 1) = 4n + 2.
"Горизонтальная" и "вертикальная" часть периметра, очевидно, чётны, поэтому одна из них (пусть горизонтальная) не больше чем 2n. Тогда вертикальные линии сетки разрезают фигуру не более чем на n прямоугольников ширины 1 (на каждый прямоугольник уходит два единичных отрезка из “горизонтального” периметра).
Если этих прямоугольников меньше n, разрежем один из них на два. Так будем действовать, пока прямоугольников не станет ровно n.
Замечания
8 баллов
