3
$\begingroup$

$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.

$\endgroup$
  • 2
    $\begingroup$ A $5\times5$ square contains $16$ different $2\times2$ squares. At most 4 non-overlapping squares at a time, though. $\endgroup$ – Arthur May 17 '18 at 15:02
3
$\begingroup$

One of the rooks must be in the bottom row, e.g.

+--+--+--+--+--+
|  |  |  |  |  |
+--+--+--+--+--+
|  |  |  |  |  |
+--+--+--+--+--+
|  |  |  |  |  |
+--+--+--+--+--+
|  |  |  |  |  |
+--+--+--+--+--+
|  |  |R |  |  |
+--+--+--+--+--+

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:

+--+--+--+--+--+
|  |  |  |R |  |
+--+--+--+--+--+
|  |  |  |  |  |
+--+--+==+==+--+
|  |  :  |  :  |
+--+--+--+--+--+
|  |  :  |  :  |
+--+--+==+==+--+
|  |  |R |  |  |
+--+--+--+--+--+

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:

+--+--+==+==+--+
|  |  :  |  :  |
+--+--+--+--+--+
|  |  :  |  :  |
+--+--+==+==+--+
|  |  |  |  |  |
+--+--+--+--+--+
|  |  |  |R |  |
+--+--+--+--+--+
|  |  |R |  |  |
+--+--+--+--+--+
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This shows there are at least two $2 \times 2$ squares empty. I think my argument can be extended to show that if you consider the rooks on all the sides, but it would take some thought. $\endgroup$ – Ross Millikan May 17 '18 at 15:34
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.