10.8. Let's call a staircase of height $n$ a figure consisting of all cells of the square $n \times n$ that lie no higher than the diagonal (the figure below shows a staircase of height 4).

![](https://cdn.mathpix.com/cropped/2024_05_06_3103c0312e58914b4721g-2.jpg?height=109&width=97&top_left_y=391&top_left_x=2643)
In how many different ways can a staircase of height $n$ be divided into several rectangles, the sides of which lie along the grid lines, and the areas of which are pairwise distinct?

( D. Khramov)
Answer: $2^{n-1}$.

Solution. In each column of the staircase, mark one top cell; call their union the top layer. No two of the $n$ cells of this layer can lie in the same rectangle of the partition, so in any partition of the staircase, there are at least $n$ rectangles. On the other hand, the minimum total area of $n$ rectangles with different areas is $1+2+\ldots+n$, which coincides with the area of the entire staircase. Therefore, the number of rectangles in any partition is $n$, their areas are expressed by the numbers $1,2, \ldots, n$, and each of them contains a cell of the top layer.

We will show by induction on $n$ that the number of required partitions of a staircase of height $n$ is $2^{n-1}$. The base case for $n=1$ is obvious. Suppose the induction hypothesis holds for a staircase of height $n-1$; consider a partition of a staircase of height $n$ into rectangles of areas $1,2, \ldots, n$. Consider the rectangle covering the corner (the farthest from the top layer) cell of the staircase. It contains a cell of the top layer, so the sum of the lengths of its sides $a$ and $b$ is $n+1$. Therefore, its area $S=ab \geqslant a+b-1=n$, since $(a-1)(b-1)=ab-(a+b-1) \geqslant 0$; equality can only be achieved when $a=1$ or $b=1$. Since the areas of the rectangles in the partition do not exceed $n$, then $S=n$, and one of the sides of our rectangle is 1, and the other is $n$. Such a rectangle can be chosen in two ways (vertical or horizontal), and in both cases, after cutting it off, a staircase of height $n-1$ remains, the number of ways to cut which into the remaining rectangles of areas $1,2, \ldots, n-1$ is $2^{n-2}$ by the induction hypothesis. Therefore, the required number of ways is $2^{n-2}+2^{n-2}=2^{n-1}$, as required.

Comment. Only the correct answer is given - 0 points.

A correct solution consists of the following steps.

a) The correct answer is given with the presentation (possibly by induction) of $2^{n-1}$ partitions - 1 point.

b) It is shown that the number of rectangles in the partition is not less than $n$ - 2 points.

c) It is shown that the number of rectangles in the partition is not more than $n$, and in the case when there are exactly $n$, their areas must be $1,2, \ldots, n$ - 1 point.

d) It is shown that there is a rectangle $1 \times n$ (covering the corner cell) in the partition - 3 points.

The points for items a)-d) are summed (the total score is 7).