Pawns and rooks are placed on a $2019\times 2019$ chessboard, with at most one piece on each of the $2019^2$ squares. A rook can see another rook if they are in the same row or column and all squares between them are empty. What is the maximal number $p$ for which $p$ pawns and $p+2019$ rooks can be placed on the chessboard in such a way that no two rooks can see each other?
Problem
Source: Benelux MO 2019 P2
Tags: combinatorics
ThE-dArK-lOrD
28.04.2019 18:07
For any row in the chessboard, if it contains $r$ rooks, it must contains at least $r-1$ pawns. Summing over all $2019$ rows, we get that there must be at least $p$ pawns, implying all equalities hold. This relation also holds if row is replaced by column. We then induct for $i=1,2,\dotsc ,1010$ that Quote: When considering only the $i$ highest rows, the number of rooks without any pawn or rook (the latter is actually included in the former) below it (i.e., in the same column) is at most $i$. The base case: if there is a pawn in the first row, the column that pawn lies in will contradicts the equality we proved. So there is no pawn and at most one rook in this row. Inductive step: Suppose there are $x$ pawns in the $(i+1)$th row, this row contains at most $x+1$ rooks. Using the inductive hypothesis, the number of rooks described is at most $i-x+(x+1)=i+1.\quad \square$ As a consequence of the above proposition, there can be at most $i$ rooks in the $i$th row. This relation also holds when we consider $1009$ lowest rows. Hence, the total number of rooks is at most $(1+2+\cdots +1010)+(1+2+\cdots +1009)=1010^2$. So, $p\leqslant 1010^2-2019=1009^2$. I'll leave the construction part to the reader.