All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
Rook Placement (Posted on 2015-09-21) Difficulty: 3 of 5
We place 41 rooks on a 10 x 10 chessboard. Prove that one can choose five of them that do not attack each other.

*** Two rooks "attack" each other if they are in the same row or column of the chessboard.

Source: A problem appearing in Colorado Mathematical Olympiad.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Detailed solution (SPOILER) | Comment 1 of 5

     

  1. Since we have 41 rooks in 10 rows and 41=10*4+1 there must be at least one row with at least 5 rooks.  Call this row A  and remove it.

  2. Now we have at least 31 rooks in 9 rows and 31=10*3+1 there must be at least one row with at least 4 rooks.  Call this row B  and remove it.

  3. Now we have at least 21 rooks in 8 rows and 21=10*2+1 there must be at least one row with at least 3 rooks.  Call this row C  and remove it.

  4. Now we have at least 11 rooks in 7 rows and 11=10*1+1 there must be at least one row with at least 2 rooks.  Call this row D  and remove it.

  5. Now we have at least 1 rooks in 6 rows and 31=10*3+1 there must be at least one row with at least 1 rooks.  Call this row E  and remove it.

  6. The rook in E is a part of the “non attacking “ team

  7. Compare the row with 1 rook and the row with 2 rooks. There must be a rook in the second row which doesn't share a column with the sole rook in the first row. Thus, these two rooks cannot attack each other. Keep these two rooks in mind.

  8.  Moving on to the third row, which has 3 rooks, there must be a rook in this row which doesn't share a column with either of the two rooks we previously discussed, the sole rook in the first row and the rook in the second row. As a result, these three rooks cannot attack each other.

  9.  We use this same tactic on the fourth row, which has 4 rooks, to show that there must also be such a rook in this row, and our group of pacifist rooks has grown to 4.

  10. Finally, there must be a rook in the fifth row (5 rooks in this one), which doesn't share a column with any of the rooks in our group of 4 pacifist rooks.

  11. Thus, we have shown that there must be 5 rooks that do not attack each other in any arrangement of 41 rooks on a 10x10 chessboard.

Clearly it does not work with 40. (find a counterexample and post it!)

 



Edited on September 26, 2015, 4:55 pm
  Posted by Ady TZIDON on 2015-09-26 06:10:45

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information