China National Team Selection Test

Question

Let a_1, a_2, be a permutation of all positive integers. Prove that there exist infinite positive integers i's, such that (a_i, a_i+1) 34i. (posed by Chen Yonggao)

Accepted Answer

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 \geq i_{0}

.

Take a positive number

M > i_{0}

, so if

i \geq 4 M

, then

(a_{i}, a_{i + 1}) > \frac{3}{4} i \geq 3 M

.

So, if

i \geq 4 M

,

a_{i} \geq (a_{i}, a_{i + 1}) > 3 M

, then

{1, 2, \dots, 3 M} \subseteq {a_{1}, a_{2}, \dots, a_{4 M - 1}}

.

Hence

∣ {1, 2, \dots, 3 M} \cap {a_{2 M}, a_{2 M + 1}, \dots, a_{4 M - 1}} ∣ \geq 3 M - (2 M - 1) = M + 1.

By Dirichlet's Drawer Principle, there exists

2 M \leq j_{0} < 4 M

such that

a_{j_{0}}, a_{j_{0} + 1} \leq 3 M

. Thus,

(a_{j_{0}}, a_{j_{0} + 1}) \leq \frac{1}{2} max {a_{j_{0}}, a_{j_{0} + 1}} \leq \frac{3 M}{2} = \frac{3}{4} \cdot 2 M \leq \frac{3}{4} j_{0},

which is a contradiction. □