2022 China Team Selection Test for IMO

Proof. For $n\ge 25$, write $5^{2t}\le n<5^{2t+2}$ for $t\in {\mathbb{N}}^{\ast }$. Take the set $$A=\{({\alpha }_{2t},\dots ,{\alpha }_1{)}_5\mid {\alpha }_{2i}\in \{0,1,2,3,4\}\text{ and }{\alpha }_{2i-1}\in \{1,3\}\text{ for }i=1,\dots ,t\},$$ where $({\alpha }_{2t},\dots ,{\alpha }_1{)}_5$ denotes the number $m=5^{2t-1}{\alpha }_{2t}+\cdots +5{\alpha }_2+{\alpha }_1$ in quinary. It is obvious that $A\subset \{1,2,\dots ,n\}$. For each pair of integers $u_1,u_2\in A$, write $u_1=(a_{2t},\dots ,a_1)$ and $u_2=(b_{2t},\dots ,b_1)$. We may assume $u_1>u_2$ and consider $u_1-u_2$. Now let $s$ be the minimal index such that $a_s\ne b_s$. Namely, we have $a_1=b_1,\dots ,a_{s-1}=b_{s-1},a_s\ne b_s$. Note that in this case, $u_1-u_2=(a_{2t}-b_{2t})5^{2t-1}+\cdots +(a_s-b_s)5^{s-1}$. If $2\mid s$, then $5^{s-1}\mid (u_1-u_2)$ i.e., $a_s-b_s\ne 0$ and $-4\le a_s-b_s\le 4$. Hence $u_1-u_2$ cannot be a perfect square. If $2\nmid s$, then $\frac{u_1-u_2}{5^{s-1}}=(a_{2t}-b_{2t})5^{2t-1}+\cdots +(a_s-b_s)\in \mathbb{Z}$. Suppose that $u_1-u_2$ is a perfect square, then $\frac{u_1-u_2}{5^{s-1}}$ is a perfect square as well. On the other hand, the condition $2\mid s-1$ and $a_s\ne b_s$ implies that $\{a_s,b_s\}=\{1,3\}$ and $\frac{u_1-u_2}{5^{s-1}}\equiv 2,3(\mathrm{mod}5)$, which can never be a perfect square. This is a contradiction. Thus for any distinct element $u_1,u_2\in A$, the number $|u_1-u_2|$ is not a perfect square. Hence $A$ satisfies the requirement. Also, note that $|A|=10^t$. Since $\alpha ={\log }_{25}10>1/2$, we obtain $$n^{\alpha }<5^{(2t+2){\log }_{25}10}=10^{t+1}=10|A|.$$ So it suffices to take $C=\frac{1}{24}$ and $\alpha ={\log }_{25}10\in (0,1)$. As for $n\le 24$, we may take $A=\{1\}$ and then $|A|\ge \frac{1}{24}n\ge \frac{1}{24}{n}^{\alpha }$. To sum up, for all $n\in {\mathbb{N}}^{\ast }$, one can find a desired subset $A$ with $|A|\ge C{n}^{\alpha }$.