China-TST-2023B

Proof. The desired value of $k$ is $n^2+n+1$.

First, we provide an example of coloring $n^2+n$ cells black, such that it is impossible to perform operation 1. This implies that $k\ge n^2+n+1$.

Color the anti-diagonal cells black, and then color black all the cells $(i,j)$ in the top-left part of the anti-diagonal, where both $i$ and $j$ are odd and $i+j<2n$. Similarly, color black all the cells $(i,j)$ in the bottom-right part of the anti-diagonal, where both $i$ and $j$ are even and $i+j>2n+2$. (The following diagram illustrates the case of $n=4$, where the cells marked with $\ast$ are colored black.)



It can be seen that a total of $n^2+n$ cells are colored black, and they satisfy the following property.

$(\star )$ For any two black cells $(i,j_1)$ and $(i,j_2)$ in the same row with $j_1<j_2$, there exists $j_1<j<j_2$ such that cells $(i-1,j)$, $(i,j)$, and $(i+1,j)$ are all white. Similarly, for any two black cells $(i_1,j)$ and $(i_2,j)$ in the same column with $i_1<i_2$, there exists $i_1<i<i_2$ such that cells $(i,j-1)$, $(i,j)$, and $(i,j+1)$ are all white. Here, all cells in the 0th row, the $(2n+1)$th row, the 0th column, and the $(2n+1)$th column are considered white.

Note that if a state satisfies $(\star )$, then in any $2\times 3$ rectangle, there can be at most 2 black cells (otherwise, either two black cells share a common edge, or there exists a white cell that has three black cells adjacent to it, both of which violate $(\star )$).

Now we will prove that for any operation performed on the diagram, it can only be operation 2, and the two colored cells will not share a common edge. Additionally, property $(\star )$ will continue to hold. If this statement is true, it implies that it is impossible to completely color all cells black. The initial state clearly satisfies the above assertion. Assuming the assertion holds after some operations, we will show that after performing one operation 2, property $(\star )$ will still be satisfied. Due to symmetry, we only need to consider the resulting cells $(i,j_1)$ and $(i,j_2)$. We will discuss two cases.

• Case 1: Both $(i,j_1)$ and $(i,j_2)$ are originally black cells. In this case, there exists $j_1<j<j_2$ such that cells $(i-1,j)$, $(i,j)$, and $(i+1,j)$ are all white. Note





(The scripts in the figure is: “at most black cells.”) If the operation does not increase the number of black cells in this $3\times (j_2-j_1-1)$ rectangle, then there must still be a column in these three rows with no black cells, which satisfies property $(\star )$. If the operation increases the number of black cells in the $3\times (j_2-j_1-1)$ rectangle, then by the description of operation 2 and the fact that any two black cells were not adjacent, it must involve adding a black cell to one of the corners of the upper $3\times (j_2-j_1-1)$ rectangle. In this case, prior to the operation, either $(i-1,j_1)$, $(i+1,j_1)$, $(i-1,j_2)$, or $(i+1,j_2)$ must have at least one black cell. However, this configuration would result in two black cells sharing a common edge, which is a contradiction!

Case 2: One of $(i,j_1)$ and $(i,j_2)$ is a newly colored black cell (the two newly colored cells are in different rows and different columns, so both $(i,j_1)$ and $(i,j_2)$ cannot be new cells). Without loss of generality, let's assume $(i,j_2)$ is the newly colored cell. Also, due to symmetry, let's assume the operation occurs in a $2\times 2$ rectangle in the $(i-1)$th and $i$th rows. If the operation involves changing $(i-1,j_2)$ and $(i,j_2-1)$ from black to white, and changing $(i-1,j_2-1)$ and $(i,j_2)$ from white to black, then prior to the operation, using property $(\star )$ for $(i,j_1)$ and $(i,j_2-1)$, we know that there exists $j_1<j<j_2-1$ such that cells $(i,j-1)$, $(i,j)$, and $(i,j+1)$ are all white. Therefore, after the operation, this $j$ still satisfies property $(\star )$. If the operation involves changing $(i-1,j_2)$ and $(i,j_2+1)$ from black to white, and changing $(i-1,j_2+1)$ and $(i,j_2)$ from white to black, then prior to the operation, using property $(\star )$ for $(i,j_1)$ and $(i,j_2+1)$, we know that there exists $j_1<j<j_2+1$ such that cells $(i,j-1)$, $(i,j)$, and $(i,j+1)$ are all white. Additionally, it is clear that $j\ne j_2$, so this $j$ still satisfies property $(\star )$.

