Threatened Rooks

Find the largest number of rooks that can be placed in a 3000 × 3000 3000 \times 3000 chessboard in such a way that each rook is threatened by no more than one rook.

Details and Assumptions:

  • Rooks can attack in any range but can only attack in a horizontal or vertical direction.
  • A rook is considered to be "threatened" if another rook can attack it.


The answer is 4000.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Michael Ng
Oct 28, 2014

A great problem! Here is my solution:

Every rook must be paired with another one, and only one, which attack each other. This is because if there is a rook unpaired (not attacking) then we are wasting a space for another rook.

Now notice that each of these pairs eliminates three 'lines' of squares; either two horizontal and one vertical or vice versa; in which no more rooks can be placed. So every two rooks corresponds to three lines.

There are 6000 6000 lines on the chessboard, hence the maximum should be 4000 4000 . However this is only a necessary condition so we must show that it can be done. If we try spiralling pairs of rooks (see image) then this gives 4000 4000 rooks as required, hence the answer is indeed 4000 \boxed{4000} .

How to place rooks How to place rooks

My proof that 4 n 4n is the largest number of rooks that can be placed in a 3 n × 3 n 3n\times3n chessboard.

Divide the rooks into three types. And let there be a a rooks that attack no other rook, b b rooks that attack other rooks horizontally, and c c rooks that attack other rooks vertically.

In any good arrangement the a a rooks of the first type will cover a a rows and a a columns, b b rooks of the second type occupy c c columns and c 2 \frac{c}{2} rows. Summing them, the number of occupied rows and columns is 2 a + 3 2 b + 3 2 c 2a+\frac{3}{2}b+\frac{3}{2}c .

Note that there exists 6 n 6n rows and columns. So 6 n 2 a + 3 2 b + 3 2 c 3 2 ( a + b + c ) 6n\geq 2a +\frac{3}{2}b+\frac{3}{2}c \geq \frac{3}{2}(a+b+c)

This leads to a + b + c 4 n a+b+c\leq 4n , as desired.

Sean Ty - 6 years, 7 months ago

We can make this configuration of rooks just by putting 4 rooks in 3x3 grid and then putting 1000 of them on a diagonal of the square.

Robert Szafarczyk - 3 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...