1900's Soviet Math Competition - Integers less than $1000$.

Solution 1:

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.

Solution 2:

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.$$