$5$ rooks are placed on a $5$ by $5$ chessboard in such a way that no two rooks attack each other. How can I prove that there exists a $2$ by $2$ square on the chessboard which does not contain any of the rooks?
(A rook is defined to attack another rook if they are in the same row or column.)
I've noticed that a $5$ by $5$ chessboard can contain four $2$ by $2$ squares, but that doesn't prove anything.
On
There are 16 2x2 squares on a 5x5 chess board. A single rook placed in the corner sits on exactly 1 2x2 square. A rook on the edge of the board (not a corner) sits on exactly 2 2x2 squares. A rook in the middle of the board sits on 4 2x2 squares. You are guaranteed to have rooks on the top edge, the bottom edge, the left edge, and the right edge (possibly the same rook on multiple edges if it is in the corner). If we maximize, we can get 3 rooks in the middle of the board, but we then need rooks in the corners. If 3 rooks are in the middle of the board and two in the corners, we cover $3\cdot 4 + 2\cdot 1 = 14$ 2x2 squares. If there are two in the middle of the board and we avoid the corners, we cover $2\cdot 4 + 3\cdot 2 = 14$ 2x2 squares. And if we have fewer than two in the center or start allowing the rooks to be in the corner, we get fewer 2x2 squares covered. So, by the Pigeonhole Principle, at least 1 2x2 square will be uncovered.
On
Let the squares be in a grid $(1,1)$ lower left to $(5,5)$ upper right. Let us try to place the first rook at $(1,1)$ and try to place three rooks as close to each other to avoid a $2$x$2$ empty space. We can have a rook in $(1,1)$, $(3,2)$, $(2,3)$. This will leave two square spaces open from $(4,1)$ to $(5,2)$ and from $(1,4)$ to $(2,5)$.
One of the rooks must be in the bottom row, e.g.
Focus on the column this rook is in and one of the neighboring columns. If the neighboring rook is in the top or next to top row, there is a $2 \times 2$ empty square on the second and third rows, such as the following case:
Otherwise, the neighboring rook is in the second or third row and there is a $2 \times 2$ square in the fourth and fifth rows, such as the following case: