Difference between revisions of "2014 IMO Problems/Problem 2"
(→Solution) |
m (→Solution) |
||
Line 6: | Line 6: | ||
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 - [\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> |
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. | ||
Revision as of 19:53, 9 February 2015
Problem
Let be an integer. Consider an
chessboard consisting of
unit squares. A configuration of
rooks on this board is
if every row and every column contains exactly one rook. Find the greatest positive integer
such that, for each peaceful configuration of
rooks, there is a
square which does not contain a rook on any of its
squares.
Solution
We claim the answer is , where
is the ceiling function of
; i.e., the least integer greater than or equal to
. Notice that
.
First, we shall show that each chessboard with a peaceful configuration of
rooks contains a valid
square. Consider firstly the rook
on the top row of the board. Because
, there exists a set
of
consecutive columns, one of which contains rook
. Consider the
squares in
. Of them, only one contains the rook
on one of its squares. Furthermore, each of the other
rooks in
can only make up to
of the
squares have it on one of its squares. Therefore, because
by the Pigeonhole Principle there exists a
square in
not covered by any rook in
. Clearly, that square cannot be covered by any rook outside of
, and so it is a valid choice.
It remains to show that there exists a chessboard without a 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
spaces down of the first rook. Then, place a rook 1 space to the right and
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
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 |