## Task A-4.5.

In a room, there are $n$ boxes of heights $1,2,3, \ldots, n$ that need to be arranged in some order against a wall. Cat Fiko can jump from one box to the next if the next box is lower (regardless of how much lower) than the one he is on, or if it is at most 1 higher than the one he is currently on. In how many ways can the boxes be arranged so that Fiko can start from the first box in the row and jump sequentially to each subsequent box?
## First Solution.

For the arrangement of boxes, we will say it is good if Fiko can start from the first box in the sequence and jump to each subsequent box in order.

Let $a_{n}$ be the number of good arrangements of boxes for a natural number $n$.

For any good arrangement of $n$ boxes, by removing the last box, we obtain a good arrangement of $n-1$ boxes.

Conversely, if a good arrangement of boxes of heights $1,2, \ldots, n-1$ is given, then the box of height $n$ can be added to exactly two places to still obtain a good arrangement: we can add it at the beginning of the sequence or immediately after the box of height $n-1$.

Therefore, $a_{n}=2 a_{n-1}$.

From this, it follows that

$$
a_{n}=2 a_{n-1}=2^{2} a_{n-2}=\cdots=2^{n-1} a_{1}
$$

Since $a_{1}=1$, we conclude that $a_{n}=2^{n-1}$.

Note: If a student lists all possibilities for $n=1,2,3$ and correctly determines $a_{1}=1$, $a_{2}=2$, and $a_{3}=4$, and conjectures that $a_{n}=2^{n-1}$ based on these examples, they should receive 2 points. An answer without any justification carries 1 point.