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 3 of 5: Lower bound: an explicit peaceful configuration for n = ℓ²

Previous step Next step

n = \ell^2 : \text{rook at } (r,c),\ r=p\ell+q \implies c \equiv q\ell+p \pmod{\ell^2}

Detailed analysis

For $n=\ell^2$ , number rows and columns $0,\ldots,\ell^2-1$ and, writing row $r=p\ell+q$ with $0\le p,q<\ell$ , place the rook of row $r$ in column $q\ell+p$ ; this uses each column exactly once. One checks every $\ell\times\ell$ square meets one of these positions: for $\ell$ consecutive rows starting at row $p\ell+q$ , the occupied columns, sorted, increase by steps of at most $\ell$ and start at most $\ell-1$ , so any block of $\ell$ consecutive columns catches one of them.