, 2020

The number of red squares must equal the total number of squares covered by the $n$ tiles, hence the tiles are only put on top of red squares. Consider a colouring of the board and the corresponding horizontal covering by the tiles (where all tiles are placed horizontally) and the vertical covering. We will deduce a number of properties for the colouring, and then count how many colourings there are. The tile whose size is $1 \times k$ is called the *$k$-tile*.

Because the horizontal covering contains an $n$-tile, each column has at least one red square. In the vertical covering, each column must therefore contain at least one tile; because there are exactly $n$ tiles, this means that there must be exactly one tile in each column. In the same way, each row must contain exactly one tile in the horizontal covering. Now number the rows and columns depending on the number of the tile that has been put there: so row $i$ is the row containing the $i$-tile in the horizontal covering, and analogously for the columns.

We will now prove that the square in row $i$ and column $j$ (which will be called $(i, j)$) is red if and only if $i+j \ge n+1$. We prove this using induction on $i$.

In row 1, there is only one red square, so that must be in the column containing the $n$-tile in the vertical covering, i.e. column $n$. Hence, the square $(1, j)$ is red if and only if $j=n$, or if and only if $1+j \ge n+1$.

Now let $k \ge 1$ and suppose the statement has been proved for all $i \le k$. We want to prove the statement for $i=k+1$, i.e. that the square $(k+1, j)$ is red if and only if $k+1+j \ge n+1$, or $j \ge n-k$. Consider a column $j \ge n-k$. Because of the induction hypothesis, we know exactly how many red squares this column has in rows $1, 2, ..., k$: namely, the square $(i, j)$ is red if and only if $i+j \ge n+1$, or $i \ge n+1-j$; these are $k-(n-j) = j+k-n$ squares. In the other $n-k$ rows, this column needs another $j-(j+k-n) = n-k$ red squares. Hence, this column has a red square in each of these rows, in particular in the row $i=k+1$. In row $i=k+1$, the squares $(i, j)$ with $j \ge n-k$ are all red, and these are $k+1$ squares. Hence, these are exactly all red squares in row $i=k+1$, hence the square $(i, j)$ is red if and only if $j \ge n-k$, or if and only if $i+j \ge n-k+k+1=n+1$. This finishes the proof by induction.

Now consider two adjacent rows with row numbers $a$ and $b$, with $a > b$. In column $n-b$, there is a red square in row $a$ (because $a+n-b > n$), but not in row $b$. In the row directly on the other side of row $b$ (if this row exists), there cannot be a red square in column $n-b$, because the red squares in column $n-b$ would otherwise not be consecutive, and then the tile with number $n-b$ cannot lie there. The row number of this row must therefore be smaller than $b$. We conclude that the row numbers cannot decrease first and then increase. Above and below row $n$, there must be a row with a smaller number (or no row at all), and the row numbers must descend in both directions from there. We see that the row numbers from top to bottom must first ascend until we get to row $n$, and then they must descend. The same can be proved for the column numbers.

Vice versa, we have to prove that if the row and column numbers are first ascending and then descending, then the horizontal and vertical tiles can be put. To prove this, we colour the square $(i, j)$ red if and only if $i+j \ge n+1$. For a fixed $i$, the red squares are the squares $(i, j)$ with $j \ge n+1-i$; because of the order of the column numbers, these columns are adjacent. Hence, in each row, the red squares are adjacent. The horizontal tiles can be put exactly on top of the red squares. In the same way, this can be done for the vertical tiles. For these row and column numbers, there was no other way to choose the colouring, because we already know that for each suitable colouring the square $(i, j)$ is red if and only if $i+j \ge n+1$.

Altogether, we are looking for the number of ways to choose the row and column numbers such that the numbers are first ascending and then descending; corresponding to each of these choices, there is exactly one way to colour the squares so that they satisfy the conditions. The number of ways to put the numbers $1$ to $n$ in an order that is first ascending and then descending, equals the number of subsets of $\{1, 2, \dots, n-1\}$. Namely, each ordering corresponds to the subset of numbers that appear before the number $n$; these can be sorted in a unique way (ascending), and the rest of the numbers must be sorted descending and put after the $n$. The number of subsets is $2^{n-1}$. Hence, the total number of colourings satisfying the conditions, is $(2^{n-1})^2 = 2^{2n-2}$. $\square$