2022 China Team Selection Test for IMO

Proof: Consider the set of all positive integers that are coprime to $6$: $B=\{1,5,7,11,13,\dots \}$, it is obvious that the sum $f(k)$ of the smallest $k$ elements of $B$ satisfies $$f(k)=\{\begin{array}{ll}\frac{3k^2}{2}& \text{if }k\text{ is even}\\ \frac{3k^2-1}{2}& \text{if }k\text{ is odd}\end{array},f(k+1)-f(k)=3k+1\text{ or }3k+2.$$ $$f(0)=0,f(1)=1,f(2)=6,f(3)=13,f(4)=24,f(5)=37,\dots$$ Every positive integer $a$ can be uniquely written as $a=2^{\alpha }{3}^{\beta }b$, with $b\in B$ and nonnegative integers $\alpha ,\beta$. Denote $h(a)=b$ or say $b$ is the core of $a$. If $a_1,\dots ,a_m$ are $m$ positive integers that cannot divide one another, and that all of their cores are $b$, then writing each $a_k=2^{{\alpha }_k}{3}^{{\beta }_k}b$ with $k=1,\dots ,m$, we must have that ${\alpha }_1,\dots ,{\alpha }_m$ are pairwise distinct (otherwise two numbers $2^{\alpha }{3}^{\beta }b$ and $2^{\alpha }{3}^{{\beta }^{\prime }}b$ must have division relations). We may put them in a sequence so that ${\alpha }_1<{\alpha }_2<\cdots <{\alpha }_m$, then correspondingly we have ${\beta }_1>{\beta }_2>\cdots >{\beta }_m\ge 0$, this time we get $a_k\ge 2^{k-1}{3}^{m-k}b$. Moreover, the sum of these $m$ numbers $$a_1+a_2+\cdots +a_m\ge 2^0{3}^{m-1}b+2^1{3}^{m-2}b+\cdots +2^{m-1}{3}^{0}b=(3^m-2^m)b.$$ We consider the map from $A=\{a_1,a_2,\dots ,a_n\}$ to $B$ by taking the cores, i.e. every $b\in B$ is the core for several numbers in $A$. Set $$B_k=\{b\in B:\#\{a\in A:h(a)=b\}\ge k\}.$$ i.e. the numbers in $B_k$ are the core for at least $k$ numbers in $\{a_1,\dots ,a_n\}$. Thus $B\supseteq B_1\supseteq B_2\supseteq \dots$, and the numbers in $B_k\setminus B_{k+1}$ are precisely the core for exactly $k$ numbers in $\{a_1,\dots ,a_n\}$. We have $$n=\sum _{k=1}^{\infty }k\cdot |B_k\setminus B_{k+1}|=|B_1|+|B_2|+\dots$$ We use $S(\cdot )$ to denote the sum of the elements in a set. We have: $$S(A)=a_1+\cdots +a_n\ge \sum _{k=1}^{\infty }(3^k-2^k)\times S(B_k\setminus B_{k+1})=\sum _{k=1}^{\infty }[(3^k-2^k)-(3^{k-1}-2^{k-1})]\times S(B_k)$$ $$S(A)\ge \sum _{k=1}^{\infty }(2\times 3^{k-1}-2^{k-1})\times f(|B_k|)$$ Define the sequence $c_k=2\times 3^{k-1}-2^{k-1}$, e.g. $c_1=1$, $c_2=4$, $c_3=14$, $c_4=46$, $c_5=146$, ... We turn to consider the optimization problem $♠$: under the assumption $x_1+x_2+\cdots =n$ (with each $x_i$ nonnegative), minimize $T=c_{1}f(x_1)+c_{2}f(x_2)+\dots$. Suppose that $X=(x_1,x_2,\dots ,x_K,0,0,\dots )$ minimizes $T$, where $x_1\ge x_2\ge \cdots \ge x_K\ge 1$, and $x_{K+1}=x_{K+2}=\cdots =0$. If $K\le 2$, then $$T=c_{1}f(x_1)+c_{2}f(x_2)\ge \frac{3x_1^2-1}{2}+4\frac{3x_2^2-1}{2}\ge \frac{6}{5}(x_1+x_2{)}^2-\frac{5}{2}\ge 1.1n^2-2n.$$ If $K\ge 3$, then $X$ being (one of) the minimizing points would mean: if we change $X$ to $X^{\prime }=(x_1+1,x_2,\dots ,x_{K-1},x_K-1,0,\dots )$, $T$ does not decrease, i.e. $$0\le \Delta T=c_1(f(x_1+1)-f(x_1))-c_K(f(x_K)-f(x_K-1))\le 3x_1+2-c_K\Rightarrow c_K\le 3x_1+2;$$ if we change $X$ to $X^{\prime \prime }=(x_1,x_2+1,\dots ,x_{K-1},x_K-1,0,\dots )$, then $T$ does not decrease, i.e. $$0\le \Delta T=c_2(f(x_2+1)-f(x_2))-c_K(f(x_K)-f(x_K-1))\le 4(3x_2+2)-c_K\Rightarrow c_K\le 12x_2+8.$$ So $n=x_1+x_2+\cdots +x_K\ge x_1+x_2+1\ge \frac{c_K-2}{3}+\frac{c_K-8}{12}+1=\frac{5c_K-4}{12}$, we get $$c_1+c_2+\cdots +c_K\le c_K\left(1+\frac{1}{3}+\cdots +\frac{1}{3^{K-1}}\right)\le \frac{12n+4}{5}\times \frac{3}{2}\le 4n.$$ Thus, $T(X)=c_{1}f(x_1)+\cdots +c_{K}f(x_K)\ge c_1\frac{3x_1^2-1}{2}+\cdots +c_K\frac{3x_K^2-1}{2}$ and $$T(X)\ge \frac{3}{2}[c_1{x}_1^2+c_2{x}_2^2+\cdots +c_K{x}_K^2]-\frac{1}{2}[c_1+c_2+\cdots +c_K]\ge \frac{3}{2}\frac{(x_1+x_2+\cdots +x_K{)}^2}{\frac{1}{c_1}+\frac{1}{c_2}+\cdots +\frac{1}{c_K}}-2n.$$ Since $c_{k+1}\ge 3c_k$ always holds, we have $$\frac{1}{c_1}+\frac{1}{c_2}+\cdots +\frac{1}{c_K}\le 1+\frac{1}{4}+\frac{1}{14}+\frac{1}{14\times 3}+\frac{1}{14\times 3^2}+\cdots =1+\frac{1}{4}+\frac{1.5}{14}\le 1.36$$ So $$T\ge \frac{3}{2}\frac{n^2}{1.36}-2n>1.1n^2-2n$$ To sum up, the optimization problem $♠$ has minimum value $T_{\min }\ge 1.1n^2-2n$, and for the original question, $$S(A)\ge \sum _{k=1}^{\infty }{c}_k\times f(|B_k|)\ge 1.1n^2-2n.$$