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 4 of 5: Lower bound: extending to n < ℓ²

Previous step Next step

n < \ell^2 : \text{trim rows/columns, then re-pair empty ones}

Detailed analysis

For $n<\ell^2$ , start from the construction above for $\ell^2$ and delete the bottom $\ell^2-n$ rows together with the rightmost $\ell^2-n$ columns. No $\ell\times\ell$ square becomes empty by this deletion, but some remaining rows and columns may now be empty of rooks; since the numbers of empty rows and empty columns are equal, pair them up arbitrarily and place a rook at each paired (empty row, empty column) crossing to restore a peaceful configuration on $n$ rooks with no empty $\ell\times\ell$ square.