Maths Olympiad Prep

Library / /5 of 38

Combinatorics Difficulty 6.2 National olympiad Prove it China

Suppose that positive integers a1,a2,,a2006a_1, a_2, \dots, a_{2\,006} (some of them may be equal) satisfy the condition: any two of a1a2,a2a3,,a2005a2006\frac{a_1}{a_2}, \frac{a_2}{a_3}, \dots, \frac{a_{2\,005}}{a_{2\,006}} are unequal. At least how many different numbers are there in {a1,a2,,a2006}\{a_1, a_2, \dots, a_{2\,006}\}? (posed by Chen Yonggao)

Solution

With 45 different positive integers we can only get 45×44+1=198145 \times 44 + 1 = 1\,981 fractions. So there are more than 45 different numbers in {a1,a2,,a2006}\{a_1, a_2, \dots, a_{2\,006}\}.

On the other hand, let p1,p2,,p46p_1, p_2, \dots, p_{46} be 46 different prime. Set a1,a2,,a2006a_1, a_2, \dots, a_{2\,006} to be:
p1,p1,p2,p1,p3,p2,p3,p1,p4,p3,p4,p2,p4,p1, p1,pk,pk1,pk,pk2,pk,,pk,p2,pk,p1, p1,p45,p44,p45,p43,p45,,p45,p2,p45,p1, p46,p45,p46,p44,p46,,p46,p22,p46. \begin{align*} p_1, p_1, p_2, p_1, p_3, p_2, p_3, p_1, p_4, p_3, p_4, p_2, p_4, p_1, \ p_1, p_k, p_{k-1}, p_k, p_{k-2}, p_k, \dots, p_k, p_2, p_k, p_1, \ p_1, p_{45}, p_{44}, p_{45}, p_{43}, p_{45}, \dots, p_{45}, p_2, p_{45}, p_1, \ p_{46}, p_{45}, p_{46}, p_{44}, p_{46}, \dots, p_{46}, p_{22}, p_{46}. \end{align*}
Then the 2 006 positive numbers satisfy that any two of a1a2,a2a3,,a2005a2006\frac{a_1}{a_2}, \frac{a_2}{a_3}, \dots, \frac{a_{2\,005}}{a_{2\,006}} are unequal.
So the answer is 46.

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 and solution reproduced as published; topic and difficulty added by this site.