China National Team Selection Test

We prove this problem by contradiction. If the conclusion of the problem is not true, then there exists $i_0$, and we have $(a_i, a_{i+1}) > \frac{3}{4}i$ for $i \ge i_0$.

Take a positive number $M > i_0$, so if $i \ge 4M$, then $(a_i, a_{i+1}) > \frac{3}{4}i \ge 3M$.

So, if $i \ge 4M$, $a_i \ge (a_i, a_{i+1}) > 3M$, then $\{1, 2, \dots, 3M\} \subseteq \{a_1, a_2, \dots, a_{4M-1}\}$.

Hence
$$\left| \{1, 2, \dots, 3M\} \cap \{a_{2M}, a_{2M+1}, \dots, a_{4M-1}\} \right| \ge 3M - (2M - 1) = M + 1.$$
By Dirichlet's Drawer Principle, there exists $2M \le j_0 < 4M$ such that $a_{j_0}, a_{j_0+1} \le 3M$. Thus,
$$(a_{j_0}, a_{j_0+1}) \le \frac{1}{2} \max\{a_{j_0}, a_{j_0+1}\} \le \frac{3M}{2} = \frac{3}{4} \cdot 2M \le \frac{3}{4} j_0,$$
which is a contradiction. □