China Southeastern Mathematical Olympiad

Proof For any integer $m\ge 2$, if the remainder of $x$ divided by $m$ is $i$, $i\in \{0,1,\dots ,m-1\}$, then $x$ belongs to the residue class modulus $m$, $K_i$. Suppose in the set $A=\{a_1,a_2,\dots ,a_n\}$, the number of elements that belong to $K_i$ is $n_i$ ($i=0,1,2,\dots ,m-1$), while in the set $B=\{1,2,\dots ,n\}$, the number of elements that belong to $K_i$ is $n_i^{\prime }$ ($i=0,1,2,\dots ,m-1$), then $$\sum _{i=0}^{m-1}{n}_i=\sum _{i=0}^{m-1}{n}_i^{\prime }=n.\stackrel{◯}{1}$$ It is obvious that for every $i,j$, $|n_i^{\prime }-n_j^{\prime }|\le 1$, and $x-y$ is a multiple of $m$ if and only if $x,y$ belong to the same residue class. As to any two elements $a_i,a_j$ in $K_i$, we have $m\mid a_j-a_i$. Hence, the $n_i$ elements in $K_i$ form $\left(\genfrac{}{}{0ex}{}{n_i}{2}\right)$ multiples of $m$. Considering all the $i$, we obtain $$\bar{A}(m)=\sum _{i=0}^{m-1}\left(\genfrac{}{}{0ex}{}{n_i}{2}\right).$$ Similarly, $$\bar{B}(m)=\sum _{i=0}^{m-1}\left(\genfrac{}{}{0ex}{}{n_i^{\prime }}{2}\right).$$ Hence, to solve the problem, we just need to prove that $$\sum _{i=0}^{m-1}\left(\genfrac{}{}{0ex}{}{n_i}{2}\right)\ge \sum _{i=0}^{m-1}\left(\genfrac{}{}{0ex}{}{n_i^{\prime }}{2}\right),\text{and it can be simplified to}$$ $$\sum _{i=0}^{m-1}{n}_i^2\ge \sum _{i=0}^{m-1}{n}_i^{\prime 2}.\stackrel{◯}{2}$$ From ①, if for every $i,j$, $|n_i-n_j|\le 1$, then $n_0,n_1,\dots ,n_{m-1}$ and $n_0^{\prime },n_1^{\prime },\dots ,n_{m-1}^{\prime }$ must be the same group (in spite of the different order), and equality holds in ②. Otherwise, if there exist $i,j$, such that $n_i-n_j\ge 2$, then we should just change the two elements $n_i,n_j$ for ${\bar{n}}_i,{\bar{n}}_j$ respectively, where ${\bar{n}}_i=n_i-1$, ${\bar{n}}_j=n_j+1$, and $n_i+n_j={\bar{n}}_i+{\bar{n}}_j$. Since $$(n_i^2+n_j^2)-({\bar{n}}_i^2+{\bar{n}}_j^2)=2(n_i-n_j-1)>0,$$ the sum of the left side in ② will decrease after adjustment. Therefore, the minimum value of ② is attained if and only if $n_0,n_1,\cdots ,n_{m-1}$ and $n_0^{\prime },n_1^{\prime },\cdots ,n_{m-1}^{\prime }$ are the same group (in spite of the different order), that is, the inequality ② holds.