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

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

• This is for Erdős ! Commented Jun 5, 2017 at 5:29
• I don't follow your argument about 500 odd numbers. $\mbox{lcm}(7,21) = 21$ since $7|21$ and both are odd; similarly $\mbox{lcm}(6,500) = 1500$ and $6\not| 500$. Commented Jun 5, 2017 at 5:49
• $n$ can be any positive integer? Commented Jun 5, 2017 at 6:23
• so the conclusion is not true fot $n>500$ Commented Jun 5, 2017 at 6:48
• Yes the conclusion is false for $n>500$, I showed that (if my argument is correct which I think it is).
– user428700
Commented Jun 5, 2017 at 6:49

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.

• Did Erdos propose it to USSR?
– user428700
Commented Jun 5, 2017 at 9:35
• Yes, In original problem $N$ was $1951$. Commented Jun 5, 2017 at 9:50

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

• I don't understand the meaning of the statement "Then there are...one of the $a_i$" can you please elaborate.
– user428700
Commented Jun 5, 2017 at 13:40