| |
17 rooks are placed on an 8×8 chessboard. Prove that there are at least 3 rooks that do not threaten each other.
|

Since there are 17 rooks in 8 rows, at least one row contains at least 3 rooks. Let this be row A. Disregard row A in the following.
The remaining 7 rows house at least 17 - 8 = 9 rooks. The Pigeonhole principle implies the existence of a row with at least 2 rooks. Denote one of these rows B and remove it from further consideration.
There at at least 9 - 8 = 1 rooks in the remaining 6 rows. It follows there is at least one row with at least one rook. Denote one of these C.
Now, let RC be any rook in rwo C. Since row B contains more than 1 rook, there is a rook RB in a column different from that of RC so that the two do not threaten each other.
Since row A contains at least 3 rooks, there is a rook RA in columns different from those of RB and RC. So chosen rooks do not threaten each other.
(The problem is a simplification of Problem 1.4.5 from Mathematics as Problem Solving by A. Soifer.)

Copyright © 1996-2009 Alexander Bogomolny
|