Problem 2

Let

n\ge2

be an integer. Consider an

n\times n

chessboard consisting of

n^2

unit squares. A configuration of

n

rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer

k

such that, for each peaceful configuration of

n

rooks, there is a

k\times k

square which does not contain a rook on any of its

k^2

unit squares.

Step 5 of 5: Conclusion

Previous step Next step

k = \left\lfloor \sqrt{n-1} \right\rfloor = \max\{\ell : \ell^2 < n\}

Detailed analysis

Combining the two parts: $\ell$ works for every peaceful configuration exactly when $\ell^2<n$ , and fails to be forced when $\ell^2\ge n$ . The greatest such $\ell$ is the largest integer with $\ell^2<n$ , i.e. $\ell^2\le n-1$ , which is $\ell=\lfloor\sqrt{n-1}\rfloor$ ; this is the required value of $k$ .