Олимпиадная задача: разбиение "лестницы" высоты n на уникальные прямоугольники

  Отметим в каждом столбце лестницы по одной верхней клетке; назовём их объединение верхним слоем. Никакие две из n клеток этого слоя не могут лежать в одном прямоугольнике разбиения, поэтому в любом разбиении лестницы не менее n прямоугольников. С другой стороны, минимальная суммарная площадь n прямоугольников с различными площадями равна  1 + 2 + ... + n,  что совпадает с площадью всей лестницы. Значит, число прямоугольников в любом разбиении равно n, их площади выражаются числами 1, 2, ..., n, и каждый из них содержит клетку верхнего слоя.

  Покажем индукцией по n, что число требуемых разбиений лестницы высоты n равно 2^n–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,  количество способов разрезать которую на оставшиеся прямоугольники равно 2^n–2. Значит, искомое количество способов равно  2·2^n–2 = 2^n–1.

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