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.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{k=\left\lfloor\sqrt{n-1}\right\rfloor =\left\lceil\sqrt n\right\rceil-1.} \]

Solution

Put \(k=\lfloor\sqrt{n-1}\rfloor\). Thus \[ k^2+1\le n\le (k+1)^2. \]

We first prove that an empty \(k\times k\) square always exists. Consider the rook in the first column, and choose \(k\) consecutive rows containing it. These rows contain exactly \(k\) rooks.

Within these rows, partition columns \(2,3,\ldots,k^2+1\) into \(k\) consecutive groups of \(k\) columns. This gives \(k\) disjoint \(k\times k\) squares. The rook in the first column belongs to none of them, so together these squares contain at most \(k-1\) rooks. Hence at least one is empty.

We now construct a peaceful configuration with no empty \((k+1)\times(k+1)\) square. Write \(m=k+1\). We first give such a construction on an \(m^2\times m^2\) board, then restrict it to the required board.

Number the rows and columns from \(1\) to \(m^2\). For every pair of integers \(u,v\) with \(0\le u,v<m\), place a rook at \[ (\text{row},\text{column})=(mu+v+1,\;mv+u+1). \] Every row and every column occurs exactly once, so this configuration is peaceful.

We claim that every \(m\times m\) square contains a rook. To prove this, take any \(m\) consecutive rows, and write their first row as \[ ma+b+1,\qquad 0\le a,b<m. \] If \(b>0\), these rows cross into the next block of \(m\) rows, so \(a\le m-2\). The columns occupied by the rooks in these rows, listed in increasing order, are \[ c_j= \begin{cases} mj+a+2,&0\le j<b,\\ mj+a+1,&b\le j<m. \end{cases} \] Indeed, the first group comes from rows in block \(a+1\), and the second from rows in block \(a\).

These column numbers satisfy \[ c_0\le m,\qquad c_{m-1}\ge m^2-m+1,\qquad c_{j+1}-c_j\le m\quad(0\le j<m-1). \] For the first inequality, use \(a\le m-2\) when \(b>0\); the other inequalities follow directly from the formula.

Consequently, there are at most \(m-1\) unoccupied columns before the first occupied column, between any two consecutive occupied columns, or after the last occupied column. Thus every set of \(m\) consecutive columns contains a rook from our chosen rows. This proves the claim.

Finally, retain only the first \(n\) rows and first \(n\) columns of this board, which is possible because \(n\le m^2\). Every \(m\times m\) square in the resulting \(n\times n\) board still contains one of the retained rooks.

Suppose \(s\) rooks remain. They occupy distinct rows and distinct columns, leaving exactly \(n-s\) empty rows and \(n-s\) empty columns. Pair these empty rows and columns arbitrarily, and place a rook at each paired intersection. The resulting configuration is peaceful, and adding rooks preserves the property that every \(m\times m\) square contains a rook.

Therefore an empty square of side \(m=k+1\) cannot always be guaranteed. Neither can any larger empty square, since it would contain an empty \(m\times m\) square. Together with the lower bound, this proves the answer.

The solution was checked against the official IMO shortlist solutions.