2014 IMO Problems/Problem 2

Problem

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 $\textit{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$ squares.

Solution

We claim the answer is $k = [\sqrt{n}] - 1$ , where $[n]$ is the ceiling function of $n$ ; i.e., the least integer greater than or equal to $n$ . Notice that $[n] < n + 1$ .

First, we shall show that each $n \times n$ chessboard with a peaceful configuration of $n$ rooks contains a valid $k \times k$ square. Consider firstly the rook $R$ on the top row of the board. Because $k < n$ , there exists a set $C$ of $k$ consecutive columns, one of which contains rook $R$ . Consider the $n - k + 1$ $k \times k$ squares in $C$ . Of them, only one contains the rook $R$ on one of its squares. Furthermore, each of the other $k - 1$ rooks in $C$ can only make up to $k$ of the $k \times k$ squares have it on one of its squares. Therefore, because $n - k + 1 = n - [\sqrt{n}] + 2 > n - \sqrt{n} + 1 = \sqrt{n} (\sqrt{n} - 1) + 1 > ([\sqrt{n}] - 1) ([\sqrt{n} - 2) + 1 = k(k - 1) + 1,$ by the Pigeonhole Principle there exists a $k \times k$ square in $C$ not covered by any rook in $C$ . Clearly, that square cannot be covered by any rook outside of $C$ , and so it is a valid choice.

It remains to show that there exists a chessboard without a $(k+1) \times (k+1)$ square. Indeed, such a board exists. First, place a rook at the upper-left corner of the board. Next, place a rook 1 space to the right and $(k+1)$ spaces down of the first rook. Then, place a rook 1 space to the right and $(k+1)$ spaces down of the second rook, and so on, until the placement of a new rook will be under the lower boundary of the board. In that case, place a rook in the same unoccupied column and in the first unoccupied row, and continue placement of subsequent rooks. This arrangement of rooks has the property that any $(k+1) \times (k+1)$ square in the board will be occupied by at least one rook, completing the proof.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2014 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search

2014 IMO Problems/Problem 2

Problem

Solution

See Also