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 2 of 5: Upper bound: pigeonhole on ℓ² × ℓ blocks

Previous step Next step

n > \ell^2 \implies \text{some } \ell\times\ell \text{ square is empty}

Detailed analysis

Assume $n>\ell^2$ . Take a row $R$ whose rook is in the leftmost column among all rows, and let $U$ be the union of $\ell$ consecutive rows including $R$ ; $U$ contains exactly $\ell$ rooks. Removing the $n-\ell^2\ge1$ leftmost columns from $U$ (which removes at least the rook of $R$ ) leaves an $\ell^2\times\ell$ rectangle with at most $\ell-1$ rooks, splittable into $\ell$ squares of size $\ell\times\ell$ ; by pigeonhole one of these squares is empty.