, 2022

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, \quad |a_{i_1} + b_{j_2} - i_1 j_2| \le m, \quad |a_{i_2} + b_{j_1} - i_2 j_1| \le m, \quad |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_1j_1 - i_1j_2 - i_2j_1 + i_2j_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}$.