Number Theory – Combinatorics Style Problems

Question

I am unsure of the source of this problem, but i was wondering if anybody had any ideas:

Let $S$ a set of $41$ distinct positive integers, prove that there exists at least one pair of integers in $S$ with lowest common multiple larger than $400$.

I have managed to prove that the largest number in $S$ is no more than $200$, because let $x>200$ be the largest number in $S$ and then since there is at least one number thats not a factor of $x$ (since the 3 digit number with the most factors was 840 i recall) so then the lcm must be atleast $2x>400$. However, not much other progress.

I was wondering anybody could offer any help on this problem.

Answer 1

Longwinded answer that explains how to work towards a solution.
In 5.2, we present the actual solution, so skip ahead if desired.
In 5.3, we strengthen the hypothesis to 38 distinct integers. (Reza showed it for 36 distinct integers.)
In 6, we generalize the problem.

Proof by contradiction. Suppose that the LCM is $\leq 400$.
Let the 41 distinct integers be $a_i$ arranged in increasing order.

1. Note that OP showed that $a_{41} < 200$.
   • This was obtained by manual verification that any integer from 200 to 400 had fewer than 40 factors. It may not be easily generalizable.
2. It is well known that $\gcd(a, b) lcm(a, b) = ab$.
   • This gives us a way to bound $lcm(a, b) = \frac{ab}{\gcd(a, b) }$, so we need an upper bound for $ \gcd(a, b)$.
3. A trivial upper bound is that for $ a < b$, $ \gcd (a, b) \leq b - a$
   • Proof via the Euclidean algorithm, or obviousness.
   • If we can't push through the solution, we could come back and revisit this bound and see if we could tighten it up more. (Doesn't seem that likely though)
4. Observe that $ 400 = 20 \times 20 = \frac{40 \times 40}{4} $. This suggests that:
   1. We need to focus on the larger values.
      Looking at $a_1$ to $a_{20}\geq 20$ might not be enough to trigger a contradiction.
      If we can't push through the solution, we can revisit this decision of ignoring the smaller values.
   2. We have $ a_{41} \geq 41$.
      With $a_{40}\geq 40$, we get $ \gcd(a_{40}, a_{41}) \geq \frac{40 \times 41 } { 400 }$ so $a_{41} - a_{40} \geq \gcd(a_{40}, a_{41} ) \geq 5$. This in turn increases the bound $a_{41} \geq a_{40} + 5 \geq 45.$.
      Likewise, with $a_{39} \geq 39$, since $\gcd(a_{39}, a_{40} ) \geq \frac{ 39\times 40 } { 400}$, so $a_{40} \geq 39 + (a_{40} - a_{39} ) + (a_{41} - a_{40} ) \geq 48$.
      We can continue this manually, leading to Reza's solution, starting from $a_{20} \geq 20$.
5. How can we simplify the argument without tracking individual values?
   1. Let's take a slight detour into making this a continuous problem, namely that if we let $f(i) = a_i$, then $f' \geq \frac{f^2}{400}$. Show that the solution to $f' = \frac{f^2}{400}$ is $f = - \frac{400}{c + x}$. So if $ f(20) \geq 20$, then $ -20 < c < -40$, and then $ f(40) \rightarrow \infty$. This gives us confidence that $f(40) $ will be "too large"
   2. To discretize this idea, observe that $400 \geq \frac{a_{i+1}a_i}{a_{i+1} - a_i} \Leftrightarrow \frac{1}{a_i} - \frac{1}{a_{i+1}} \geq \frac{1}{400}$. So we have the contradiction (with 40 integers) that $$\frac{20}{400} \leq \sum_{i=1}^{20} \frac{1}{a_{19+i}} - \frac{1}{a_{19+i+1}} = \frac{1}{a_{20}} - \frac{1}{a_{40}} < \frac{ 1}{a_{20}} \leq \frac{1}{20}.$$
   3. Note that since OP indicated $a_i < 200$, we could strengthen the hypothesis to 38 integers, and reach the contradiction

$$\frac{18}{400} \leq \sum_{i=1}^{18} \frac{1}{a_{19+i}} - \frac{1}{a_{19+i+1}} = \frac{1}{a_{20}} - \frac{1}{a_{38}} < \frac{1}{20} - \frac{1}{200} = \frac{18}{400}.$$

6. This allows us to generalize the problem to showing that out of $2n$ integers, there must be 2 whose LCM is $\geq n^2$.
   • Of course, this bound could be tightened further. I'm guessing that we could get it towards $ \geq 3 n^2$ or even $\geq 4n^2-2n$.
   • Note that $4n^2 - 2n$ is obtained via the first $2n$ integers.