Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 IMO Problems/Problem 2"

m (→‎Solution)
(→‎Solution)
Line 9: Line 9:
 
by the Pigeonhole Principle there exists a <math>k \times k</math> square in <math>C</math> not covered by any rook in <math>C</math>. Clearly, that square cannot be covered by any rook outside of <math>C</math>, and so it is a valid choice.
 
by the Pigeonhole Principle there exists a <math>k \times k</math> square in <math>C</math> not covered by any rook in <math>C</math>. Clearly, that square cannot be covered by any rook outside of <math>C</math>, and so it is a valid choice.
  
−
It remains to show that there exists a chessboard without a <math>(k+1) \times (k+1)</math> 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 <math>(k+1)</math> spaces down of the first rook. Then, place a rook 1 space to the right and <math>(k+1)</math> 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 <math>(k+1) \times (k+1)</math> square in the board will be occupied by at least one rook, completing the proof.
+
It remains to show that there exists a chessboard without a <math>(k+1) \times (k+1)</math> 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 <math>(k+1)</math> spaces down of the first rook. Then, place a rook 1 space to the right and <math>(k+1)</math> 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 is clearly peaceful, and because <math>(k+1)^2 > n</math> it has the property that any <math>(k+1) \times (k+1)</math> square in the board will be occupied by at least one rook, completing the proof.
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 18:55, 9 February 2015

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 is clearly peaceful, and because $(k+1)^2 > n$ it 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.

See Also

2014 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_IMO_Problems/Problem_2&oldid=67757"