32. a) What is the maximum number of rooks that can be placed on a chessboard of $n^{2}$ squares so that no two rooks threaten each other? In how many different ways can this be done?

b) What is the minimum number of rooks that can be placed on a chessboard of $n^{2}$ squares so that these rooks threaten all the squares of the board? In how many different ways can this be done?
32. a) A chessboard consisting of $n^{2}$ squares (see Fig. 39, where the case $n=8$ is shown) contains $n$ rows and $n$ columns. To ensure that no two rooks placed on this board threaten each other, it is necessary that no two rooks stand on the same row or the same column. It is clear, therefore, that the total number of rooks cannot exceed $n$, and $n$ rooks can be placed so that no two of them threaten each other: for example, by placing these rooks along one of the main diagonals of the chessboard.

![](https://cdn.mathpix.com/cropped/2024_05_21_68334347b64402497ba5g-148.jpg?height=415&width=416&top_left_y=454&top_left_x=598)

Fig. 39. 

Now let's determine how many different arrangements of $n$ rooks satisfy our conditions. We will call the first rook the one standing on the first column, the second the one standing on the second column, and so on, up to the $n$-th rook standing on the $n$-th column. The first rook can be placed on any of the $n$ rows, after which the second can be placed on any of the $n-1$ remaining rows (the row occupied by the first rook is excluded, as no two rooks should threaten each other), the third rook on any of the $n-2$ remaining unoccupied rows, and so on, up to the $(n-1)$-th rook, for which two unoccupied rows remain, and the last rook, for which only one unoccupied row remains. By combining $n$ different placements of the first rook with $n-1$ different placements of the second rook, we get $n(n-1)$ possible placements of the first two rooks; similarly, we get $n(n-1)(n-2)$ possible placements of the first three rooks, $n(n-1)(n-2)(n-3)$ placements of the first four rooks, ..., $n(n-1)(n-2) \ldots 2 \cdot 1$ different placements of all $n$ rooks. Therefore, the number of different arrangements is

$$
1 \cdot 2 \cdot 3 \ldots(n-1) n=n!
$$

In particular, for a standard chessboard, where $n=8$, we get:

$$
8!=8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=40320
$$

different arrangements.

b) All the squares of a chessboard consisting of $n^{2}$ squares cannot be under threat if there are fewer than $n$ rooks on the board. Indeed, in this case, there is at least one column without any rook; the $n$ squares of this column cannot all be under threat from the placed rooks, as the number of rooks is less than $n$ and none of them can threaten two squares of the considered column simultaneously; $n$ rooks, satisfying the conditions of the problem, can obviously be placed (see, for example, Fig. 39).

If $n$ rooks, placed on a chessboard consisting of $n^{2}$ squares, threaten all the squares of the board, then either there is one rook on each column of the board or one rook on each row. Indeed, if there were both a column and a row free from rooks, then the square at the intersection of these column and row would not be under threat. The number of ways to place rooks, one on each of the $n$ columns, is $n^{n}$ (the first rook can be placed in $n$ ways on one of the squares of the first column; the second, independently of the first, in $n$ ways on one of the squares of the second column, and so on). The number of ways to place $n$ rooks, one on each of the $n$ rows, is obviously also $n^{n}$. At first glance, it might seem that the total number of arrangements of $n$ rooks, under which they threaten all the squares of the board, is $n^{n}+n^{n}=2 n^{n}$. However, in this count, each arrangement where there is one rook on each column and simultaneously one rook on each row is counted twice. Since the total number of these latter arrangements is $n!$ (see the solution to part a)), the correct answer to the question is $2 n^{n}-n!$.

In particular, for a standard chessboard ($n=8$), we get:

$$
2 \cdot 8^{8}-8!=33514312
$$

different arrangements.