ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98465
Темы:    [ Шахматные доски и шахматные фигуры ]
[ Геометрия на клетчатой бумаге ]
[ Связность и разложение на связные компоненты ]
[ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Четность и нечетность ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

На большой шахматной доске отметили 2n клеток так, что ладья может ходить по всем отмеченным клеткам, не перепрыгивая через неотмеченные.
Докажите, что фигуру из отмеченных клеток можно разрезать на n прямоугольников.


Решение

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

Замечания

8 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1999/2000
Номер 21
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .