What is the maximum number of rooks one can place on a chessboard such that any rook attacks exactly two other rooks? (We say that two rooks attack each other if they are on the same line or on the same column and between them there are no other rooks.) Alexandru Mihalcu
Problem
Source: 2018 Romania JBMO TST 1.4
Tags: combinatorics, Chessboard
bin_sherlo
23.09.2023 21:55
Answer:$16$.
$RRWWWWWW$
$RRWWWWWW$
$WWRRWWWW$
$WWRRWWWW$
$WWWWRRWW$
$WWWWRRWW$
$WWWWWWRR$
$WWWWWWRR$
Proof:Assume that there exist more than $16$ rooks. We can change the places of columns and rows. There exists a row such that there are atleast $3$ rooks. Let's place that row to the highest row and place the rooks to the first $3$ columns.
$RRR-----$
$.$
$.$
$.$
$--------$
There can't exist a rook in the first $3$ columns and in the first row other than these $3$. So there should be atleast $14$ rooks in a $7x5$ board. $i)$If there exist a row which there are atleast $3$ rooks: Similarily take them to the first $3$ column and first row.
$RRR--$
$.$
$.$
$.$
$-----$
There can't exist a rook in the first $3$ column and in the first row other than these $3$. So there should be atleast $11$ rooks in a $6x2$ which is not possible. $ii)$If there exist $2$ rooks in every row: There exist a column which there are $3$ rooks.
$R----$
$R----$
$R----$
$...$
Similarily there can't exist a rook in the first $3$ row and in the first column other than these $3$. So there should be atleast $11$ rooks in a $4x4$ board. There exists a row which there are $3$ rooks. There can't exist a rook in the first $3$ column and in the first row other than these $3$. So there should be atleast $8$ rooks in a $3x1$ board which is impossible.