Next, we will prove that $k=n^2+n+1$ satisfies the conditions. To do this, we need to show that if the number of black cells is not less than $n^2+n+1$ and there is at least one white cell, then it is possible to perform several operations 2 followed by one operation 1. We will use a proof by contradiction. First, we prove a lemma.

Lemma: Let $x_i$ be the number of black cells in the $i$th row. If $x_{i-1}+2x_i+x_{i+1}\ge 2n+2$, then it is possible to perform some operations 2 in the $(i-1)$th, $i$th, and $(i+1)$th rows such that (within this $3\times 2n$ rectangle) there are two black cells with a common edge (where $x_0=x_{2n+1}=0$).



Proof of the Lemma:** We first prove that it is possible to perform some operations 2 in the $(i-1)$th, $i$th, and $(i+1)$th rows without changing $x_{i-1}$, $x_i$, and $x_{i+1}$, such that (within this $3\times 2n$ rectangle) there is either a row or a column with two black cells having a common edge. Assuming otherwise, it means that there are no rows or columns with two black cells having a common edge in the current state. Let the black cells in the $i$th row be in columns $j_1,\dots ,j_r$ with $j_1<\cdots <j_r$. If in the $(i-1)$th, $i$th, and $(i+1)$th rows, there are at most $j_{k+1}-j_k-2$ black cells in columns $j_k+1,\dots ,j_{k+1}-1$ ($k=1,\dots ,r-1$), then the first $j_1-1$ columns in these three rows have at most $j_1-1$ black cells, and the last $2n-j_r$ columns have at most $2n-j_r$ black cells. Hence, we have $x_{i-1}+2x_i+x_{i+1}\le 2r+(j_1-1)+(2n-j_r)+{\sum }_{k=1}^{r-1}(j_{k+1}-j_k-2)=2n+1$, which is a contradiction.

If there are more than $j_1-1$ black cells in the first $j_1-1$ columns or more than $2n-j_r$ black cells in the last $2n-j_r$ columns, it can also be concluded that there is a $2\times 3$ rectangle with at least 3 black cells. In this case, there must be three black cells that do not share a common edge. Performing one operation 2 on two of these cells will result in two black cells in a column with a common edge, without changing $x_{i-1}$, $x_i$, and $x_{i+1}$.

If there exists $k\in \{1,\dots ,r-1\}$ such that there are at least $j_{k+1}-j_k-1$ black cells in columns $j_k+1,\dots ,j_{k+1}-1$ in these three rows, we first note that if there are two adjacent columns in these three rows that have at least 3 black cells, we can similarly perform operation 2 to make two black cells adjacent. Assuming this case does not occur, in particular, the columns $j_k+1$ and $j_{k+1}-1$ have at most 1 black cell each. However, the sum of the number of black cells in columns $j_k+1,\dots ,j_{k+1}-1$ in these three rows is at least $j_{k+1}-j_k-1$. By simple analysis, we can see that both the $j_k+1$ column and the $j_{k+1}+1$ column in these three rows must have exactly one black cell. After performing operation 2 on $(i,j_k)$ and the black cell in the $j_k+1$ column, both $(i,j_k+1)$ and $(i,j_{k+1})$ will be black cells, and there will still be at least $j_{k+1}-j_k-2$ black cells in columns $j_k+2,\dots ,j_{k+1}-1$. Repeat this discussion and operation until the last two black cells in the $i$th row are adjacent.

