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 later book, the problem is treated again (7.6) but now the solution is hard to find faults with.
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.
For a solution, fold a 10×10 board into a cylinder and then color the square diagonaly into 10 colors. This splits the board into 1×10 monochromatic chains of squares.There are
- A. Soifer, Mathematics as Problem Solving, Springer, 2009 (2nd, expanded edition)
- A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)