## Task A-4.4.

Given is a board of dimensions $n \times n$ and tiles of dimensions $1 \times 1, 1 \times 2, \ldots, 1 \times n$.

In how many ways can $\frac{1}{2} n(n+1)$ fields of the board be selected so that the selected part can be covered by tiles placed horizontally, but also by tiles placed vertically?
## Solution.

Each way of selecting fields on the board will be represented by one coloring of the board in black and white. The fields that are among the $\frac{1}{2} n(n+1)$ selected will be painted black, and the rest of the fields will be painted white. Then we will count how many well-colored boards there are (boards whose coloring satisfies the conditions of the problem).

First, note that the total number of black fields on the board is equal to the total number of fields that all tiles cover (whether in horizontal or vertical coverage). Furthermore, in order to place a tile of shape $n \times 1$ (a vertically placed tile of shape $1 \times n$), it is necessary to paint at least one field black in each row. This means that in horizontal tiling, each of the $n$ tiles will be in a separate row, so for each $k \in\{1,2,3, \ldots, n\}$ there will be a row in which $k$ fields are painted black. Therefore, for each coloring, there is exactly one way to cover those fields with tiles by placing them horizontally. Analogous statements hold for vertical tiling.

Now consider where we can place a $1 \times 1$ tile during horizontal tiling. The column in which the $n \times 1$ tile is located is entirely painted black, so we must use all the tiles to cover those fields in horizontal tiling. Among them is a (horizontal) $1 \times 1$ tile. Furthermore, in the column where the $(n-1) \times 1$ tile is located, all fields except one are black, and the white field can only be in the first or last row. If the (horizontally placed) $1 \times 1$ tile were not in the first or last row, we would have at least two black fields in the row where it is located (one due to the $n \times 1$ tile, and one due to the $(n-1) \times 1$ tile), which is impossible since only one field in that row can be black. Therefore, that tile is in the first or last row of the board.

Now consider where we can place a $1 \times 2$ tile. Look at the part of the board of shape $(n-1) \times n$ from which the row in which exactly one field is painted black (which is the first or last row) has been removed. In this part of the board, two columns are entirely black due to the tiles $n \times 1$ and $(n-1) \times 1$, and so is the row in which the $1 \times 2$ tile is located. Furthermore, in the column where the $(n-2) \times 1$ tile is located, all fields except one are black. The remaining white field in the $(n-1) \times n$ board can only be in the first or last row. Since the row in which the $1 \times 2$ tile is located has exactly two black fields, we conclude that the tile must be in the first or last row of the remaining part of the board $(n-1) \times n$.

We can continue this reasoning inductively: assume that each tile $1 \times i$, $i=1, \ldots, k$ must be in the first or last row of the remaining part of the board $(n-i+1) \times n$, and that $k+1$ columns in the remaining part of the board $(n-k) \times n$ are entirely black (due to the tiles $n \times 1, \ldots,(n-k) \times 1$). Then, due to the tile of shape $(n-k-1) \times 1$ (in whose column all fields except in the first or last row are black), the tile of shape $1 \times(k+1)$ must be in the first or last row of the remaining part of the board $(n-k) \times n$.

Therefore, for each well-colored board, there is a permutation $\left(r_{1}, r_{2}, \ldots, r_{n}\right)$ of the set $\{1,2, \ldots, n\}$ constructed as follows: the number 1 is in the first or last position, the number 2 is in the first free or last free position, etc. This permutation indicates that row $i$ contains $r_{i}$ black fields. Note that there are $2^{n-1}$ such permutations since for all numbers $1,2, \ldots, n-1$ we have 2 choices.

We can apply the same arguments to the columns: there is a permutation $\left(s_{1}, s_{2}, \ldots, s_{n}\right)$ of the set $\{1,2, \ldots, n\}$ constructed in the same way as the permutation $\left(r_{1}, r_{2}, \ldots, r_{n}\right)$, which indicates that column $i$ contains $s_{i}$ black fields.

The total number of pairs of such permutations is $2^{n-1} \cdot 2^{n-1}=2^{2 n-2}$, and each well-colored board is associated with one such pair of permutations. We will also prove the converse: each pair of permutations $\left(r_{1}, r_{2}, \ldots, r_{n}\right)$ and $\left(s_{1}, s_{2}, \ldots, s_{n}\right)$ (constructed as above) represents a unique well-colored $n \times n$ board.

Consider the index $i_{1}$ for which $s_{i_{1}}=n$. In the $i_{1}$-th column, there must be $n$ black fields, so we paint all the fields in that column black. Consider the index $j_{1}$ for which $r_{j_{1}}=1$. We know that the $j_{1}$-th row is the first or last, and all fields except one must be black, so we paint all the uncolored fields in that row white.

Now consider the index $i_{2}$ for which $s_{i_{2}}=n-1$. From the construction of the permutation $(s_{1}, \ldots, s_{n})$, the number $n-1$ is immediately next to the position with index $i_{1}$. In that column, all fields except one must be black. One field is already painted white (in row $r_{j_{1}}$), so we paint all the others black. Then we paint all the uncolored fields in row $j_{2}$ (the index for which $s_{j_{2}}=2$) white. In that row, it will be possible to place a $1 \times 2$ tile because $i_{1}$ and $i_{2}$ are consecutive natural numbers. Also, in column $i_{2}$, it will be possible to place a tile of shape $(n-1) \times 1$, due to the construction of the permutation $\left(r_{1}, r_{2}, \ldots, r_{n}\right)$.

We can continue this coloring inductively: the column $i_{k}$ in which $k$ black fields must be located will be uniquely painted because then $n-k$ fields will already be white. Also, since that column is immediately next to all other columns that are already painted black, it will be possible to place a tile $1 \times k$ in column $j_{k}$ (for which $r_{j_{k}}=k$), and it will also be possible to place a tile of shape $(n-k) \times 1$.

Since each pair of permutations $\left(r_{1}, r_{2}, \ldots, r_{n}\right)$ and $\left(s_{1}, s_{2}, \ldots, s_{n}\right)$ constructed as above represents a well-colored $n \times n$ board that is unique, we conclude that the number of such boards is equal to the number of pairs of permutations. Thus, the number of ways to select fields on the board is $2^{2 n-2}$.