There are (2n - 1) rooks on a (2n - 1)×(2n - 1) board placed so that none of them threatens another. Prove that any n×n square contains at least one rook.

Solution

Assuming an n×n square is void of the rooks, there remain n - 1 vertical and n - 1 horizontal lines to house (2n - 1) rooks. But each of these 2n - 2 lines may carry only one rook. By the Pigeonhole principle this is impossible.