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

 Rook Placement (Posted on 2015-09-21)
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.

 See The Solution Submitted by K Sengupta Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 the “official” solution - spoiler | Comment 3 of 5 |

Since there complaints about the “official” solution (too long, illegible) and I cannot edit it-

I will relate the method (pigeonhole principle ) in details :

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!)

 Posted by Ady TZIDON on 2015-09-26 16:45:00

 Search: Search body:
Forums (0)