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"

(→‎Solution)
m (→‎See Also)
 
(3 intermediate revisions by 2 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
We claim the answer is <math>k = [\sqrt{n}] - 1</math>, where <math>[n]</math> is the ceiling function of <math>n</math>; i.e., the least integer greater than or equal to <math>n</math>. Notice that <math>[n] < n + 1</math>.
+
We claim the answer is <math>k = \lceil \sqrt{n}\rceil  - 1</math>, where <math>\lceil n\rceil </math> is the ceiling function of <math>n</math>; i.e., the least integer greater than or equal to <math>n</math>. Notice that <math>\lceil n\rceil  < n + 1</math>.
  
 
First, we shall show that each <math>n \times n</math> chessboard with a peaceful configuration of <math>n</math> rooks contains a valid <math>k \times k</math> square. Consider firstly the rook <math>R</math> on the top row of the board. Because <math>k < n</math>, there exists a set <math>C</math> of <math>k</math> consecutive columns, one of which contains rook <math>R</math>. Consider the <math>n - k + 1</math> <math>k \times k</math> squares in <math>C</math>. Of them, only one contains the rook <math>R</math> on one of its squares. Furthermore, each of the other <math>k - 1</math> rooks in <math>C</math> can only make up to <math>k</math> of the <math>k \times k</math> squares have it on one of its squares. Therefore, because
 
First, we shall show that each <math>n \times n</math> chessboard with a peaceful configuration of <math>n</math> rooks contains a valid <math>k \times k</math> square. Consider firstly the rook <math>R</math> on the top row of the board. Because <math>k < n</math>, there exists a set <math>C</math> of <math>k</math> consecutive columns, one of which contains rook <math>R</math>. Consider the <math>n - k + 1</math> <math>k \times k</math> squares in <math>C</math>. Of them, only one contains the rook <math>R</math> on one of its squares. Furthermore, each of the other <math>k - 1</math> rooks in <math>C</math> can only make up to <math>k</math> of the <math>k \times k</math> squares have it on one of its squares. Therefore, because
−
<cmath>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,</cmath>
+
<cmath>n - k + 1 = n - \lceil \sqrt{n}\rceil  + 2 > n - \sqrt{n} + 1 = \sqrt{n} (\sqrt{n} - 1) + 1 > (\lceil \sqrt{n}\rceil  - 1) (\lceil \sqrt{n}\rceil  - 2) + 1 = k(k - 1) + 1,</cmath>
 
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}}
Line 15: Line 15:
 
==See Also==
 
==See Also==
  
−
{{IMO box|year=2014|num-b=1|num-a=2}}
+
{{IMO box|year=2014|num-b=1|num-a=3}}
  
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 10:36, 1 December 2018

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 = \lceil \sqrt{n}\rceil - 1$, where $\lceil n\rceil$ is the ceiling function of $n$; i.e., the least integer greater than or equal to $n$. Notice that $\lceil n\rceil < 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 - \lceil \sqrt{n}\rceil + 2 > n - \sqrt{n} + 1 = \sqrt{n} (\sqrt{n} - 1) + 1 > (\lceil \sqrt{n}\rceil - 1) (\lceil \sqrt{n}\rceil - 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 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_IMO_Problems/Problem_2&oldid=99210"