Question 95: Let $n \geq 2$ be an integer, consider an $n \times n$ chessboard composed of $n^2$ unit squares. If each row and each column contains exactly one “rook”, then the placement of $n$ rooks is called “peaceful”. Find the largest positive integer $k$, such that for any peaceful placement of $n$ rooks, there exists a $k \times k$ square, whose $k^2$ unit squares all do not contain a rook.
The 95th question:
Solution: The maximum value of $k$ we are looking for is $[\sqrt{n-1}]$.
Next, we will prove two conclusions to show that the maximum value sought is $\mathrm{k}_{\max }=[\sqrt{\mathrm{n}-1}]$.
(1) If $\mathrm{n}>\mathrm{m}^{2}$, then for any peaceful placement of $\mathrm{n}$ rooks, there exists an empty $\mathrm{m} \times \mathrm{m}$ square;
(2) If $\mathrm{n} \leq \mathrm{m}^{2}$, then there exists a peaceful placement of $\mathrm{n}$ rooks such that each $\mathrm{m} \times \mathrm{m}$ square contains at least one rook.

Proof: (1) When $\mathrm{n}>\mathrm{m}^{2}$, for any peaceful placement of $\mathrm{n}$ rooks, there exists a row $\mathrm{R}$ such that the first square in this row contains a rook. Take $\mathrm{m}$ consecutive rows (including row $\mathrm{R}$), and their union $U$ contains exactly $\mathrm{m}$ rooks. At this point, consider the columns from the 2nd to the $\mathrm{m}^{2}+1(\leq \mathrm{n})$ column in set $\mathrm{U}$. This $\mathrm{m} \times \mathrm{m}^{2}$ rectangle can be divided into $\mathrm{m}$ $\mathrm{m} \times \mathrm{m}$ squares, but there are at most $\mathrm{m}-1$ rooks in it (since set $U$ already has one rook in the 1st column), thus, among these $\mathrm{m}$ $\mathrm{m} \times \mathrm{m}$ squares, at least one is empty.
(2) For the case of $n=m^{2}$, first construct a peaceful placement scheme without any empty $\mathrm{m} \times \mathrm{m}$ square. Label all rows from bottom to top as $0, 1, 2, \ldots, \mathrm{~m}^{2}-1$, and label all columns from left to right as $0, 1, 2, \ldots, m^{2}-1$, and denote the unit square in the $\mathrm{r}$-th row and $\mathrm{c}$-th column as $(\mathrm{r}, \mathrm{c})$.

Place a rook in each unit square of the form $(\mathrm{i} \cdot \mathrm{m}+\mathrm{j}, \mathrm{j} \cdot \mathrm{m}+\mathrm{i})(\mathrm{i}, \mathrm{j}=0, 1, \ldots, m-1)$. Since each number from 0 to $m^{2}-1$ has a unique representation of the form $i \cdot m+j$ (in fact, it is the $m$-ary representation, (ij) $)_{m}=\mathrm{i} \cdot \mathrm{m}+\mathrm{j}$), there is exactly one rook in each row and each column. We prove that at this point, each $\mathrm{m} \times \mathrm{m}$ square contains at least one rook.

At this point, for any $\mathrm{m} \times \mathrm{m}$ square $\mathrm{A}$, let the label of the lowest row of square $\mathrm{A}$ be $\mathrm{pm}+\mathrm{q}$, then the $\mathrm{m}$ rows of square $\mathrm{A}$ contain $\mathrm{m}$ rooks, and the labels of the columns where these $\mathrm{m}$ rooks are located are $\mathrm{qm}+\mathrm{p}, \mathrm{q}(\mathrm{m}+1)+\mathrm{p}, \ldots, (m-1) m+p, 0 \cdot m+(p+1), 1 \cdot m+(p+1), \ldots, (q-1) m+(p+1)$. Arrange these numbers in ascending order:
$$
p+1, m+(p+1), \ldots, (q-1) m+(p+1), q m+p, (q+1) m+p, \ldots, (m-1) m+p
$$
The difference between any two adjacent numbers in this sequence does not exceed $\mathrm{m}$, the first number does not exceed $\mathrm{m}-1$ (if $\mathrm{p}=\mathrm{m}-1$, then $\mathrm{q}=0$, so the first number will be $\mathrm{qm}+\mathrm{p}=\mathrm{m}-1$), and the last number is not less than $\mathrm{m}(\mathrm{m}-1)$. Therefore, at least one of the labels of the $\mathrm{m}$ columns of square $\mathrm{A}$ appears in this sequence, indicating that square $\mathrm{A}$ contains at least one rook.
For the case of $\mathrm{n}<\mathrm{m}^{2}$, construct a peaceful placement scheme without any empty $\mathrm{m} \times \mathrm{m}$ square.
For this, consider the construction of the $\mathrm{m}^{2} \times \mathrm{m}^{2}$ case as described above, and delete the last $\mathrm{m}^{2}-\mathrm{n}$ columns and the top $\mathrm{m}^{2}-\mathrm{n}$ rows, resulting in an $\mathrm{n} \times \mathrm{n}$ square, and there are no empty $\mathrm{m} \times \mathrm{m}$ squares in it. However, some rows and columns may be empty, but obviously, the number of empty rows is equal to the number of empty columns, so they can be paired one-to-one, and then place a rook at the intersection of the corresponding empty rows and columns, thus obtaining a peaceful placement scheme of $\mathrm{n}$ rooks on an $\mathrm{n} \times \mathrm{n}$ chessboard, and there are no empty $\mathrm{m} \times \mathrm{m}$ squares in it.
In summary, the maximum value sought is $\mathrm{k}_{\max }=[\sqrt{\mathrm{n}-1}]$.