IMO 2014 #2
by Wolstenholme, Oct 26, 2014, 8:31 PM
Let 
be an integer. Consider an 
chessboard consisting of 
unit squares. A configuration of 
rooks on this board is peaceful 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 
unit squares.
Solution:
After testing some small cases, it should be clear that the solution will be
. Let's prove it! In the following lemmas, assume that the board size is 
for some 
.
Lemma 1: If
for some 
, then there exists a peaceful configuration where every 
sub-square contains a rook.
Proof: I will provide an explicit configuration. Enumerate the unit squares with ordered pairs in a Cartesian fashion, such that the bottom left unit square has coordinates
and, for example, the square in the fourth column and second row (from the bottom) has coordinates 
. Now let 
and define 
. It is clear that if one places rooks on the squares with coordinates in 
then no sub-square will lack a rook, as desired.
Lemma 2: If
for some , then there exists a peaceful configuration where every sub-square contains a rook.
Proof: We proceed by reverse induction on
, with the result in Lemma 1 as the base case. Assume that for some 
, the result in Lemma 2 holds. Now consider a peaceful configuration on an 
board such that every sub-square contains a rook. Shift left the 
-coordinate of each ordered pair corresponding to a rook by 
(modulo 
) until there is a rook in the square with coordinate . Clearly the configuration is still peaceful and clearly every sub-square still contains a rook. Now just delete the first row and column, rooks and all. This new 
board clearly still satisfies the induction hypothesis so we are done.
Lemma 3: Let
for some 
. Then in any peaceful configuration, there is an 
sub-square containing no rooks.
Proof: Assume the contrary, and let us try to create such a peaceful configuration. Consider the
sub-square in the bottom-left corner. Tiling it by squares, we see it must contain 
rooks. Then the 
square in the top- right corner must contain 
rooks. But as the square in the bottom-right corner must also contain rooks, so the right-most columns all contain more than one rook, contradiction.
The combination of these lemmas clearly implies the desired result.
be an integer. Consider an 
chessboard consisting of 
unit squares. A configuration of 
rooks on this board is peaceful 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 
unit squares.Solution:
After testing some small cases, it should be clear that the solution will be
. Let's prove it! In the following lemmas, assume that the board size is 
for some 
.Lemma 1: If
for some 
, then there exists a peaceful configuration where every 
sub-square contains a rook.Proof: I will provide an explicit configuration. Enumerate the unit squares with ordered pairs in a Cartesian fashion, such that the bottom left unit square has coordinates
and, for example, the square in the fourth column and second row (from the bottom) has coordinates 
. Now let 
and define 
. It is clear that if one places rooks on the squares with coordinates in 
then no sub-square will lack a rook, as desired.Lemma 2: If
for some , then there exists a peaceful configuration where every sub-square contains a rook.Proof: We proceed by reverse induction on
, with the result in Lemma 1 as the base case. Assume that for some 
, the result in Lemma 2 holds. Now consider a peaceful configuration on an 
board such that every sub-square contains a rook. Shift left the 
-coordinate of each ordered pair corresponding to a rook by 
(modulo 
) until there is a rook in the square with coordinate . Clearly the configuration is still peaceful and clearly every sub-square still contains a rook. Now just delete the first row and column, rooks and all. This new 
board clearly still satisfies the induction hypothesis so we are done.Lemma 3: Let
for some 
. Then in any peaceful configuration, there is an 
sub-square containing no rooks.Proof: Assume the contrary, and let us try to create such a peaceful configuration. Consider the
sub-square in the bottom-left corner. Tiling it by squares, we see it must contain 
rooks. Then the 
square in the top- right corner must contain 
rooks. But as the square in the bottom-right corner must also contain rooks, so the right-most columns all contain more than one rook, contradiction.The combination of these lemmas clearly implies the desired result.
August 2016
June 2016