Given an integer $n>1$. The board $n\times n$ is colored white and black in a chess-like manner. We call any non-empty set of different cells of the board as a figure. We call figures $F_1$ and $F_2$ similar, if $F_1$ can be obtained from $F_2$ by a rotation with respect to the center of the board by an angle multiple of $90^\circ$ and a parallel transfer. (Any figure is similar to itself.) We call a figure $F$ connected if for any cells $a,b\in F$ there is a sequence of cells $c_1,\ldots,c_m\in F$ such that $c_1 = a$, $c_m = b$, and also $c_i$ and $c_{i+1}$ have a common side for each $1\le i\le m - 1$. Find the largest possible value of $k$ such that for any connected figure $F$ consisting of $k$ cells, there are figures $F_1,F_2$ similar to $F$ such that $F_1$ has more white cells than black cells and $F_2$ has more black cells than white cells in it.
Problem
Source: Kazakhstan National Olympiad 2024 (9 grade), P2
Tags: combinatorics
21.03.2024 16:39
If I understand it correctly, here is my solution: If there are figures $F_1,F_2$ similar to $F$ such that $F_1$ has more white cells than black cells and $F_2$ has more black cells than white cells in it, then call $F$ as good. Every similar figure has same value for $|N_b-N_w|$ where $N_b,N_w$ are number of black and white cells. So for even $k$ there is connected figure $F$ with $N_b=N_w$ and so there are no figure $F_1$ which is similar to $F$ and $N_b \ neq N_w$. and so $F$ is not good. So $k$ is odd for good $F$ Case 1: $n$ is even. Take any connected figure $F$ with odd $k$ cells. Let we have $N_b>N_w$. Rotate this figure by $90^\circ$ to get similar figure $F_2$. Easy to prove that $N_{b2}=N_w, N_{w2}=N_b$, so $N_{w2}>N_{b2}$ and so $F$ is good. So for even $n$ answer is $n^2-1$ Case 2: $n$ is odd. If $k \geq 2n-1$ then build next figure: Select row and column, which contains central cell. Such cross contains $2n-1$ cells. Then select any $k-(2n-1)$ cells, such that $F$ is connected. Now we can see, that we can not make parallel transfer for $F$ to get similar figures. So all similar figures can be done only with rotation. But every such rotation does not change $N_b-N_w$ because every black cell after rotation goes to black cell, and every white to white. And so $F$ can not be good, because $N_b-N_w$ has same sign for similar figures. Now let $k \leq 2n-3$. Take any connected figure $F$ and let $N_b>N_w$ Call first and last rows and columns as borders. As $k \leq 2n-3$ then there is border, which has no common cells with figure $F$. Now make parallel transfer to move figure $F$ on one cell in direction of this border. Such move can be done, and every cell changes color, so for $F_2$ we have $N_b<N_w$ and so $F$ is good Answer: $n^2-1$ for even $n$ and $2n-3$ for odd $n$
21.03.2024 18:58
RagvaloD wrote: Call first and last rows and columns as borders. As $k \leq 2n-3$ then there is border, which has no common cells with figure $F$. Is it really that obvious? I mean this should've been the main part of the solution. .
31.05.2024 04:50
The answer is $n^2-1$ if $n$ is even and $2n-3$ if $n$ is odd. Case 1: $n$ is even Clearly $k=n^2$ does not work. Notice that $k=n^2-1$ does indeed work as rotating $90^{\circ}$ about the center changes the color of every cell. Case 2: $n$ is odd Notice that $k$ must be odd and rotating about the center does not change the color of any of the cells. It is sufficient to find the largest $k$ for which any figure consisting of $k$ cells can be shifted one unit in some direction. By considering an $L$-shape consisting of two walls of the grid we get that $k<2n-1$. Now we show that a figure that can not be shifted contains at least $2n-1$ cells. Consider the (non intersecting) outer boundary of the figure which must touch all four walls. Using a simple tax-cab distance argument we get that the perimeter of this outer shape is at least $4n$. By Picks Theorem the area of this figure is at least $2n-1$ concluding the proof.