Let's start with some definitions and general observations. In the following, we denote by $(i, j)$ the $1 \times 1$ small square located at the $j$-th level of the $i$-th step. We will call the upper square each small square $(k, k)$, i.e., each square located at the very top of a step.
We consider the construction of a staircase of size $n$ using $f(n)$ square stones. Two distinct upper squares cannot belong to the same stone. Since there are exactly $n$ upper squares in a staircase of size $n$, we deduce that $f(n) \geqslant n$ for all $n \geqslant 0$. We now address questions 1 and 2.

1. First, it is clear that $f(0)=0$. Now let $n \geqslant 1$ be an integer such that $f(n)=n$.

From the above observation, each stone contains a unique upper square. This is particularly the case for the stone containing the square $(n, 1)$. But then this stone divides the staircase into two symmetric parts. Thus, each part forms a staircase of size $(n-1) / 2$, such that $f((n-1) / 2)=(n-1) / 2$. Consequently, an immediate induction shows that there exists an integer $k \geqslant 0$ such that $n=2^{k}-1$.
Conversely, and following this construction in the other direction, an immediate induction shows that $f\left(2^{k}-1\right)=2^{k}-1$ for all integers $k \geqslant 0$.
The integers $n$ sought are therefore the integers of the form $n=2^{k}-1$ with $k \geqslant 0$.
2. This time, we know that $n \geqslant 2$. Furthermore, the stone containing the square $(n, 1)$ cannot contain an upper square; indeed, if it did, it would cut the staircase into two symmetric parts, each forming a staircase of size $(n-1) / 2$, so $f(n)-n$ would have to be even.
It is therefore the only stone that does not contain an upper square. Let $\ell \times \ell$ be the dimensions of this stone. Once $\ell$ and $n$ are fixed, each other stone must contain an upper square, and the dimensions of the stones are therefore prescribed. In particular, an immediate induction on $n+i-j$ shows that the stones containing the squares $(i, j)$ and $(n+1-j, n+1-i)$ actually occupy symmetric positions.
In order to reduce the problem to treating only staircases where each stone contains an upper square, we specifically focus on the stones containing the squares $(n, 1)$, $(n-\ell, 1)$, $(n, \ell+1)$, and $(n-\ell, \ell+1)$; the latter stone exists only if $n \neq 2 \ell$.
We first assume that $n \neq 2 \ell$. In this case, our four stones are pairwise disjoint, with respective sizes $\ell \times \ell$, $(n+1-\ell) / 2$, $(n+1-\ell) / 2$, and $(n+1-2 \ell) / 2$, and they cut the staircase into four small staircases: two staircases of size $(n-1-\ell) / 2$ and two staircases of size $(n-1-2 \ell) / 2$. Given the results of the first question, there therefore exist two non-zero natural numbers $k$ and $k'$ such that $n=2^{k}+\ell-1=2^{k'}+2 \ell-1$.

This means that $\ell=2^{k}-2^{k'}$, so $k \geqslant k'$ and $n=2^{k+1}-2^{k'}-1$. Conversely, if there exist integers $k \geqslant k' \geqslant 1$ such that $n=2^{k+1}-2^{k'}-1$, it is indeed sufficient to choose $\ell=2^{k}-2^{k'}$ for our construction to work.
Similarly, if $n=2 \ell$, we actually have three stones, which cut the staircase into four small staircases of size $(n-1-\ell) / 2=(\ell-1) / 2$, so there exists a non-zero natural number $k$ such that $\ell=2^{k}-1$ and $n=2^{k+1}-2$. Conversely, if there exists an integer $k \geqslant 1$ such that $n=2^{k+1}-2$, it is indeed sufficient to choose $\ell=n / 2$ for our construction to work. The integers $n$ sought are therefore the integers of the form $n=2^{k+1}-2^{k'}-1$ with $k \geqslant k' \geqslant 0$.

## Exercise for both Junior and Senior groups