Find the largest number of rooks that can be placed in a 3 0 0 0 × 3 0 0 0 chessboard in such a way that each rook is threatened by no more than one rook.
Details and Assumptions:
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.
My proof that 4 n is the largest number of rooks that can be placed in a 3 n × 3 n chessboard.
Divide the rooks into three types. And let there be a rooks that attack no other rook, b rooks that attack other rooks horizontally, and c rooks that attack other rooks vertically.
In any good arrangement the a rooks of the first type will cover a rows and a columns, b rooks of the second type occupy c columns and 2 c rows. Summing them, the number of occupied rows and columns is 2 a + 2 3 b + 2 3 c .
Note that there exists 6 n rows and columns. So 6 n ≥ 2 a + 2 3 b + 2 3 c ≥ 2 3 ( a + b + c )
This leads to a + b + c ≤ 4 n , as desired.
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.
Problem Loading...
Note Loading...
Set Loading...
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 6 0 0 0 lines on the chessboard, hence the maximum should be 4 0 0 0 . 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 4 0 0 0 rooks as required, hence the answer is indeed 4 0 0 0 .
How to place rooks