Maths Olympiad Prep

Library / /7 of 53

Combinatorics Difficulty 5.2 AIME, harder Prove it China

Let mm and nn be positive integers with m>n2m > n \ge 2. Set S={1,2,,m}S = \{1, 2, \dots, m\}, and T={a1,a2,,an}T = \{a_1, a_2, \dots, a_n\} is a subset of SS such that every element in SS is divisible by at most one element in TT. Prove that
1a1+1a2++1an<m+nm. \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n} < \frac{m+n}{m}.

Solution

For every ii with 1in1 \le i \le n, we define set
Si={bb is an element in S and is divisible by ai}. S_i = \{b \mid b \text{ is an element in } S \text{ and is divisible by } a_i\}.
There are mai\lfloor \frac{m}{a_i} \rfloor elements in SiS_i. Since every element in SS is not divisible by any two distinct elements in TT, it follows that SiSj=S_i \cap S_j = \emptyset for 1i<jn1 \le i < j \le n. Thus
i=1nmai=i=1nSiS=m. \sum_{i=1}^{n} \lfloor \frac{m}{a_i} \rfloor = \sum_{i=1}^{n} |S_i| \le |S| = m.
Note that mai<mai+1\frac{m}{a_i} < \lfloor \frac{m}{a_i} \rfloor + 1. It follows that
i=1nmai<i=1n(mai+1)=i=1nmai+i=1n1m+n. \sum_{i=1}^{n} \frac{m}{a_i} < \sum_{i=1}^{n} (\lfloor \frac{m}{a_i} \rfloor + 1) = \sum_{i=1}^{n} \lfloor \frac{m}{a_i} \rfloor + \sum_{i=1}^{n} 1 \le m + n.
So the desired result is obtained.

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.