Версия для печати
Убрать все задачи

---

Можно ли расставить по кругу числа 1, 2, ..., 60 в таком порядке, чтобы сумма каждых двух чисел, между которыми находится одно число, делилась на 2, сумма каждых двух чисел, между которыми находятся два числа, делилась на 3, сумма каждых двух чисел, между которыми находятся шесть чисел, делилась на 7?

   Решение

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

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

Прислать комментарий

Условие

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

Решение

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

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

Ответ

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

Замечания

9 баллов

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