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 there complaints about the “official” solution (too
long, illegible) and I cannot edit it-
I will relate the method (pigeonhole principle ) in details
:
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!)
the “official” solution - spoiler
