|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2017 Alexander Bogomolny### 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 R_{C} be any rook in row C. Since row B contains more than 1 rook, there is a rook R_{B} in a column different from that of R_{C} so that the two do not threaten each other.

Since row A contains at least 3 rooks, there is a rook R_{A} in columns different from those of R_{B} and R_{C}. 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### References

- A. Soifer,
*Mathematics as Problem Solving*, Springer, 2009 (2nd, expanded edition) - A. Soifer,
*Geometric Etudes in Combinatorial Mathematics*, Springer, 2010 (2nd, expanded edition)

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2017 Alexander Bogomolny62681824 |