Given some positive integers less than $1951$, where each two have a lowest common multiple greater than $1951$

algebra-precalculuscontest-math

Given some positive integers less than $1951$, where each two have a lowest common multiple greater than $1951$. We need to show that sum of the reciprocals of these numbers is less than $2$

I don't have any work of mine to show on this problem, i have no idea where to start.
I'd appreciate any hints on how to progress upon this

Best Answer

Hint: Here's the high-level idea:

  1. Create a well-defined "function" $f: \{ 1, 2, \ldots 1951\} \rightarrow \{ a_1, a_2, \ldots a_n \}$.
    It is a "function" because not all $n$ need to map to an $a_i$.

  2. The preimage of $a_i$ has $\approx \frac{1951}{a_i}$ terms.

  3. The sum of the sizes of the preimage is less than the domain of the "function".
    This gives us an upper bound on $ \sum \approx \frac{1951}{a_i} $, which is close to what the question is asking for. We just have to massage it enough to get the actual upper bound.

With this in mind, what function should we try?

2:

Preimage of $a_i$ has $ \approx \frac{1951}{a_i}$ terms suggests that $f(k a_i ) = a_i$.

1: We verify that this mapping works

If for some $f(n) = a_i, a_j$, then $ a_i, a_j \mid n $ and $lcm (a_i, a_j ) \mid n $ which is a contradiction.
Thus, at most one $a_i$ will divide $n$, and we say $f(n) = a_i$.

3:

The preimage of $a_i$ is the values that are multiples of $a_i$, so there are $ \lfloor \frac{1951} { a_i } \rfloor$ of them.

This tells us that $\sum \lfloor \frac{1951} { a_i } \rfloor \leq 1951$.
There's a bit of work here, which I'd leave you to fill in the gap.
In particular, while $ \frac{1951}{n} \geq \lfloor \frac{1951}{n} \rfloor $, that inequality isn't in the direction that we want.

Show that it further implies $ \sum \frac{1}{a_i} \leq 2 $.

Notes

  • 1951 is prime so that avoids "is greater strictly greater than or greater than or equal to" ambiguity in the phrasing of the question. In particular, I'm going with the "less/greater than or equal to" interpretation.
Related Question