China National Team Selection Test

Proof For $a\in (\sqrt{n},\sqrt{2n}]$, $\text{lcm}(a,a+1)=a(a+1)>n$, so $|A\cap (\sqrt{n},\sqrt{2n}]|\le \frac{1}{2}(\sqrt{2}-1)\sqrt{n}+1$. For $a\in (\sqrt{2n},\sqrt{3n}]$, we have $$\text{lcm}(a,a+1)=a(a+1)>n,$$ $$\text{lcm}(a+1,a+2)=(a+1)(a+2)>n,$$ $$\text{lcm}(a,a+2)\ge \frac{1}{2}a(a+2)>n.$$ So $$|A\cap (\sqrt{2n},\sqrt{3n}]|\le \frac{1}{3}(\sqrt{3}-\sqrt{2})\sqrt{n}+1.$$ Similarly $$|A\cap (\sqrt{3n},2\sqrt{n}]|\le \frac{1}{4}(\sqrt{4}-\sqrt{3})\sqrt{n}+1.$$ Hence $$\begin{array}{rl}|A\cap [1,2\sqrt{n}]|& \le \sqrt{n}+\frac{1}{2}(\sqrt{2}-1)\sqrt{n}+\frac{1}{3}(\sqrt{3}-\sqrt{2})\sqrt{n}\\ & +\frac{1}{4}(\sqrt{4}-\sqrt{3})\sqrt{n}+3\\ & =\left(1+\frac{\sqrt{2}}{6}+\frac{\sqrt{3}}{12}\right)\sqrt{n}+3.\end{array}$$ Let $k\in {\mathbb{N}}^{\ast }$, suppose $a,b\in (\frac{n}{k+1},\frac{n}{k})$, $a>b$, and $\text{lcm}(a,b)=as=bt$, where $s,t\in {\mathbb{N}}^{\ast }$. Then $$\frac{a}{(a,b)s}=\frac{b}{(a,b)t}.$$ Since $\text{gcd}(\frac{a}{(a,b)},\frac{b}{(a,b)})=1$, so $\frac{b}{(a,b)}|s$. It follows that $$\begin{array}{rl}\mathrm{lcm}(a,b)& =as\ge \frac{ab}{(a,b)}\ge \frac{ab}{a-b}\\ & =b+\frac{b^2}{a-b}>\frac{n}{k+1}+\frac{{\left(\frac{n}{k+1}\right)}^2}{\frac{n}{k}-\frac{n}{k+1}}\\ & =n.\end{array}$$ Therefore, $|A\cap (\frac{n}{k+1},\frac{n}{k})|\le 1$. Suppose $T\in {\mathbb{N}}^{\ast }$ such that $\frac{n}{T+1}\le 2\sqrt{n}<\frac{n}{T}$. Then $$\begin{array}{rl}|A\cap (2\sqrt{n},n]|& \le \sum _{k=1}^T\left|A\cap \left(\frac{n}{k+1},\frac{n}{k}\right]\right|\\ & \le T<\frac{1}{2}\sqrt{n}.\end{array}$$ By the above arguments, we arrive at $$|A|\le \left(\frac{3}{2}+\frac{1}{6}\sqrt{2}+\frac{1}{12}\sqrt{3}\right)\sqrt{n}+3<1.9\sqrt{n}+5.$$