2023 Chinese IMO National Team Selection Test

Let the row with the maximum number of red squares (let's assume it's the first row) have $a$ red squares, and the column with the maximum number of red squares (let's assume it's the first column) have $b$ red squares. If $a>b$, consider the $a$ columns in which the $a$ red squares of the first row are located. These columns must have distinct numbers of red squares and can only be chosen from $1,2,\dots ,b$. This leads to a contradiction. Similarly, we can show that $a$ cannot be less than $b$. Therefore, we conclude that $a=b$. Moreover, the number of red squares in the columns where the red squares of the first row are located must be a permutation of $1,2,\dots ,a$, and the number of red squares in the rows where the red squares of the first column are located must also be a permutation of $1,2,\dots ,a$. In other words, for any $1\le i\le a$, there exist rows with exactly $i$ red squares and columns with exactly $i$ red squares.

Next, we prove that there exists a coloring that satisfies condition (1) and has $x_i$ rows with exactly $i$ red squares and $y_i$ columns with exactly $i$ red squares ($x_i,y_i\in {\mathbb{Z}}_{>0}$, $i=1,2,\dots ,a$), if and only if there exists a coloring of an $a\times a$ grid such that the $i$th row has exactly $i{x}_i$ red squares and the $i$th column has exactly $i{y}_i$ red squares ($i=1,2,\dots ,a$). ().

First, we prove the necessity. If the coloring of a $70\times 70$ grid $P$ satisfies condition (1), we construct an $a\times a$ grid $Q$ with the following coloring: for any $i,j\in \{1,2,\dots ,a\}$, the cell in the $i$th row and $j$th column of $Q$ is colored red if and only if $P$ has a red cell in a row with exactly $i$ red cells and a column with exactly $j$ red cells (denoted as $T(i,j)$). Note that in $P$, the number of red cells in a row with exactly $i$ red cells is $i{x}_i$, and the numbers of red cells in their corresponding columns are distinct. Therefore, $Q$ satisfies $T(i,j)$ if and only if there are exactly $i{x}_i$ red cells in column $j$, which implies that the $i$th row of $Q$ has exactly $i{x}_i$ red cells. Similarly, the $i$th column of $Q$ has exactly $i{y}_i$ red cells. Thus, the necessity is proved.

Next, we prove the sufficiency. Assume that the $a\times a$ grid $Q$ has exactly $i{x}_i$ red cells in the $i$th row and exactly $i{y}_i$ red cells in the $i$th column. We construct a $70\times 70$ grid $P$ as follows: we label all rows of $P$ as $R(i,x)$ ($1\le x\le x_i$) and all columns of $P$ as $C(i,y)$ ($1\le y\le y_i$). Then, we color the cells of $P$ as follows: if the cell in the $i$th row and $j$th column of $Q$ is red, we mark $(i,j)$ as a good pair. For each good pair $(i_0,j_0)$, we define $v(i_0,j_0)$ as the index of $j$ (in ascending order) such that $(i_0,j)$ is a good pair, and $u(i_0,j_0)$ as the index of $i$ (in ascending order) such that $(i,j_0)$ is a good pair. Then, in $P$, we color the intersection of row $R(i_0,\lfloor \frac{v(i_0,j_0)}{i_0}\rfloor )$ and column $C(j_0,\lfloor \frac{u(i_0,j_0)}{j_0}\rfloor )$ red. In this way, each good pair $(i_0,j_0)$ is associated with only one pair of row $R(i_0,x)$ and column $C(j_0,y)$, satisfying condition (1). Moreover, for any row $R(i_0,x)$, the red cells correspond to $j$ values that are the $(x-1)i_0+1$st, $(x-1)i_0+2$nd, ..., $x{i}_0$th smallest $j$ among all good pairs $(i_0,j_0)$. Thus, this row has exactly $i_0$ red cells. Similarly, each column $C(j_0,y)$ has exactly $j_0$ red cells. Therefore, the sufficiency is proved, and thus () holds.

Returning to the original problem, let's first construct an example for $m=32$. Consider a $64\times 64$ grid $Q$, where the cell in the $i$th row and $j$th column is colored red if and only if $i+j\le 66$. This coloring ensures that each row of $Q$ has a decreasing number of red cells from 64 to 2, and each column has the same pattern. Now, let $$a=64,x_{32}=x_{16}=x_8=x_4=x_2=x_1=y_{32}=y_{16}=y_8=y_4=y_2=y_1=2,$$ while all other $x_i$ and $y_i$ are set to 1. According to (*) and the above construction, we know that there exists a grid $P$ that satisfies condition (1) and has two rows with exactly 32 red cells. Thus, we have shown that $m=32$ meets the requirements of the problem.

