## Task 2.

Let $N$ be a natural number. We call a staircase a part of a square plate of dimensions $N \times N$ that consists of the first $K$ fields in the $K$-th row for $K=1,2, \ldots, N$. In how many ways can the staircase be cut into rectangles of different areas that consist of the fields of the given plate?
## Solution.

Notice that each square on the diagonal is in a different rectangle, so at least $N$ rectangles are needed. The combined area of these rectangles is at least $1+2+\cdots+N$.

Since the area of the stairs is $1+2+\cdots+N$, there must be exactly $N$ rectangles, which have areas $1,2, \ldots, N$, and each must contain exactly one square on the diagonal.

Consider the rectangle that contains the square in the corner of the stairs and assume its dimensions are $A \times B$. Since this rectangle also contains one square on the diagonal, $A+B=N+1$.

Thus, the area of this rectangle is $A \cdot B = A \cdot (N+1-A) \geqslant N$.

Since the area of any rectangle is at most $N$, equality must hold. From this, we conclude that $A=1$ or $A=N$.

In both cases, the rectangle that contains the square in the corner of the stairs must have an area of $N$, and after cutting it out, we are left with stairs obtained from a board of dimensions $(N-1) \times (N-1)$.

If we denote by $F_{N}$ the number of ways to cut the stairs obtained from a board of dimensions $N \times N$, then $F_{N}=2 \cdot F_{N-1}$. Since $F_{1}=1$, it follows that $F_{N}=2^{N-1}$.