Let $n \geq 3$ be an odd number and suppose that each square in a $n \times n$ chessboard is colored either black or white. Two squares are considered adjacent if they are of the same color and share a common vertex and two squares $a,b$ are considered connected if there exists a sequence of squares $c_1,\ldots,c_k$ with $c_1 = a, c_k = b$ such that $c_i, c_{i+1}$ are adjacent for $i=1,2,\ldots,k-1$. Find the maximal number $M$ such that there exists a coloring admitting $M$ pairwise disconnected squares.
Problem
Source: China Mathematical Olympiad 2018 Q5
Tags: combinatorics
Skravin
16.11.2017 09:15
Ah I thought wrong so that common line would make no vertex come out... easy fact but forgets all the time
arvindf232
16.11.2017 16:17
Remarks: The central idea is to count in a nature similar to Euler’s formula, inductively expressing components as other quantities. Afterwards, a tedious classification on types of objects will give the solution. It is obvious that in any particular colouring, the maximal $M$ is simply the number of maximally connected components. Now, obtain a graph $G$ by joining any two adjacent-by-edge square. Two diagonally adjacent square is only joint if there are precisely 2 black and 2 white squares in this local 2*2 square. This is done so that the graph is planar. In $G$, M can be related by $ M = Cells - Edge + Faces $ Which can be obtained with simple induction similar to Euler’s formula Each face can be represented and considered with a minimal cycle: A set of square forming a cycle but no subset of this cycle does. It remains to count and classify all edges and cycles. A primal central square is a 2*2 sub-square of the n*n square board. Thus there are $(n-1)^2$ Primal squares. A primal side rectangle is a two connected cells, both lying on a certain side of the n*n square. There are $4(n-1)$ primal side rectangle. For any edge, we say a primal object witness this edge if it is contained in within the primal side/square. A primal central square is identical if the four underlying squares are of the same colour A primal side rectangle is identical if the two underlying squares are of the same colour It is easy to check the following holds (1) Each edge is witnessed by at most 2 primal objects (2) A non-identical primal central square witness 2 edges (3) An identical primal central square witness 4 edges (4) A primal side rectangle witness 1 edges if identical, none otherwise Denote the number of non-identical, identical primal central squares by $C_2,C_4$. Denote the number of non-identical , identical primal side rectangle by $S_0,S_1$ respectivelt. Then (1) to (4) shows: $ Edges = \frac{2 C_2 +4 C_4 + S_1}{2} = (n-1)^2 + C_4 + \frac{1}{2} S_1$ Next, we classify the cycles: We say the boundary squares to be the squares from the 4 sides of the square (i.e. the 4(n-1) squares of first/last row/column) A cycle is non-encasing if no squares of opposite colour is trapped inside the cycle. An encasing cycle is binding if it contains boundary squares. A cycle is proper if it is encasing and not binding. Denote the numbers of binding, non-encasing, proper cycles by $F_B,F_{NE},F_P$. Then (5) $Total number of cycles = F_B + F_{NE} + F_P$ It is easy to see (6) If a cycle is non-encasing, then it must be a 4-square 4-edge cycle With proper repesentitives/invariants/counting it naturally follows that (7) $F_{NE} \leq C_4$ Essentially : identical primal central squares cancel any actions of non-encasing cycle. Similarly: (8) If a cycle is non-binding, then it must contain 3 square on the boundary squares This naturally witness two primal side rectangle each being identical, os (9) $2F_S \leq S_1$ Essentially: Identical side rectangle cancels any actions of binding cycle. Lastly: (10) A proper cycle spans at least 9 squares in area And self-evidently: (11) There can be at most $( \frac {n-3}{2} )^2$ proper cycles So $M = Cells - Edge + Faces$ $ \leq n^2 - (n-1)^2 - C_4 - \frac{1}{2} S_1 + C_4 - \frac{1}{2} S_1 + ( \frac {n-3}{2} )^2 $ $= (2n-1) + (\frac{n-3}{2})^2$ $= (\frac{n+1}{2})^2 + 1$ as expected Construction is trivially taking squares with odd coordinates being black and others white.
ltf0501
22.11.2017 10:30
If we color board as a chessboard, I think your edges is wrong. Since 2*2 with diagonal same color won't be re-computed.
vsathiam
25.12.2017 06:38
Wait lol here is much simpler solution: We claim for a 2k+1X 2k+1 grid, maximal working M is $(k+1)^2$ For this, take (i,j) black for i and j both odd, (the rest are white) and they will form our disjoint M set. To show this is maximal, note that each disconnected square must not share a vertex with another disconnected square. Since there are $(2k+2)^2$ = 4*$(k+1)^2$ vertices on the grid, more than $(k+1)^2$ would mean that at least two disjoint squares share a common vertex, contradiction.
McTeague
23.04.2018 00:14
vsathiam wrote: To show this is maximal, note that each disconnected square must not share a vertex with another disconnected square. Since there are $(2k+2)^2$ = 4*$(k+1)^2$ vertices on the grid, more than $(k+1)^2$ would mean that at least two disjoint squares share a common vertex, contradiction. Since a black connected component can share a vertex somewhere with a white connected component, doesn't your argument only show that there are at most $(k+1)^2$ distinct components of a single color? (So at most $2(k+1)^2$ distinct components altogether?) Also, since any vertex on the perimeter of the board cannot attain $4$ incident components, I think that that would imply that $(k+1)^2$ would have to be a strict upper bound without equality ever being possible, which goes against the fact that you were able to present an example with exactly $(k+1)^2$ distinct components. (?)
McTeague
01.05.2018 20:16
I still don't see how the vertex argument gives the bound. Anyway, I think that I may have another approach that works, but I suppose that there is a chance for errors. I used red and blue instead. As noted above, the problem is equivalent to showing that there can be at most $(n+1)^2 + 1$ disjoint maximal monochromatic components in a $(2n+1) \times (2n+1)$ board. For brevity, I will just refer to these as "components". More generally, we prove that for $m, n \ge 1$, a $(2m+1) \times (2n+1)$ board can have at most $(m+1)(n+1)$ components when there is a corner square whose color matches the color of at least one of its cardinal neighbors, e.g. when some corner of the board looks as on the left below. Call this a type $A$ configuration. Otherwise, the board can have at most $(m+1)(n+1) + 1$ components, e.g. when each corner looks as on the right below (call this latter type a $B$ configuration):
If $Z$ is the number of total components and $Y$ is the number of components present in the bottom $2m-1$ rows, then let $X = Z - Y$, i.e. the number of components that are added to the count by the first two rows. Lemma 1: $X \le b_1^{(1)} + \left \lceil \frac{b_2}{2} \right \rceil$.
The first row alone has $b_1^{(1)} + b_1^{(2)}$ components. However, all of the $b_1^{(2)}$ components not wholly contained in the first row also appear in the second row, so we can write this upper bound on the count as $b_1^{(1)} + b_2$. Finally, any two runs of consecutive monochromatic cells that are edge-adjacent in the second row must be different colors, so that one of them is adjacent to a cell in the third row, and therefore not counted by $X$ (see the picture below for an example of the second and third rows in this case). So for any two components that are edge-adjacent in the second row, at least one is not counted by $X$, i.e. we can subtract $\left\lfloor \frac{b_2}{2} \right\rfloor$ from the count to get: $X \le b_1^{(1)} + b_2 - \left\lfloor \frac{b_2}{2} \right\rfloor = b_1^{(1)} + \left \lceil \frac{b_2}{2} \right \rceil$.
[asy][asy]size(6cm);
defaultpen(linewidth(1.5));
path p = (1,0)--(0,0)--(0,1)--(1,1)--(1,0);
path q = (0,0)--(1,0);
path r = (0,0)--(0,1);
fill((0,0)--(0,1)--(1,1)--(1,0)--cycle,lightred);
fill((1,0)--(1,1)--(2,1)--(2,0)--cycle,lightred);
fill((1,-1)--(1,0)--(2,0)--(2,-1)--cycle,lightblue);
fill((2,0)--(2,1)--(3,1)--(3,0)--cycle,lightblue);
fill((3,0)--(3,1)--(4,1)--(4,0)--cycle,lightblue);
draw(p, black);
draw(shift(1,0) * p, black);
draw(shift(2,0) * p, black);
draw(shift(3,0) * p, black);
draw(shift(1,-1) * p, black);
draw(shift(-1,0) * q, black);
draw(shift(-1,1) * q, black);
draw(shift(4,0) * q, black);
draw(shift(4,1) * q, black);
draw((2.6,-0.1)--(2.1,-0.7),BeginArrow);
[/asy][/asy]
Lemma 2: $b_2 \le 2n + 3 - 2b_1^{(1)}$.
Roughly speaking, the intuition here is that if we begin with the $2n+1$ cells of the second row, we can count $b_2$ by subtracting off cells of the row which appear as the second, third, fourth,... cells in some consecutive monochromatic run. Any component of the first row which is wholly contained in the first row (i.e. counted by $b_1^{(1)}$) is usually one cell above or diagonally above its own set of $\ge 3$ cells of the same component in row $2$, so most of the time we can subtract $2$ from the $2n+1$ for each of the $b_1^{(1)}$ components, giving roughly $(2n+1) - 2b_1^{(1)}$.
The only issue here is when there is a component of size $1$ wholly contained in the first row which is in the leftmost or rightmost cell of the row. If instead the component is at least $3$ cells long, then we can subtract the first two cells below from the count and only count the third, as in this diagram:
[asy][asy]size(6cm);
defaultpen(linewidth(1.5));
path p = (1,0)--(0,0)--(0,1)--(1,1)--(1,0);
path q = (0,0)--(1,0);
path r = (0,0)--(0,1);
path s = (0.2,-0.8)--(0.8,-0.2);
path t = (0.2,-0.2)--(0.8,-0.8);
fill((0,0)--(0,1)--(1,1)--(1,0)--cycle,lightred);
fill((1,0)--(1,1)--(2,1)--(2,0)--cycle,lightred);
fill((2,0)--(2,1)--(3,1)--(3,0)--cycle,lightred);
fill((0,-1)--(0,0)--(1,0)--(1,-1)--cycle,lightblue);
fill((1,-1)--(1,0)--(2,0)--(2,-1)--cycle,lightblue);
fill((2,-1)--(2,0)--(3,0)--(3,-1)--cycle,lightblue);
draw(p, black);
draw(shift(1,0) * p, black);
draw(shift(2,0) * p, black);
draw(shift(1,-1) * p, black);
draw(shift(0,-1) * p, black);
draw(shift(2,-1) * p, black);
draw(shift(-1,0) * q, black);
draw(shift(-1,1) * q, black);
draw(shift(3,0) * q, black);
draw(shift(3,1) * q, black);
draw(s, black);
draw(t, black);
draw(shift(1,0) * s, black);
draw(shift(1,0) * t, black);
[/asy][/asy]
The analysis for components contained wholly in the first row of length $1$ or $2$ is a little trickier. For sets of components that are in a succession, separated by single cells of the opposite color, we can always subtract an amortized $2$ cells each if the set of components does not end at the first or last cell of the row. This is difficult to explain but best seen with pictures:
[asy][asy]size(6cm);
defaultpen(linewidth(1.5));
path p = (1,0)--(0,0)--(0,1)--(1,1)--(1,0);
path q = (0,0)--(1,0);
path r = (0,0)--(0,1);
path s = (0.2,-0.8)--(0.8,-0.2);
path t = (0.2,-0.2)--(0.8,-0.8);
for (int i = -1; i < 7; i+=2) {
fill((i,0)--(i,1)--(i+1,1)--(i+1,0)--cycle, lightblue);
}
for (int i = 0; i < 8; i+=2) {
fill((i,0)--(i,1)--(i+1,1)--(i+1,0)--cycle, lightred);
}
for (int i = -1; i < 8; ++i) {
fill((i,-1)--(i,0)--(i+1,0)--(i+1,-1)--cycle, lightblue);
}
fill((7,0)--(7,1)--(8,1)--(8,0)--cycle, lightred);
for (int i = -1; i < 8; ++i) {
draw(shift(i,0) * p, black);
draw(shift(i,-1) * p, black);
}
for (int i = -1; i < 7; ++i) {
draw(shift(i,0) * s, black);
draw(shift(i,0) * t, black);
}
draw((7.5,-1.2)--(7.5,-2.2), BeginArrow);
[/asy][/asy]
Here, this set of four components of length $\le 2$ each, each "subtract" the blue squares diagonally left and below and also directly below, leaving the indicated blue square to count for the entire single blue component. This idea carries over in general, with the only exception being when there is a single-cell component on the far left or far right of the first row. In this case, these each only subtract $1$ from the count rather than $2$, so the bound is $b_2 \le 2n+1 - (2b_1^{(1)}-2) = 2n+3 - 2b_1^{(1)}$.
Notice that in the proofs of the two lemmas, there is room for slight improvement on the inequalities in special cases, which we will take advantage of. To complete the induction, first orient the board so that if it is type $A$, the upper left corner square and its right neighbor are the same color, WLOG with width $2n+1$. If it is of type $B$, orient it so that the length is more than $3$. Let $M$ denote the whole $(2m+1) \times (2n+1)$ board and let $M'$ denote the board consisting of the bottom $2m-1$ rows. To complete the induction, we now prove the four possible cases (all short proofs):
Since the board is oriented so that the top leftmost cell and its right neighbor are the same color, we can strengthen the result in lemma $2$ to $b_2 \le 2n+2-2b_1^{(1)}$. Applying lemma $1$, $X \le n+1$. By the IH, $M'$ has at most $m(n+1)$ components, for a total of at most $(m+1)(n+1)$ in $M$.
Plugging in the bound from lemma $2$ into lemma $1$ directly, we get that $X \le n+2$. By the IH, $M'$ has at most $m(n+1)$ components, for a total of at most $(m+1)(n+1) + 1$ in $M$.
Since $M'$ is type $B$, the third row of $M$ begins and ends with a blue and a red square each. Thus, if the first and last squares of the second row are not part of a single consecutive monochromatic run, we can strengthen the bound in lemma $1$ to:
\begin{align*}
X &\le b_1^{(1)} + b_1^{(2)} + b_2 - b_1^{(2)} - \left(\left\lfloor \frac{b_2-2}{2} \right\rfloor + 2 \right) \\
&= b_1^{(1)} + \left\lceil \frac{b_2}{2} \right\rceil - 1
\end{align*}Furthermore, as in the first case, since $M$ is of type $A$, we can strengthen lemma $2$ to $b_2 \le 2n+2-2b_1^{(1)}$. Taken together, these imply that $X \le n$.
If the first and last squares of the second row are part of a single consecutive monochromatic run, then the second row is one single color, WLOG blue. Since $M$ has two cells of the same color in the leftmost two squares and any blue cell will be part of the second row's component, there can be at most $n$ new components from the first row. Since $M'$ is type $B$ and therefore has its two leftmost squares different colors, the blue second row is not counted in $X$ and so $X \le n$.
So in either case, the top two rows contribute at most $n$ new components. By the IH, $M'$ has at most $m(n+1) + 1$ components, for a total of at most $(m+1)(n+1)$ in $M$.
Through an analysis similar to that in the third case, we get that either the second row is all one color, so that $X \le n+1$ or we improve lemma $1$ to $X \le b_1^{(1)} + \left\lceil \frac{b_2}{2} \right \rceil - 1$, which also leads to $X \le n+1$ by using lemma $2$. By the IH, $M'$ has at most $m(n+1)+1$ components, for a total of at most $(m+1)(n+1)+1$ in $M$.
When inducting down from $M$ of type $A$, we wanted the upper left corner to have two squares of the same color, which means that we could have oriented the board to a height of $3$ ($m=1$) and attempted to induct down to $m = 0$, which is bad. To avoid this, we can prove the main result for $3 \times (2n+1)$ boards on its own (by induction on $n$ -- the case work is a little annoying but not too long or arduous). Alternatively, we could include it as an inductive step above and only have to apply the inductive step for $3 \times (2n+1)$ boards of the following form (which seemed to cut the casework down by about $2/3$):
[asy][asy]size(4cm);
defaultpen(linewidth(1.5));
path p = (1,0)--(0,0)--(0,1)--(1,1)--(1,0);
path q = (0,0)--(1,0);
fill((0,0)--(0,1)--(1,1)--(1,0)--cycle, lightblue);
fill((0,2)--(0,3)--(1,3)--(1,2)--cycle, lightblue);
fill((1,2)--(1,3)--(2,3)--(2,2)--cycle, lightblue);
fill((0,1)--(0,2)--(1,2)--(1,1)--cycle, lightred);
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
draw(shift(i,j) * p, black);
}
draw(shift(3,i) * q, black);
}
draw(shift(3,3) * q, black);
[/asy][/asy]
alita
22.06.2018 12:49
vsathiam wrote: To show this is maximal, note that each disconnected square must not share a vertex with another disconnected square. I think that vsathiam is right. It now suffices to show that each disconnected square must not share a vertex with another disconnected square. This is clearly true if the two squares are of the same color, by the conditions of the problem. Now, suppose that a red disconnected square shares a vertex with a blue disconnected square. There are two cases: Case 1: The red square and the blue square shares two common vertices. [asy][asy] size(2cm); defaultpen(linewidth(1.5)); path p = (1,0)--(0,0)--(0,1)--(1,1)--(1,0); path q = (0,0)--(1,0); path r = (0,0)--(0,1); fill((6,0)--(7,0)--(7,-1)--(6,-1)--cycle,lightred); fill((7,0)--(8,0)--(8,-1)--(7,-1)--cycle,lightblue); draw(shift(5,0) * p, black); draw(shift(6,0) * p, black); draw(shift(5,-1) * p, black); draw(shift(7,0) * p, black); draw(shift(6,-1) * p, black); draw(shift(5,-2) * p, black); draw(shift(6,-2) * p, black); draw(shift(7,-1) * p, black); draw(shift(7,-2) * p, black); [/asy][/asy] Since the red square is disconnected, there must not be a red square in any of the eight(or three/five, if the red cell is on the corner/edge) cells that shares a vertex with that disconnected red square. Hence, these cells must all be blue squares. But then this implies that the disconnected blue square will share a vertex with another blue square, contradiction. [asy][asy] size(2cm); defaultpen(linewidth(1.5)); path p = (1,0)--(0,0)--(0,1)--(1,1)--(1,0); path q = (0,0)--(1,0); path r = (0,0)--(0,1); fill((5,0)--(5,1)--(6,1)--(6,0)--cycle,lightblue); fill((6,0)--(6,1)--(7,1)--(7,0)--cycle,lightblue); fill((5,0)--(6,0)--(6,-1)--(5,-1)--cycle,lightblue); fill((6,0)--(7,0)--(7,-1)--(6,-1)--cycle,lightred); fill((7,0)--(8,0)--(8,-1)--(7,-1)--cycle,lightblue); fill((7,1)--(8,1)--(8,0)--(7,0)--cycle,lightblue); fill((5,-2)--(5,-1)--(6,-1)--(6,-2)--cycle,lightblue); fill((6,-2)--(6,-1)--(7,-1)--(7,-2)--cycle,lightblue); fill((7,-2)--(7,-1)--(8,-1)--(8,-2)--cycle,lightblue); draw(shift(5,0) * p, black); draw(shift(6,0) * p, black); draw(shift(5,-1) * p, black); draw(shift(7,0) * p, black); draw(shift(6,-1) * p, black); draw(shift(5,-2) * p, black); draw(shift(6,-2) * p, black); draw(shift(7,-1) * p, black); draw(shift(7,-2) * p, black); [/asy][/asy] Case 2: The red square and the blue square shares one common vertex. Similar to case 1.
MK4J
28.10.2018 20:41
This problem was proposed as the last problem on the senior paper of the Danube Mathematical Competition 2018, held in Romania yesterday. Here is my idea of solution from the contest: Consider just the centers of the squares. Between any 2 adiacent cells, draw an edge between their centers if and only if they are of the same color. Moreover, paint that edge in the color of the 2 cells. In this way we obtain a kind of graph (the vertices are represented by the centers of the cells). A nice feature of the graph is that it is completely broken into many pieces, each piece having all the edges in the same color. Also, $M$ is exactly the number of pieces because in order to consider a set of $M$ cells with the given property, I simply choose a cell from each piece. That set formed verifies the problem's conditions. I want to prove $$M \leq (\frac{n+1}{2})^2 + 1$$and since the equality is verified for considering all the cells with both coordinates odd of a color and all the rest of the other one, I consider the following classification of pieces: surrounded and unsurrounded Consider a random piece. Suppose it does not have squares on the border of the table. Then, because it is limited in all the directions (otherwise it would be bigger or it would have cells on the border of the table, it is surrounded by a piece of the opposite color. If that piece that surrounds does not have squares on the border of the table, it is surrounded by another piece of the initial color. Now look at the 2 pieces inside this piece. I can change the colors between the squares and the rest of the table is not affected by this. Also, immediately, I can keep the 4 extremities of the mid piece (the one of opposite color than the rest) in the same color, being separated into 4 different pieces, each formed by a single square and all the rest of the cells being of the first color. In this way, I've increased the number of pieces in the table from $3$ to $5$. So $M$ increases, contradiction! What does this imply? It implies that any piece that surrounds some other piece in the given table will have squares on the border. But the number of squares on the border is $4n-2$ (a relatively small one). Also, any piece that is surrounded by other piece has to be formed by a single square. To conclude, denote by $S$ the number of different pieces that have squares on the border. In order for $M$ to be maximal, the cells on the border with all the coordinates odd can be painted again in a single color and the other to have the other color. By applying the implication found, $S$ will be $2n +1$, and the number of surrounded pieces will be $n^2$. Also, I can't have pieces from just a single color, so I have one more piece. That means $$M \leq (\frac{n+1}{2})^2 + 1,$$that is exactly the maximum searched for.
meagain
13.07.2019 23:34
arvindf232 wrote: Remarks: ... Now, obtain a graph $G$ by joining any two adjacent-by-edge square. Two diagonally adjacent square is only joint if there are precisely 2 black and 2 white squares in this local 2*2 square. This is done so that the graph is planar. ... Is this really how you want to make adjancency? Is really graph planar?
Afternonz
20.06.2022 16:05
Let $n=2k+1$. We claim the maximum number of connected components is $(k+1)^2+1$. Construction is the same as above posts. Now we induct on $k$ to show the upper bound and an additional statement: In any optimal coloring, all cells in the bottom row and the rightmost column must not all be the same color. Base case $k=1$ is some casework. Inductive step: Consider the following two "shells" (call red one the first shell and blue one the second shell) and label the three corners of the first shell $A,B,C$ as shown.
Consider groups of consecutive cells with the same color in the first shell. Let the number of cells in each group be $n_1,n_2,\dots,n_i$ when counting from $A$ to $C$-end. Note that the sum of all $n_i$s is $4k-1$. Catagorize these groups into 4 types: 1) the one not containing any of $A,B,C$, 2) the one containing $A$ but not $B,C$ (and its cyclic variants), 3) the one containing $A,B$ but not $C$ (and its cyclic variants), and 4) the one containing $A,B,C$. For each group $G$, we will bound the number of connected components that stay only in the second shell and share at least one side with $G$, denoted $M$, as follows: Suppose $G$ contains $n$ cells. $G$ is of type 1: $M\le \left\lfloor\frac{n-1}{2}\right\rfloor$
[asy][asy]
size(4cm);
defaultpen(linewidth(0.5));
path p=(0,0)--(0,1)--(1,1)--(1,0)--cycle;
path q=(0,0)--(0,-0.25);
fill(p, gray);
fill(shift(5,0)*p, gray);
fill((1,0)--(5,0)--(5,1)--(1,1)--cycle, lightblue);
draw((0,0)--(0,2)--(6,2)--(6,0)--cycle, black);
draw((0,1)--(6,1), black);
draw((-0.5,0)--(0,0), black+dotted);
draw((-0.5,1)--(0,1), black+dotted);
draw((-0.5,2)--(0,2), black+dotted);
draw((6,0)--(6.5,0), black+dotted);
draw((6,1)--(6.5,1), black+dotted);
draw((6,2)--(6.5,2), black+dotted);
draw((1,0)--(1,1), black);
draw((5,0)--(5,1), black);
label("$G$",(3,1.5));
draw(shift(1,-0.25)*q, black);
draw(shift(5,-0.25)*q, black);
draw((1,-0.375)--(5,-0.375), black);
label(scale(0.75)*"$n-2$ cells", (3,-0.75));
[/asy][/asy]
Each of the shaded cells will be connected to at least one component from the first shell, so we won't count it. Any two adjacent cells can contribute at most 1 to $M$ (If two cells have the same color, we are done. Otherwise, at least one of them shares the same color as the cell adjacent to both of them in the first shell). Hence, the blue part contributes at most $\frac{n-1}{2}$ to $M$ so $M\le\frac{n-1}{2}$. Note that $M$ is an integer to get the desired result.
$G$ is of type 2.1 (containing $A$ or $C$): $M\le \left\lfloor\frac{n}{2}\right\rfloor$
[asy][asy]
size(4cm);
defaultpen(linewidth(0.5));
path p=(0,0)--(0,1)--(1,1)--(1,0)--cycle;
path q=(0,0)--(0,-0.25);
fill(shift(5,0)*p, gray);
fill((0,0)--(5,0)--(5,1)--(0,1)--cycle, lightblue);
draw((1,1)--(1,2), black+dotted);
label(scale(0.8)*"$A$",(0.5,1.5));
draw((0,0)--(0,2)--(6,2)--(6,0)--cycle, black);
draw((0,1)--(6,1), black);
draw((6,0)--(6.5,0), black+dotted);
draw((6,1)--(6.5,1), black+dotted);
draw((6,2)--(6.5,2), black+dotted);
draw((5,0)--(5,1), black);
label("$G$",(3,1.5));
draw(shift(0,-0.25)*q, black);
draw(shift(5,-0.25)*q, black);
draw((0,-0.375)--(5,-0.375), black);
label(scale(0.75)*"$n-1$ cells", (2.5,-0.75));
[/asy][/asy]
Again, the shaded cell will not be counted. Then bound $M$ in the same way as Type 1.
$G$ is of type 2.2 (containing $B$): $M\le \left\lfloor\frac{n+1}{2}\right\rfloor$
[asy][asy]
size(4cm);
defaultpen(linewidth(0.5));
path p=(0,0)--(0,1)--(1,1)--(1,0)--cycle;
path q=(0,0)--(0,-0.25);
path r=(0,0)--(-0.25,0);
path s=(0,0)--(0,0.25);
fill(p, gray);
fill(shift(5,4)*p, gray);
fill((1,0)--(1,1)--(4,1)--(4,0)--cycle, lightblue);
fill((5,2)--(6,2)--(6,4)--(5,4)--cycle, lightblue);
fill((4,0)--(4,1)--(5,1)--(5,2)--(6,2)--(6,0)--(4,0)--cycle, lightred);
draw((0,0)--(0,2)--(4,2)--(4,5)--(6,5)--(6,0)--cycle, black);
draw((0,1)--(5,1)--(5,5), black);
draw((5,2)--(4,2)--(4,1), black+dotted);
label(scale(0.8)*"$B$", (4.5,1.5));
label("$G$", (3,1.5));
draw((1,0)--(1,1), black);
draw((4,0)--(4,1), black);
draw((5,2)--(6,2), black);
draw((5,4)--(6,4), black);
draw(shift(0,-0.25)*q, black);
draw(shift(4,-0.25)*q, black);
draw((0,-0.375)--(4,-0.375), black);
label(scale(0.6)*"$x$ cells", (2,-0.75));
draw(shift(6.25+0.25,5)*r, black);
draw(shift(6.25+0.25,2)*r, black);
draw((6.375,5)--(6.375,2), black);
label(scale(0.6)*"$y$ cells", (7.25,3.5));
draw(shift(4,5)*s, black+dotted);
draw(shift(5,5)*s, black+dotted);
draw(shift(6,5)*s, black+dotted);
draw(shift(0,0)*r, black+dotted);
draw(shift(0,1)*r, black+dotted);
draw(shift(0,2)*r, black+dotted);
[/asy][/asy]
Let $n=x+y+1$ as shown. The shaded cells (if exist) won't be counted. The red, blue parts contribute at most $1, \frac{x+y}{2}$ to $M$, resp. so $M\le \frac{x+y}{2}+1=\frac{n+1}{2}$.
$G$ is of type 3: $M\le \left\lfloor\frac{n}{2}\right\rfloor$
[asy][asy]
size(4cm);
defaultpen(linewidth(0.5));
path p=(0,0)--(0,1)--(1,1)--(1,0)--cycle;
path q=(0,0)--(0,-0.25);
path r=(0,0)--(-0.25,0);
path s=(0,0)--(0,0.25);
fill(shift(5,4)*p, gray);
fill((0,0)--(0,1)--(4,1)--(4,0)--cycle, lightgreen);
fill((5,2)--(6,2)--(6,4)--(5,4)--cycle, lightblue);
fill((4,0)--(4,1)--(5,1)--(5,2)--(6,2)--(6,0)--(4,0)--cycle, lightred);
draw((0,0)--(0,2)--(4,2)--(4,5)--(6,5)--(6,0)--cycle, black);
draw((0,1)--(5,1)--(5,5), black);
draw((5,2)--(4,2)--(4,1), black+dotted);
label(scale(0.8)*"$B$", (4.5,1.5));
label("$G$", (3,1.5));
draw((4,0)--(4,1), black);
draw((5,2)--(6,2), black);
draw((5,4)--(6,4), black);
draw((1,1)--(1,2), black+dotted);
label(scale(0.8)*"$A$",(0.5,1.5));
draw(shift(6.25+0.25,5)*r, black);
draw(shift(6.25+0.25,2)*r, black);
draw((6.375,5)--(6.375,2), black);
label(scale(0.6)*"$x$ cells", (7.25,3.5));
draw(shift(4,5)*s, black+dotted);
draw(shift(5,5)*s, black+dotted);
draw(shift(6,5)*s, black+dotted);
[/asy][/asy]
WLOG, the group contains $A,B$. Let $n=2k+x$. The shaded cells (if exist) won't be counted. The green, red, and blue part each contributes at most $k-1, 1,$ and $\frac{x}{2}$ to $M$ so $M\le (k-1)+1+ \frac{x}{2}=\frac{n}{2}$.
$G$ is of type 4: $M\le \left\lfloor\frac{n}{2}\right\rfloor$
[asy][asy]
size(4cm);
defaultpen(linewidth(0.5));
path p=(0,0)--(0,1)--(1,1)--(1,0)--cycle;
path q=(0,0)--(0,-0.25);
path r=(0,0)--(-0.25,0);
path s=(0,0)--(0,0.25);
fill((0,0)--(0,1)--(4,1)--(4,0)--cycle, lightblue);
fill((5,2)--(6,2)--(6,6)--(5,6)--cycle, lightblue);
fill((4,0)--(4,1)--(5,1)--(5,2)--(6,2)--(6,0)--(4,0)--cycle, lightred);
draw((0,0)--(0,2)--(4,2)--(4,6)--(6,6)--(6,0)--cycle, black);
draw((0,1)--(5,1)--(5,6), black);
draw((5,2)--(4,2)--(4,1), black+dotted);
label(scale(0.8)*"$B$", (4.5,1.5));
label("$G$", (3,1.5));
draw((4,0)--(4,1), black);
draw((5,2)--(6,2), black);
draw((1,1)--(1,2), black+dotted);
label(scale(0.8)*"$A$",(0.5,1.5));
draw((4,5)--(5,5), black+dotted);
label(scale(0.8)*"$C$",(4.5,5.5));
[/asy][/asy]
Note that $n=4k-1$. The red, blue parts contribute at most $1, 2(k-1)$, resp. Hence, $M\le 2(k-1)+1=\left\lfloor\frac{n}{2}\right\rfloor$.
Let $N$ be the number of connected components disjoint from the top-left $k-2\times k-2$ grid and $T$ be the total number of connected components. We now consider 3 cases: Case 1: There is a group of type 4. This means all cells in the first shell has the same color. $N$ is thus at most $1 + \left\lfloor\frac{n_1}{2}\right\rfloor=2k$. Apply the inductive hypothesis to get that $T$ is at most $k^2+1+2k$. Case 2: There is one group for each of type 2 and 3. WLOG, let the type-3 one contains $A,B$ so it contains $n_1$ cells. The type-2 one thus contains $n_i$ cells. We can show that \begin{align*} N &\le \underbrace{\left\lfloor\frac{i+1}{2}\right\rfloor}_{\text{from the first shell}}+\left\lfloor\frac{n_1+2}{2}\right\rfloor+\left(\left\lfloor\frac{n_2-1}{2}\right\rfloor+\dots+\left\lfloor\frac{n_{i-1}-1}{2}\right\rfloor\right) +\left\lfloor\frac{n_i}{2}\right\rfloor \\ &\le \frac{(i+1)+(n_1+n_2+\dots+n_i)+(2-(i-2))}{2}\\ &=2k+2. \end{align*}If equality case occurs, the first shell must contribute exactly $\frac{i+1}{2}$ components to $N$. This only happens when all cells in the top-left $k-2\times k-2$ grid that is adjacent to the first shell have the same color; the inductive hypothesis tells us that $T$ is at most $k^2+(2k+2)$ here. If this is not the case, $N\le 2k+1$ so $T \le (k^2+1)+(2k+1)$. Case 3: There is three groups of type 3. Suppose the groups containing $A,B,C$ contain $n_1,n_b,n_i$ cells, respectively. We can show that \begin{align*} N &\le\left\lfloor\frac{i+1}{2}\right\rfloor+\left\lfloor\frac{n_1}{2}\right\rfloor+\left(\left\lfloor\frac{n_2-1}{2}\right\rfloor+\dots+\left\lfloor\frac{n_{b-1}-1}{2}\right\rfloor+\left\lfloor\frac{n_{b}+1}{2}\right\rfloor+\left\lfloor\frac{n_{b+1}-1}{2}\right\rfloor+\dots+\left\lfloor\frac{n_{i-1}-1}{2}\right\rfloor\right) +\left\lfloor\frac{n_i}{2}\right\rfloor\\ &\le \frac{(i+1)+(n_1+n_2+\dots+n_i)+(1-(i-3))}{2}\\ &=2k+2. \end{align*}The finish is the same as Case 2. Now consider a coloring such that all cells in the second shell have the same color, say white. The number of black connected components in the first shell is at most $2k-1$. So $N\le 2k$ and $T\le (k^2+1)+2k<(k+1)^2+1$ by inductive hypothesis. Hence, such coloring is not optimal, finishing the inductive step.
IAmTheHazard
22.09.2023 23:32
A good reminder of why I don't do more china problems The answer is $(\tfrac{n+1}{2})^2+1$. For a construction label the rows/columns $1$ through $n$, and color the double-odd cells white. Now for the bound; induct on $n$. Check $n=3$ manually (and note that this bound also holds when $n=1$). Consider the cells in the leftmost two columns or topmost two rows and call this a hook. Ignore the other cells. Suppose we take the set of cells $S:=\{(2,n),(2,n-1),\ldots,(2,3),(3,2),\ldots,(n-1,2),(n,2)\}$ and place them into a rectangle in that order, and there are $c$ connected components. Also let $d$ be $2$ if both of $(2,n),(2,n-1)$ and $(n-1,2),(n,2)$ are same-color, $1$ if one of them is, and $0$ if neither of them are. I claim that there are at most $n+1+\tfrac{c-h-1}{2}$ connected components in this hook. This is just another induction on $n$ after checking $n=3$ manually (consider each "end" of the hook separately). Or at least I think so—I haven't checked everything (if someone would do this for me that would be nice lol) but I'm fairly confident it works out. We will only need the fact that this quantity is at most $n+1+\tfrac{c-1}{2}$ for the rest of the problem: $h$ is just used for the induction. Now reintroduce the rest of the grid. We consider only CCs in the hook that aren't connected to something in the bottom-right $(n-2) \times (n-2)$ grid. Between any two adjacent cells in $S$ which are different-color, at least one must be connected to something in the rest of the grid, so there are at least $\lfloor c/2\rfloor$ CCs in the hook which we should discount.This finishes except in the case where there are exactly $\tfrac{c-1}{2}$ CCs in the hook, which (among other things) implies $c$ is odd. It's fairly clear that in this case we would need all of $(3,n),\ldots,(3,4),(3,3),(4,3),\ldots,(n,3)$ to be the same color. Now apply this to the other hooks by taking top-right, bottom-right, bottom-left. This means that we only have to handle the case where the third highest and lowest rows and the third leftmost and rightmost columns are all the same color. For $n=5$ these divide the board into four disjoint $2 \times 2$ "corner" sections which each contain at most two other CCs, hence at most $9$ CCs in total which is small enough. Otherwise, these divide the board into four $2 \times 2$ "corner" sections, four $2 \times (n-6)$ "edge" sections, and an $(n-6) \times (n-6)$ "center" section. The corner sections each contribute at most two more CCs. By hypothesis the center section contributes at most $(\tfrac{n-5}{2})^2+1$ CCs. We now bound the number of CCs in an "edge" section. We prove a more general claim. Suppose we have a $2 \times m$ section (with $m$ odd) which is against a wall on the $m$-length side (and not to any other walls). Then it has at most $\tfrac{m+1}{2}$ CCs which aren't connected to cells outside the section. This just follows by induction, removing the top $2 \times 2$ square—note that if the bottom two cells of this cell are different then one must be connected to the lower $2 \times (m-2)$ part of the section. Applying this claim and adding back in the last CC (which are the four rows themselves), it follows that there are at most $$8+2(n-5)+\left(\frac{n-5}{2}\right)^2+1+1=\frac{n^2-2n+25}{4}$$CCs total, which is at most $(\tfrac{n+1}{2})^2+1$ since $n \geq 7$. $\blacksquare$