IMO Shortlist

Answer. $\lfloor\sqrt{n-1}\rfloor$.

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.