C3. Let $n \geqslant 2$ be an integer. Consider an $n \times n$ chessboard divided into $n^{2}$ unit squares. We call a configuration of $n$ rooks on this board happy if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that for every happy configuration of rooks, we can find a $k \times k$ square without a rook on any of its $k^{2}$ unit squares.
Answer. $\lfloor\sqrt{n-1}\rfloor$.
Solution. Let $\ell$ be a positive integer. We will show that (i) if $n>\ell^{2}$ then each happy configuration contains an empty $\ell \times \ell$ square, but (ii) if $n \leqslant \ell^{2}$ then there exists a happy configuration not containing such a square. These two statements together yield the answer.
(i). Assume that $n>\ell^{2}$. Consider any happy configuration. There exists a row $R$ containing a rook in its leftmost square. Take $\ell$ consecutive rows with $R$ being one of them. Their union $U$ contains exactly $\ell$ rooks. Now remove the $n-\ell^{2} \geqslant 1$ leftmost columns from $U$ (thus at least one rook is also removed). The remaining part is an $\ell^{2} \times \ell$ rectangle, so it can be split into $\ell$ squares of size $\ell \times \ell$, and this part contains at most $\ell-1$ rooks. Thus one of these squares is empty:
(ii). Now we assume that $n \leqslant \ell^{2}$. Firstly, we will construct a happy configuration with no empty $\ell \times \ell$ square for the case $n-\ell^{2}$. After that we will modify it to work for smaller values of $n$.

Let us enumerate the rows from bottom to top as well as the columns from left to right by the numbers $0,1, \ldots, \ell^{2}-1$. Every square will be denoted, as usual, by the pair $(r, c)$ of its row and column numbers. Now we put the rooks on all squares of the form $(i \ell+j, j \ell+i)$ with $i, j=0,1, \ldots, \ell-1$ (the picture below represents this arrangement for $\ell-3$ ). Since each number from 0 to $\ell^{2}-1$ has a unique representation of the form $i \ell+j(0 \leqslant i, j \leqslant \ell-1)$, each row and each column contains exactly one rook.

Next, we show that each $\ell \times \ell$ square $A$ on the board contains a rook. Consider such a square $A$, and consider $\ell$ consecutive rows the union of which contains $A$. Let the lowest of these rows have number $p \ell+q$ with $0 \leqslant p, q \leqslant \ell-1$ (notice that $p \ell+q \leqslant \ell^{2}-\ell$ ). Then the rooks in this union are placed in the columns with numbers $q \ell+p,(q+1) \ell+p, \ldots,(\ell-1) \ell+p$, $p+1, \ell+(p+1), \ldots,(q-1) \ell+p+1$, or, putting these numbers in increasing order,
$$
p+1, \ell+(p+1), \ldots,(q-1) \ell+(p+1), q \ell+p,(q+1) \ell+p, \ldots,(\ell-1) \ell+p .
$$

One readily checks that the first number in this list is at most $\ell-1$ (if $p-\ell-1$, then $q=0$, and the first listed number is $q \ell+p-\ell-1)$, the last one is at least $(\ell-1) \ell$, and the difference between any two consecutive numbers is at most $\ell$. Thus, one of the $\ell$ consecutive columns intersecting $A$ contains a number listed above, and the rook in this column is inside $A$, as required. The construction for $n-\ell^{2}$ is established.

It remains to construct a happy configuration of rooks not containing an empty $\ell \times \ell$ square for $n<\ell^{2}$. In order to achieve this, take the construction for an $\ell^{2} \times \ell^{2}$ square described above and remove the $\ell^{2}-n$ bottom rows together with the $\ell^{2}-n$ rightmost columns. We will have a rook arrangement with no empty $\ell \times \ell$ square, but several rows and columns may happen to be empty. Clearly, the number of empty rows is equal to the number of empty columns, so one can find a bijection between them, and put a rook on any crossing of an empty row and an empty column corresponding to each other.

Comment. Part (i) allows several different proofs. E.g., in the last paragraph of the solution, it suffices to deal only with the case $n=\ell^{2}+1$. Notice now that among the four corner squares, at least one is empty. So the rooks in its row and in its column are distinct. Now, deleting this row and column we obtain an $\ell^{2} \times \ell^{2}$ square with $\ell^{2}-1$ rooks in it. This square can be partitioned into $\ell^{2}$ squares of size $\ell \times \ell$, so one of them is empty.