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