Non-attacking rooks

Given an $n \times n$ chess board and $2n+1$ rooks placed on it, prove that we will always be able to choose 3 rooks who can't attack each other.

Solution

Partition the board into $n$ groups in a "broken diagonal" pattern. That is, cell $(i,j)$ belongs to group $i+nj \mod n$. Two cells in the same group can't attack each other (easily shown either by diagonal argument or modular analysis).

Because there are $2n+1$ rooks, then there are 3 rooks that sit on the same group.