The positive integers $a_1,a_2,...,a_n$ are such that $a_i<1000$ for all $i$. And $\mathrm{lcm}(a_i,a_j)>1000$ for all $i\neq j$. Then show that $$\sum_{i=1}^n\frac{1}{a_i}<2$$.
I am totally clueless on this one. Please help. All I have been able to do is show that $n\le 500$ as follows: There are $500$ odd numbers between $1-1000$. If there were $501$ or more, numbers than by pigeonhole principle one will divide the other which contradicts the lcm criteria i.e. $lcm(a_i,a_j)>1000>a_i$.
Erdős problem for soviet union Olympiad 1951. Let $N=1000$.
Hint: Notice that for each $1\leq i\leq n$ number of multiples of $a_i$ not larger than $N$ is $\lfloor N/a_i \rfloor$.
Using $\text{lcm}(a_i, a_j)>N$ prove that $\sum_{i=1}^n \lfloor N/a_i \rfloor \le N$.
Its easy to see that $\sum_{i=1}^n \{N/a_i\} < n$, where $\{\}$ is fractional part.
Adding the two inequalities above gives your answer.
If $\frac{1000}{m+1} < a < \frac{1000}{m}$ , then the $m$ multiples $a$, $2a$, . . . , $ma$ do not exceed $1000$. Let $k_1$ the number of $a_i$ in the interval $\left( \frac{1000}{2}, 1000\right]$, $k_2$ in $\left(\frac{1000}{3}, \frac{1000}{2} \right]$, etc. Then there are $k_1 + 2k_2 + 3k_3 + \dots$ integers, no greater than $1000$, that are multiples of at least one of the $a_i$. But the multiples are distinct, so $k_1 + 2k_2 + 3k_3 +\dots <1000 $
$$ 2k_1 + 3k_2 + 4k_3 + · · · = \\ (k_1 + 2k_2 + 3k_3 + · · · ) + (k_1 + k_2 + k_3 + · · · ) < 1000 + n < 2000$$
Therefore, $$\sum_{i=1}^{n} \frac{1}{a_i} \le k_1 \frac{2}{1000} + k_2 \frac{3}{1000} + k_3 \frac{4}{1000} + · · · = \frac{2k_1 + 3k_2 + 4k_3 + · · ·}{1000} < 2.$$
