Thread: Rooks on a checkboard

For every , determine the greatest number of rooks that can be placed on a checkerboard so that the following property is satisfied: if a rook is attacked by two others, then all three are on the same line.

Originally Posted by atreyyu

For every , determine the greatest number of rooks that can be placed on a checkerboard so that the following property is satisfied: if a rook is attacked by two others, then all three are on the same line.

I will outline a solution with some parts left for you to fill in.

The number of rooks that can be placed is 2n-2. We need to show, first, that 2n-2 rooks can be placed on an n by n chessboard subject to the required constraint; second, that no larger number can be placed. I leave the first part to you.

To show that no more than 2n-2 rooks can be placed, assume the contrary; i.e., for some n, more than 2n-2 rooks can be placed on an n by n chessboard such that no rook shares a row and column with two other rooks. Choose the least such n. It is clear that we can't place more than 2 rooks on a 2 by 2 chessboard without violating the constraint, so n is greater than 2.

Suppose we have our rooks on the chessboard-- i.e., consider a suitable configuration of more than 2n-2 rooks.

We claim that some row has at most 1 rook in it. If not, there must be at least 2 rooks in every row. Each such 2 rooks eliminate 2 columns from the places where we can place rooks, so there are 2n columns where we can't place a rook. This can't be, since there are only n columns. So, as claimed, there is a row with at most 1 rook in it-- say row i.

Similarly, there is a column with at most 1 rook in it, say column j. Remove row i and column j from the chessboard. What remains is an n-1 by n-1 chessboard with at least 2n-1-2 = 2(n-1)-1 rooks, such that if any rook is attacked by 2 others, then all 3 are on the same row or column. Since 2(n-1)-1 > 2(n-1)-2, this violates our assumption that n is minimal. This contradiction shows that no such configuration is possible.