Maths Olympiad Prep

Library / /2 of 9

Combinatorics Difficulty 7.0 National Olympiad Prove it Benelux Mathematical Olympiad

Problem:

Pawns and rooks are placed on a 2019×20192019 \times 2019 chessboard, with at most one piece on each of the 201922019^{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 pp for which pp pawns and p+2019p+2019 rooks can be placed on the chessboard in such a way that no two rooks can see each other?

Solution

Solution:

Answer: the maximal pp equals 100921009^{2}.
Write n=2019n=2019 and k=1009k=1009; then n=2k+1n=2k+1. We first show that we can place k2k^{2} pawns and n+k2n+k^{2} rooks. Each cell of the chess board has coordinates (x,y)(x, y) with 1x,yn1 \leqslant x, y \leqslant n. We colour each cell black or white depending on whether x+yx+y is even or odd.
Let AA be cell (1,k+1)(1, k+1), BB be cell (k+1,1)(k+1,1), CC be cell (2k+1,k+1)(2k+1, k+1) and DD be cell (k+1,2k+1)(k+1,2k+1), and consider the skew square ABCDABCD. We place rooks on the cells of this square which have the same colour as AA, and we place pawns on the other cells of this square. In this way, no rook can see another rook. Now we have placed p=k2p=k^{2} pawns and (k+1)2=k2+(2k+1)=p+n(k+1)^{2}=k^{2}+(2k+1)=p+n rooks.

Now we show that we can not place more pawns. Observe that in every row the number of rooks exceeds the number of pawns by at most 11, since there has to be a pawn between every two neighbouring rooks. So the total number of rooks exceeds the number of pawns by at most nn. On the other hand we are to place pp pawns and p+np+n rooks, so the number of rooks in every row exceeds the number of pawns by exactly 11. This means that the rooks and pawns alternate, with rooks at the two ends. For the columns the same holds.

Consider the \ell-th row. Let aa be the number of pawns in this row and let bb be the number of pawns above the \ell-th row. For all these pawns, a rook must be somewhere above it. Counting the rooks directly above these a+ba+b pawns, we conclude that there must be at least a+ba+b rooks in the first 1\ell-1 rows. In every row the number of rooks exceeds the number of pawns by 11, so in these first 1\ell-1 rows we have at least a+b(1)a+b-(\ell-1) pawns. So ba+b(1)b \geqslant a+b-(\ell-1), yielding a1a \leqslant \ell-1. We conclude that the \ell-th row contains at most 1\ell-1 pawns. The same holds for the \ell-th row counted from below (row (n+1)(n+1)-\ell): also in this row, there are at most 1\ell-1 pawns. As n=2k+1n=2k+1, the maximal number pp is
=1k(1)+=1k+1(1)=k+212k(k1)=k+k(k1)=k2 \sum_{\ell=1}^{k}(\ell-1)+\sum_{\ell=1}^{k+1}(\ell-1)=k+2 \cdot \frac{1}{2}k(k-1)=k+k(k-1)=k^{2}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.