Maths Olympiad Prep

Library / /415 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

Let a1,a2,,a2000a_1,a_2,\cdots,a_{2000} be distinct positive integers such that 1a1<a2<<a2000<40001 \leq a_1 < a_2 < \cdots < a_{2000} < 4000 such that the LCM (least common multiple) of any two of them is 4000\geq 4000. Show that a11334a_1 \geq 1334

Solution

1. Restate the problem in a general form:
Let a1,a2,,an a_1, a_2, \ldots, a_n be distinct positive integers such that 1a1<a2<<an<2n 1 \leq a_1 < a_2 < \cdots < a_n < 2n and the least common multiple (LCM) of any two of them is 2n\geq 2n. We need to show that a12n3 a_1 \geq \left\lfloor \frac{2n}{3} \right\rfloor .

2. Initial observation:
Note that if aiaj a_i \mid a_j for any ij i \neq j , then LCM(ai,aj)=aj<2n\text{LCM}(a_i, a_j) = a_j < 2n, which contradicts the given condition. Therefore, no ai a_i can be a divisor of another aj a_j .

3. **Consider sequences of the form 2ki 2^k \cdot i :**
We consider sequences A1,A3,,A2n1 A_1, A_3, \ldots, A_{2n-1} , where Ai A_i contains all positive integers less than 2n 2n of the form 2ki 2^k \cdot i with i i being an odd number and k k a non-negative integer. These sequences cover all integers from 1 1 to 2n1 2n-1 .

4. **Distribution of ai a_i in sequences:**
There are exactly n n such sequences. If there exist distinct ai a_i and aj a_j in the same sequence, one must divide the other, which is a contradiction. Hence, each sequence Ai A_i contains exactly one ai a_i .

5. **Odd numbers greater than or equal to n n :**
The sequences Ak A_k where k k is an odd number n\geq n have only one element each. Therefore, the set {ai} \{a_i\} contains all odd numbers greater than or equal to n n .

6. **Contradiction if a1<2n3 a_1 < \left\lfloor \frac{2n}{3} \right\rfloor :**
Suppose a1<2n3 a_1 < \left\lfloor \frac{2n}{3} \right\rfloor . We consider two cases:

**Case 1: a1 a_1 is odd**
- Consider the sequence 3a1,5a1, 3a_1, 5a_1, \ldots . The difference between any two terms is 2a1 2a_1 , so any a1 a_1 consecutive odd numbers contain one of 3a1,5a1, 3a_1, 5a_1, \ldots .
- If a1<n2 a_1 < \frac{n}{2} , there are at least n2 \frac{n}{2} odd numbers from n n to 2n 2n . Thus, there exists some aj a_j such that aj a_j is an odd multiple of a1 a_1 , which is a contradiction.
- If a1n2 a_1 \geq \frac{n}{2} , then 3a13n2 3a_1 \geq \frac{3n}{2} , which lies between n n and 2n 2n , leading to another contradiction.

**Case 2: a1 a_1 is even**
- Let a1=2km a_1 = 2^k \cdot m where m m is an odd integer. Note that mn3 m \leq \frac{n}{3} .
- Consider the element aj a_j in the sequence A3m A_{3m} , and let aj=2t3m a_j = 2^t \cdot 3m .
- If k>t k > t , then LCM(a1,aj)=2k3m=3aj<2n\text{LCM}(a_1, a_j) = 2^k \cdot 3m = 3a_j < 2n. If kt k \leq t , then LCM(a1,aj)=aj<2n\text{LCM}(a_1, a_j) = a_j < 2n. Both cases yield a contradiction.

7. Conclusion:
Hence, a12n3 a_1 \geq \left\lfloor \frac{2n}{3} \right\rfloor .

The final answer is a11334 \boxed{ a_1 \geq 1334 } .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.