Exercise 3. Let $\mathrm{n}$ be a natural number. A staircase of size $\mathrm{n}$ is made up of small $1 \times 1$ squares, with 1 square for the first step, 2 squares for the second step, and so on, up to $n$ squares for the $n^{\text{th}}$ step.

We have square stones (with integer side lengths) of all sizes to build this staircase, and we denote $f(n)$ as the minimum number of stones needed to build a staircase of size $n$. For example, $f(2)=3$ and $f(4)=7$, as illustrated below.

![](https://cdn.mathpix.com/cropped/2024_06_04_8eef2314e2bac5f22e49g-3.jpg?height=228&width=826&top_left_y=477&top_left_x=615)

1. Find all integers $n \geqslant 0$ such that $f(n)=n$.
2. Find all integers $n \geqslant 0$ such that $f(n)=n+1$.
Solution to Exercise 3 Let's start with some definitions and general observations. In the following, we denote by $(i, j)$ the small $1 \times 1$ square located at the $j$-th level of the $i^{\text{th}}$ step. We will call the upper square each small square $(k, k)$, that is, 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 2 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$. On the other hand, the stone containing the square $(n, 1)$ cannot contain an upper square; indeed, if it did, it would cut the staircase into 2 symmetric parts, each forming a staircase of size $(n-1) / 2$, so that $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 common to Junior and Senior groups