Finally, we prove that $m$ cannot be greater than 32. Note that when $x_i\ge 2$, we have $2m\le a\le 69$, which implies $m\le 34$. We only need to show that $m$ cannot equal 33 or 34. In this case, we only need to consider $a\in \{66,67,68,69\}$. For the grid $Q$ and any $r,s\le a$, the difference between the total number of red cells in any $r$ rows and the total number of red cells in any $s$ columns is no more than the total number of red cells in those $r$ rows and the remaining $a-s$ columns, which is no more than $r(a-s)$.

If $a=69$, then we have $x_m=2$ and all other $x_i$ can only be 1. From calculating twice, we find that only $y_m=2$ and all other $y_i$ can only be 1. In this case, in the grid $Q$, the top 5 rows with the maximum number of red cells have at least $69+68+67+66+66$ red cells, while the leftmost 5 columns with the minimum number of red cells have $1+2+3+4+5$ red cells. However, $$(69+68+67+66+66)-(1+2+3+4+5)>5\cdot (69-5),$$ which leads to a contradiction!

If $a=68$, similarly, we have $$(68+67+66+66+66)-(1+2+3+4)>4\cdot (68-4),$$ which means that at least one of $y_1,y_2,y_3,y_4$ is not less than 2. Since $$(68+67+66+66+65+64+63+62)-(1+2+3+4+5+6+7+8)-8\cdot (68-8)>4,$$ we have ${\sum }_{i=1}^8(y_i-1)\ge 2$. Furthermore, notice that $$(68+67+66+66+65+\cdots +54)-(1+2+\cdots +16)-16\cdot (68-16)>4+8,$$ which implies ${\sum }_{i=1}^{16}(y_i-1)\ge 3$. However, this contradicts the fact that ${\sum }_{i=1}^{68}(y_i-1)=2$.

If $a=67$ (in this case, $m=33$), similarly, we have $$(67+66+66+66)-(1+2+3)>3\cdot (67-3),$$ which implies that at least one of $y_1,y_2,y_3$ is not less than 2. Additionally, we have $$(67+66+66+65+64+63)-(1+2+3+4+5+6)-6\cdot (67-6)>3,$$ which means that ${\sum }_{i=1}^6(y_i-1)\ge 2$. Furthermore, we have $$(67+66+66+65+\cdots +57)-(1+2+\cdots +12)-12\cdot (67-12)>3+6,$$ implying that ${\sum }_{i=1}^{12}(y_i-1)\ge 3$. Finally, we have $$(67+66+66+65+\cdots +45)-(1+2+\cdots +24)-24\cdot (67-24)>3+6+12,$$ which shows that ${\sum }_{i=1}^{24}(y_i-1)\ge 4$. However, this contradicts the fact that ${\sum }_{i=1}^{67}(y_i-1)=3$.

If $a=66$ (in this case, $m=33$), we have two values of $i{x}_i$ equal to 66, indicating that all $i{y}_i$ are not less than 2, i.e., $y_1\ge 2$. Similarly, we have $$(66+66+65)-(1+2)-3\cdot (66-2)>1,$$ which implies ${\sum }_{i=1}^2(y_i-1)\ge 2$. Furthermore, we have $$(66+66+65+64+63)-(1+2+3+4)-5\cdot (66-4)>1+2,$$ implying ${\sum }_{i=1}^4(y_i-1)\ge 3$. Additionally, we have $$(66+66+65+\cdots +59)-(1+2+\cdots +8)-9\cdot (66-8)>1+2+4,$$ which shows ${\sum }_{i=1}^8(y_i-1)\ge 4$. Moreover, we have $$(66+66+65+\cdots +51)-(1+2+\cdots +16)-17\cdot (66-16)>1+2+4+8,$$ implying ${\sum }_{i=1}^{16}(y_i-1)\ge 5$. However, this contradicts the fact that ${\sum }_{i=1}^{66}(y_i-1)=4$.

In conclusion, the maximum value of $m$ that satisfies the conditions is 32. $\square$