Given a $6\times6$ chess board with $13$ marked squares, can you always place three mutually non-attacking rooks on the marked squares? If so, how can this be proven?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The squares of the board can be divided into six subsets, each one consisting of a NE-SW diagonal that wraps around the board if necessary. Mathematically, the $j$th subset ($0\le j\le5$) consists of those squares in the $r$th row and $c$th column such that $r-c\equiv j\pmod 6$. These subsets are pictured below.
Since there are 13 rooks and 6 such subsets, some subset must contain at least 3 rooks (by the pigeonhole principle). Those 3 rooks cannot attack one another.
(A similar argument with NW-SE diagonals shows that there must be at least two such subsets of 3 rooks, which overlap in at most 1 rook.)