Maths Olympiad Prep

Library / /23 of 108

Number theory Difficulty 5.5 AIME, harder Prove it Mongolia

Given are mm positive integers such that 1a1a2am4001 \le a_1 \le a_2 \le \dots \le a_m \le 400. Show that m40m \le 40, if gcd(ai,aj)400\text{gcd}(a_i, a_j) \le 400 for all ii and jj (1i,jm1 \le i, j \le m).

Solution

First let us change the order: a1=bma_1 = b_m, a2=bm1a_2 = b_{m-1}, ..., am=b1a_m = b_1. Then we have 1bmbm1b2b14001 \le b_m \le b_{m-1} \le \dots \le b_2 \le b_1 \le 400. Let us show that bk400kb_k \le \frac{400}{k}, 1km1 \le k \le m. If k=1k=1, it is true.

For the induction step, we need to prove that bk+1400k+1b_{k+1} \le \frac{400}{k+1}. By the condition
bkbk+1(bk,bk+1)=bkbk+1[bk,bk+1]bkbk+1400 b_k - b_{k+1} \ge (b_k, b_{k+1}) = \frac{b_k \cdot b_{k+1}}{[b_k, b_{k+1}]} \ge \frac{b_k \cdot b_{k+1}}{400}
holds. From this inequality we have bk+1400bkbk+400=4001+400bk4001+kb_{k+1} \le \frac{400b_k}{b_k + 400} = \frac{400}{1 + \frac{400}{b_k}} \le \frac{400}{1+k}. Hence 400bkk\frac{400}{b_k} \ge k.

The 1bmbm1b2040020=201 \le b_m \le b_{m-1} \le \dots \le b_{20} \le \frac{400}{20} = 20. Since bib_i is integer for 1im1 \le i \le m, m40m \le 40.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.