(a) A diagonal square in an $n$-staircase is a unit square that lies on the diagonal going from the top-left to the bottom-right. A minimal tiling of an $n$-staircase is a tiling consisting of $f(n)$ square tiles.

Observe that $f(n) \geq n$ for all $n$. There are $n$ diagonal squares in an $n$-staircase, and a square tile can cover at most one diagonal square, so any tiling requires at least $n$ square tiles. In other words, $f(n) \geq n$. Hence, if $f(n)=n$, then each square tile covers exactly one diagonal square.

Let $n$ be a positive integer such that $f(n)=n$, and consider a minimal tiling of an $n$-staircase. The only square tile that can cover the unit square in the first row is the unit square itself.

!

## Sun Life Financial

!
that can cover this unit square and a diagonal square is a $4 \times 4$ square tile.

!

Continuing this construction, we see that the side lengths of the square tiles we encounter will be $1,2,4$, and so on, up to $2^{k}$ for some nonnegative integer $k$. Therefore, $n$, the height of the $n$-staircase, is equal to $1+2+4+\cdots+2^{k}=2^{k+1}-1$. Alternatively, $n=2^{k}-1$ for some positive integer $k$. Let $p(k)=2^{k}-1$.

Conversely, we can tile a $p(k)$-staircase with $p(k)$ square tiles recursively as follows: We have that $p(1)=1$, and we can tile a 1 -staircase with 1 square tile. Assume that we can tile a $p(k)$-staircase with $p(k)$ square tiles for some positive integer $k$.

Consider a $p(k+1)$-staircase. Place a $2^{k} \times 2^{k}$ square tile in the bottom left corner. Note that this square tile covers a diagonal square. Then $p(k+1)-2^{k}=$ $2^{k+1}-1-2^{k}=2^{k}-1=p(k)$, so we are left with two $p(k)$-staircases.

!

Furthermore, these two $p(k)$-staircases can be tiled with $2 p(k)$ square tiles, which means we use $2 p(k)+1=p(k+1)$ square tiles.

Therefore, $f(n)=n$ if and only if $n=2^{k}-1=p(k)$ for some positive integer $k$. In other words, the binary representation of $n$ consists of all $1 \mathrm{~s}$, with no $0 \mathrm{~s}$.

(b) Let $n$ be a positive integer such that $f(n)=n+1$, and consider a minimal tiling of an $n$-staircase. Since there are $n$ diagonal squares, every square tile except one covers a diagonal square. We claim that the square tile that covers the bottom-left unit square must be the square tile that does not cover a diagonal square.

If $n$ is even, then this fact is obvious, because the square tile that covers the bottom-left unit square cannot cover any diagonal square, so assume that $n$ is odd. Let $n=2 m+1$. We may assume that $n>1$, so $m \geq 1$. Suppose that the square tile covering the bottom-left unit square also covers a diagonal square. Then the side length of this square tile must be $m+1$. After this $(m+1) \times(m+1)$ square tile has been placed, we are left with two $m$-staircases.

!

Hence, $f(n)=2 f(m)+1$. But $2 f(m)+1$ is odd, and $n+1=2 m+2$ is even, so $f(n)$ cannot be equal to $n+1$, contradiction. Therefore, the square tile that covers the bottom-left unit square is the square tile that does not cover a diagonal square.

Let $t$ be the side length of the square tile covering the bottom-left unit square. Then every other square tile must cover a diagonal square, so by the same construction as in part (a), $n=1+2+4+\cdots+2^{k-1}+t=2^{k}+t-1$ for some positive integer $k$. Furthermore, the top $p(k)=2^{k}-1$ rows of the $n$-staircase must be tiled the same way as the minimal tiling of a $p(k)$-staircase. Therefore, the horizontal line between rows $p(k)$ and $p(k)+1$ does not pass through any square tiles. Let us call such a line a fault line. Similarly, the vertical line between columns $t$ and $t+1$ is also a fault line. These two fault lines partition two $p(k)$-staircases.

!

If these two $p(k)$-staircases do not overlap, then $t=p(k)$, so $n=2 p(k)$. For example, the minimal tiling for $n=2 p(2)=6$ is shown below.

!

Hence, assume that the two $p(k)$-staircases do overlap. The intersection of the two $p(k)$-staircases is a $[p(k)-t]$-staircase. Since this $[p(k)-t]$-staircase is tiled the same way as the top $p(k)-t$ rows of a minimal tiling of a $p(k)$-staircase, $p(k)-t=p(l)$ for some positive integer $l$.

where $k$ is a positive integer. Also, our argument shows how if $n$ is of this form, then an $n$-staircase can be tiled with $n+1$ square tiles.

Finally, we observe that $n$ is of this form if and only if the binary representation of $n$ contains exactly one 0:

$$2^{k+1}-2^{l}-1=\underbrace{11 \ldots 1}_{k-l 1 \mathrm{~s}} 0 \underbrace{11 \ldots 1}_{l 1 \mathrm{~s}} \text {. }$$