2022 China Team Selection Test for IMO

Proof: Mark red all points $(i,j)$ for which $|a_i+b_j-ij|\le m$.

Lemma: If $(i_1,j_1)$, $(i_1,j_2)$, $(i_2,j_1)$, $(i_2,j_2)$ are all red, then $|(i_2-i_1)(j_2-j_1)|\le 4m$.

Proof of the lemma: By the definition of red points, we know $$|a_{i_1}+b_{j_1}-i_1{j}_1|\le m,|a_{i_1}+b_{j_2}-i_1{j}_2|\le m,|a_{i_2}+b_{j_1}-i_2{j}_1|\le m,|a_{i_2}+b_{j_2}-i_2{j}_2|\le m.$$ Taking the differences of these expressions to eliminate $a_{i_1}$, $a_{i_2}$, $b_{j_1}$, and $b_{j_2}$, we get $|i_1{j}_1-i_1{j}_2-i_2{j}_1+i_2{j}_2|\le 4m$. This proves the lemma.

We first calculate, for a given pair $1\le i_1<i_2\le n$, the number of $j$'s such that $(i_1,j)$ and $(i_2,j)$ are all red points. Put $d=i_2-i_1$. Since the difference of any two such $j$'s is at most $\frac{4m}{d}$, we can have at most $\frac{4m}{d}+1$ such $j$'s.

Moreover, when the difference $d$ is given, there are $n-d$ ways to choose $i_1$ and $i_2$, so the total number of $1\le i_1<i_2\le n$ and $1\le j\le n$ for which $(i_1,j)$ and $(i_2,j)$ are all red points cannot be larger than $$\sum _{d=1}^{n-1}(n-d)\left(\frac{4m}{d}+1\right)=\sum _{d=1}^{n-1}(n-d)-4mn+4m\sum _{d=1}^{n-1}\frac{n}{d}<\frac{n(n-1)}{2}+4mn\ln n.$$

On the other hand, for $1\le j\le n$, assume that there are $x_j$ red points in $(1,j)$, $(2,j)$, ..., $(n,j)$. Then $$\sum _{j=1}^n{C}_{x_j}^2<\frac{n(n-1)}{2}+4mn\ln n.$$ So $$\sum _{j=1}^n{\left(x_j-\frac{1}{2}\right)}^2<n^2-\frac{1}{4}n+8mn\ln n.$$ By Cauchy's inequality, we know $$\sum _{j=1}^n\left(x_j-\frac{1}{2}\right)\le \sqrt{n\left(n^2-\frac{1}{4}n+8mn\ln n\right)},$$ i.e. $$\sum _{j=1}^n{x}_j\le \frac{n}{2}+n\sqrt{n-\frac{1}{4}+8m\ln n}.$$ When $m\ge n\ge 2022$, some elementary estimate shows that $\le 3n\sqrt{m\ln n}$.