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

Solution


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

Copyright © 1996-2018 Alexander Bogomolny

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 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.

a chessboard wrap into a cylinder

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 41 = 4×10 + 1 sitting on 10 such chains. It follows that at least one chain contains at least 5 rooks. However, the rooks on a chain to do not threaten each other.

References

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

Related material
Read more...

  • Chinese Remainder Theorem
  • Pigeonhole in a Chessboard
  • Pigeonhole in Concurrent Cuts
  • Monochromatic Rectangle in a 2-coloring of the Plane
  • Polynomial and Integer Division
  • Power of three that ends with 001
  • Pigeonhole Principle (subsets)
  • Pigeonhole in Integer Differences
  • Four Numbers, Six Differences, GCD of the Products

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

    Copyright © 1996-2018 Alexander Bogomolny

    71546907