Now if there are two black cells with a common edge in the same row, the conclusion is already established. If there are two black cells with a common edge in the same column, we can perform operations to move them horizontally. Note that both rows cannot have only one black cell (otherwise, the other row would have at least $(2n+2)-2\cdot 1-1=2n-1$ black cells, which would lead to two black cells with a common edge within that row). Therefore, it is always possible to perform operations to have two black cells with a common edge in the same row, and the lemma is proved. $\square$

Returning to the original problem, we have $$x_1+\sum _{i=1}^n(x_{2i-1}+2x_{2i}+x_{2i+1})\ge 2(n^2+n+1),$$ where $x_{2n+1}=0$. If $x_1\ge n+1$, then the first row has two consecutive black cells. If $x_1\le n$, then there exists $i\in \{1,2,\dots ,n\}$ such that $$x_{2i-1}+2x_{2i}+x_{2i+1}\ge \lceil \frac{2n^2+n+2}{n}\rceil \ge 2n+2,$$ and by the lemma, we can perform some operations 2 within these three rows to have two black cells with a common edge within a single row.

Assume these two cells are located in the $j_1$th column and the $(j_1+1)$st column. Let $u$ and $v$ be the maximum positive integers such that there are black cells in the columns $j_1-u,j_1-(u-1),\dots ,j_1+v$. If one of these columns has at least 2 black cells, let's say the column $j_1-s$. We perform operations 2 on $(2i,j_1)$ and $(2i,j_1+1)$ until the black cell in the $(i,j_1)$th row is in the same row as the black cell in the $(j_1-1)$th column. Then, we perform operations on the $j_1-1$st and $j_1$th columns to make the black cell in the $j_1-1$st column in the same row as one of the black cells in the $j_1-2$nd column, and so on. Finally, we can make the black cell in the $j_1-(s-1)$th column in the same row as one of the black cells in the $j_1-s$th column. Then, we perform operations on the $j_1-(s-1)$th and $j_1-s$th columns to bring these two cells close to another black cell in the $j_1-s$th column, forming a $2\times 2$ square with at least 3 black cells (if operations 2 cannot be performed during this process, it means that a similar situation has occurred). If this $2\times 2$ square can be transformed by operation 1, then the conclusion is already established. If not, then all four cells in this $2\times 2$ square are black. We can move these four black cells upwards, downwards, leftwards, or rightwards until they encounter another black cell. At this point, if it is not possible to perform operation 1, it means that a $2\times 3$ rectangle has been formed with all four cells being black. Considering the three cells on the other side of an edge with length 3, if one or two of them are black, operation 1 can be performed. If none of them is black, then operation 2 can be performed on the four cells on both sides of this edge, followed by operation 1. Therefore, all three cells must be black. By induction, it can be concluded that all cells are black, which contradicts our assumption. Therefore, all the columns $j_1-u,j_1-(u-1),\dots ,j_1+v$ have exactly one black cell.

At this point, let the number of black cells in each column be $y_1,y_2,\dots ,y_n$. Either there are two black cells with a common edge in the first column, or there exists $1\le j\le n$ such that $y_{2j-1}+2y_{2j}+y_{2j+1}\ge 2n+2$. From $y_{j_1-u}=y_{j_1-u+1}=\cdots =y_{j_1+v}=1$ and $y_{j_1-j-1}=y_{j_1+v+1}=0$, it follows that $$2j\notin \{j_1-u-1,j_1-u,\dots ,j_1+v+1\}.$$ Using the same procedure as before, we can perform operations in the columns $2j-1,2j,2j+1$ such that there are two black cells with a common edge in one of these columns, without affecting the two black cells with a common edge in the same row. Now, we vertically move the two black cells in the same row and horizontally move the two black cells in the same column until these four black cells “meet,” creating a $2\times 2$ square with at least 3 black cells. As discussed earlier, it is always possible to perform operation 1 after several operations 2, and thus $k=n^2+n+1$ satisfies the given condition.

Therefore, the minimum value of $k$ is $n^2+n+1$. $\square$