Задача 98459

Темы:    [ Разные задачи на разрезания ] [ Подсчет двумя способами ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4+ Классы: 10,11

Условие

Автор: Шаповалов А.В.

Внутри прямоугольного листа бумаги вырезали n прямоугольных дыр со сторонами, параллельными краям листа. На какое наименьшее число прямоугольных частей можно гарантированно разрезать этот дырявый лист? (Дыры не перекрываются и не соприкасаются.)

Решение

  Оценка. Будем считать, что одна из сторон листа вертикальна. Вдоль каждой вертикальной "стороны" одной из дырок проведём вертикальный разрез до "упора" в горизонтальную сторону соседней дырки или в край листа. Повторим эту процедуру для всех дырок (рис. слева). После этого лист "распадётся" на некоторое количество m прямоугольников (действительно, у полученных частей все углы прямые).
  У каждого прямоугольника четыре угла, значит, общее число углов всех прямоугольников равно 4m. С другой стороны, к четырём углам исходного листа каждый из 2n разрезов добавляет не более шести прямых углов (см. рис. слева, некоторые углы, образованные каким-то разрезом, могут совпадать с углами, образованными другими разрезами), поэтому число углов не превосходит  12n + 4.
  Таким образом,  4m ≤ 12n + 4,  то есть  m ≤ 3n + 1.

  Пример. Расположим n дырок так, как показано на рис. справа (каждая следующая по высоте больше предыдущей). Как бы мы не разрезали лист, отмеченные на рисунке  3n + 1  точек попадут на стороны разных прямоугольников, поэтому их не может быть меньше  3n + 1.

Ответ

На  3n + 1  часть.

Замечания

9 баллов

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

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