7
$\begingroup$

Some rooks are placed on an $n\times n$ board. Each rook is attacked by at most one other rook, and every unoccupied cell is attacked by some rook. What is the smallest $k$ such that no matter how we set up the board, every $k\times k$ subboard contains at least one rook?

$k=\lfloor n/2\rfloor$ is too small, because we can take the board with a rook on each square of the main diagonal. In this board the bottom-left (or top-right) $\lfloor n/2\rfloor\times\lfloor n/2\rfloor$ subboard does not contain any rook. Is it true that every $(\lfloor n/2\rfloor+1)\times (\lfloor n/2\rfloor+1)$ subboard must contain some rook?

$\endgroup$
  • 1
    $\begingroup$ Usually a rook is not considered to attack its own square. For clarity, you should say that every unoccupied square is attacked by a rook. $\endgroup$ – bof Aug 18 '16 at 20:15
  • $\begingroup$ For $n=5$, it's easy to leave an open $3\times3$ subboard and satisfy the other conditions with $6$ rooks. $\endgroup$ – Barry Cipra Aug 18 '16 at 20:29
  • 1
    $\begingroup$ It's easy to place $4n$ rooks on a $3n\times3n$ chessboard so that each rook is attacked by exactly one other rook, every unoccupied square is attacked by at least two rooks, and there is a $2n\times2n$ subboard with no rooks. $\endgroup$ – bof Aug 18 '16 at 21:02
  • $\begingroup$ @Bof As I understand the question, we are looking for the worst possible placement of the rooks, such that we are guaranteed that ever $k$X$k$ subboard contains at least one rook. $\endgroup$ – Jens Aug 18 '16 at 21:05
  • $\begingroup$ Is it correctly understood that you are looking for the smallest $k$ which can be guaranteed given any board that fulfills your two first sentences? Or are you looking for the smallest $k$ possible, given an optimal board? $\endgroup$ – Jens Aug 18 '16 at 21:20
4
$\begingroup$

$\lfloor n/2 \rfloor + 1$ is not enough. As @bof stated, you can have $2n/3 \times 2n/3$ subboard without any rooks: take this empty subboard in the bottom left corner. For the $n/3$ rows above the subboard, starting from the top left corner, put $2$ rooks in each row in a staggered fashion, ending above the top right corner of the empty subboard. Do a similar thing with the $n/3$ columns to the right of the empty subboard. Then every square is attacked by a rook while this large subboard remains empty.

However, this turns out to be the worst case. That is, every $(\lfloor 2n/3 \rfloor +1) \times (\lfloor 2n/3 \rfloor +1)$ subboard must contain at least one rook.

To prove this, suppose we had an empty $k \times k $ subboard for some $k > 2n/3$. We first show that every row must have at least one rook.

If not, then there is a row with no rooks. Every square in this row must be attacked by some rook in the same column. Now consider the squares of this row that are in the same $k$ columns as the empty $k \times k $ subboard. The attacking rooks must therefore be in the $n-k $ rows outside this empty subboard. Since each row can have at most $2$ rooks in it, there are at most $2 (n-k) < k $ attacking rooks here, so some square in the empty row is left unattacked. This gives a contradiction.

Hence there is at least one rook in every row. By symmetry, there is also at least one rook in every column. Of course, there can be at most $2$ rooks in any column. Let $r $ be the number of rows with $2$ rooks. The total number of rooks is then $n+r $. By double-counting, there are also $r $ columns with two rooks in them.

Now these $n+r $ rooks cannot be in the $k \times k $ subboard. Hence they are either in the $n-k $ rows outside the subboard, or the $n-k $ columns outside the subboard.

The $n-k $ rows can have at most $\max (n-k, r) $ rows among them with $2$ rooks, and hence contain at most $n-k + \max (n-k, r) $ rooks in total. By symmetry, the same is true of the $n-k $ columns. Hence the total number of rooks is at most $$ 2 (n-k) + 2 \max (n-k, r) \le 2 (n-k) + n-k + r = 3 (n-k) +r. $$ (Note that this would count twice any rook that is in both a different row and column from the subboard, but since we are getting an upper bound, it is okay to overcount some rooks.)

However, we know there are $n+r $ rooks. Thus $n+r \le 3 (n-k) +r $, which simplifies to $k \le 2n/3$, a contradiction.

Thus if $k > 2n/3$, every $k \times k $ subboard must contain at least one rook.

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