China Mathematical Competition (Complementary Test)

We first claim that the number of “bad cells” in $A$ is no more than $25$. Otherwise, there will be at most one cell in $A$ that is not “bad”. Without loss of generality, we assume the cells in the first row of $A$ are all “bad”. Then let the numbers from top to bottom in the $i$th column be $a_i,b_i,c_i$ ($i=1,2,\dots ,9$) in turn, and define $$S_k=\sum _{i=1}^k{a}_i,T_k=\sum _{i=1}^k(b_i+c_i),k=1,2,\dots ,9,$$ with $S_0=T_0=0$. We are going to prove that three number groups $S_0,S_1,\dots ,S_9$, $T_0,T_1,\dots ,T_9$, and $S_0+T_0,S_1+T_1,\dots ,S_9+T_9$ each form a complete set of residues modulo $10$:

If there exist $m,n,0\le m<n\le 9$ such that $S_m\equiv S_n(\mathrm{mod}10)$, then $$\sum _{i=m+1}^n{a}_i=S_n-S_m\equiv 0(\mathrm{mod}10),$$ which means that the cells in the first row and from columns $m+1$ to $n$ form a “good rectangle”. But it is a contradiction to the assumption that the cells in the first row are all “bad”.

If there exist $m,n,0\le m<n\le 9$ such that $T_m\equiv T_n(\mathrm{mod}10)$, then $$\sum _{i=m+1}^n(b_i+c_i)=T_n-T_m\equiv 0(\mathrm{mod}10).$$ So the cells ranging from rows $2$ to $3$ and columns $m+1$ to $n$ form a “good rectangle”, which means there are at least two cells that are not “bad”. But it is also a contradiction.

In a similar way, we can also prove that there are no $m,n,0\le m<n\le 9$ such that $$S_m+T_m\equiv S_n+T_n(\mathrm{mod}10).$$ Therefore, we have $$\begin{array}{rl}\sum _{k=0}^9{S}_k& \equiv \sum _{k=0}^9{T}_k\equiv \sum _{k=0}^9(S_k+T_k)\equiv 0+1+2+\cdots +9\\ & \equiv 5(\mathrm{mod}10).\end{array}$$ Then $$\sum _{k=0}^9(S_k+T_k)\equiv \sum _{k=0}^9{S}_k+\sum _{k=0}^9{T}_k\equiv 5+5\equiv 0(\mathrm{mod}10).$$ It is again a contradiction! Therefore, the number of “bad cells” in $A$ is no more than $25$.

On the other hand, we can construct a $3\times 9$ array in the following and check that each cell in it that does not contain number $10$ is “bad”.

1	1	1	2	1	1	1	1	10
1	1	1	1	1	1	1	1	1
1	1	1	10	1	1	1	1	2

Therefore, we find out that the maximum number of “bad cells” in $A$ is $25$.

$\boxed{25}$