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
Source: A problem appearing in Colorado Mathematical Olympiad.
(In reply to the “official” solution - spoiler
by Ady TZIDON)
Thanks, Ady, for the clear and witty editing of the "official" solution.
The counter-example that you requested is having all of the rooks in 4 rows (or having them all in 4 columns). With 40 rooks so placed, no set of 5 rooks can be found that do not attack each other. By the pigeonhole principle, if they are all in 4 rows, then at least two of them must be in the same row.