Given is a positive integer $n$. There are $2n$ mutually non-attacking rooks placed on a grid $2n \times 2n$. The grid is splitted into two connected parts, symmetric with respect to the center of the grid. What is the largest number of rooks that could lie in the same part?
Problem
Source: ARO Regional stage 2022 9.3
Tags: combinatorics, Russia
Tintarn
05.03.2023 19:04
The answer is $2n-1$. It is easy to produce an example with $2n-1$ rooks as follows: Start with the decomposition cut along the main diagonal from top left to lower right. Give the upper left half of the diagonal to the upper right piece and the other half to the other piece. So we have a symmetric decomposition into two parts. Now we can just place the rooks on the diagonal upper right to the main diagonal (and the last rook on the lower left corner) so that $2n-1$ of the rooks are in the upper right piece.
On the other hand, it is not possible to have all $2n$ rooks in one piece. Indeed, it suffices to show that any decomposition misses at least one column or at least one row. But else there is a part of piece A in both the left and the right column and a part of piece B in both the upper and the lower row. Since both pieces are connected, there is a path inside the pieces going from left to right resp. top to down. But of course they must cross which is a contradiction.
sami1618
28.06.2024 23:17
Answer: $2n-1$ Construction: Below is a construction for $n=4$ which easily generalizes. [asy][asy] filldraw(((0,0)--(0,1)--(1,1)--(1,0)--cycle), grey); filldraw(((1,1)--(1,2)--(2,2)--(2,1)--cycle), grey); filldraw(((2,2)--(2,3)--(3,3)--(3,2)--cycle), grey); filldraw(((3,3)--(3,4)--(4,4)--(4,3)--cycle), grey); filldraw(((5,4)--(5,5)--(6,5)--(6,4)--cycle), grey); filldraw(((6,5)--(6,6)--(7,6)--(7,5)--cycle), grey); filldraw(((7,6)--(7,7)--(8,7)--(8,6)--cycle), grey); filldraw(((4,7)--(5,7)--(5,8)--(4,8)--cycle), grey); draw((0,1)--(1,1)--(1,2)--(2,2)--(2,3)--(3,3)--(3,4)--(5,4)--(5,5)--(6,5)--(6,6)--(7,6)--(7,7)--(8,7),red+linewidth(4)); add(grid(8,8)); [/asy][/asy] Bound: Notice that there must exist a rook in every row and column. Let the grid be split into two parts along a curve $C$ that intersects the boundary at $A$ and $B$ (not at the corners). Then $A$ and $B$ lie on opposite sides and thus there exist a full row or column to each side of $C$, finishing the proof.