17 rooks are placed on an 8×8 chessboard. Prove that there are at least 3 rooks that do not threaten each other.
17 rooks are placed on an 8×8 chessboard. Prove that there are at least 3 rooks that do not threaten each other.
Solution 1
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 row 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 a book by A. Soifer. In that book, the problem is treated twice. Both solutions although evolving from simple ideas are somewhat complicated to my liking.
In the author's The original (not simplified) problem asks to prove that if 41 rooks have been placed on a 10×10 board then there are at least 5 of them that do not threaten each other.
