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 1 of 5: State the answer and the plan

Previous step Next step

k = \left\lfloor \sqrt{n-1} \right\rfloor

Detailed analysis

The answer is $k=\lfloor\sqrt{n-1}\rfloor$ . This is shown by proving, for each positive integer $\ell$ : (i) if $n>\ell^2$ then every peaceful configuration has an empty $\ell\times\ell$ square, and (ii) if $n\le\ell^2$ then some peaceful configuration has none; together these pin down the largest working $\ell$ as $\lfloor\sqrt{n-1}\rfloor$ .