IMO 2014 Problem 2

Let \(n \ge 2\) 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.

==================

Solution:

\(k=\lfloor\sqrt{n-1}\rfloor\).

We will show that all peaceful configurations of \(n\) rooks permit a \(k\times k\) rook-free square if and only if \(k^2\lt n\).

If \(k^2\lt n\), then find \(k\) consecutive columns that contains a rook at the very bottom. These \(n\) rows are then partitioned into \(k\) consecutive groups with each group containing a rook in the bottom row. By pigeonhole principle there is a group with more than \(k\) rows, which therefore permits a \(k\times k\) rook-free square.

If \(k^2\ge n\), let \(n'=k^2\). There is a \(n'\times n'\) peaceful configuration of \(n'\) rooks without \(k\times k\) rook-free square. Truncate it to \(n\times n\), which may not have \(n\) rooks but already denies the desired rook-free square.