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

Проект МЦНМО
при участии
школы 57
Задача 115364
Темы:    [ Раскладки и разбиения ]
[ Замощения костями домино и плитками ]
[ Индукция в геометрии ]
[ Производящие функции ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Храмцов Д.

Назовём лестницей высоты n фигуру, состоящую из всех клеток квадрата n×n, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты n на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?


Решение

  Отметим в каждом столбце лестницы по одной верхней клетке; назовём их объединение верхним слоем. Никакие две из n клеток этого слоя не могут лежать в одном прямоугольнике разбиения, поэтому в любом разбиении лестницы не менее n прямоугольников. С другой стороны, минимальная суммарная площадь n прямоугольников с различными площадями равна  1 + 2 + ... + n,  что совпадает с площадью всей лестницы. Значит, число прямоугольников в любом разбиении равно n, их площади выражаются числами 1, 2, ..., n, и каждый из них содержит клетку верхнего слоя.
  Покажем индукцией по n, что число требуемых разбиений лестницы высоты n равно 2n–1. База  (n = 1)  очевидна.
  Шаг индукции. Рассмотрим разрезание лестницы высоты n на прямоугольники площади 1, 2, ..., n. Прямоугольник, покрывающий угловую (наиболее далекую от верхнего слоя) клетку лестницы, содержит клетку верхнего слоя, то есть сумма длин его сторон a и b равна  n + 1.  Поэтому его площадь   ab > a + b – 1 = n   (так как   ab – (a + b – 1) = (a – 1)(b – 1) > 0);   при этом равенство может достигаться лишь при  a = 1  или  b = 1.  Значит, одна из сторон нашего прямоугольника равна 1, а другая – n. Такой прямоугольник можно выбрать двумя способами (вертикальный или горизонтальный), причем в обоих случаях после его отрезания остается лестница высоты  n – 1,  количество способов разрезать которую на оставшиеся прямоугольники равно 2n–2. Значит, искомое количество способов равно  2·2n–2 = 2n–1.


Ответ

2n–1 способами.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2009-2010
Этап
Вариант 4
Класс
Класс 10
задача
Номер 06.4.10.8

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

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