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.
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.
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.
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.
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.
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.
The rook in E is a part of the “non attacking “ team
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.
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.
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.
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.
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
Detailed solution (SPOILER)
