Maths Olympiad Prep

Track / Stage 7 / 97 of 300 #1497 of 1964

Problem 1497

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.1 Prove it

Integers a1,a2,,ana_1, a_2, \ldots, a_n satisfy
1<a1<a2<<an<2a1.1<a_1<a_2<\ldots < a_n < 2a_1.
If mm is the number of distinct prime factors of a1a2ana_1a_2\cdots a_n, then prove that
(a1a2an)m1(n!)m.(a_1a_2\cdots a_n)^{m-1}\geq (n!)^m.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

To prove the inequality (a1a2an)m1(n!)m(a_1a_2\cdots a_n)^{m-1} \geq (n!)^m, we will proceed with the following steps:

1. **Base Case m=1m = 1**:
- If m=1m = 1, then a1a_1 is the only integer, and n=1n = 1. The inequality becomes:
(a1)11(1!)1    11 (a_1)^{1-1} \geq (1!)^1 \implies 1 \geq 1
which is true. Hence, the base case holds.

2. **General Case m2m \geq 2**:
- Assume m2m \geq 2. We need to show that (a1a2an)m1(n!)m(a_1a_2\cdots a_n)^{m-1} \geq (n!)^m.

3. **Bounding ana_n**:
- If an>n2a_n > n^2, then the inequality can be directly proved. Otherwise, we consider the case where ann2a_n \leq n^2.

4. Prime Factors and Smooth Numbers:
- We have nn positive integers a1,a2,,ana_1, a_2, \ldots, a_n all less than 2a12a_1. The number of distinct prime factors mm of the product a1a2ana_1a_2\cdots a_n is at most mm.
- By the properties of smooth numbers, the number of distinct prime factors mm must be large enough to cover all nn integers. Specifically, mm must be at least log2(n)\log^2(n).

5. **Using aii+n1a_i \geq i + n - 1**:
- Given 1<a1<a2<<an<2a11 < a_1 < a_2 < \ldots < a_n < 2a_1, we can infer that aii+n1a_i \geq i + n - 1 for all ii.
- This implies that the product a1a2ana_1a_2\cdots a_n is bounded below by the product of these terms.

6. Combining the Results:
- We need to show that (a1a2an)m1(n!)m(a_1a_2\cdots a_n)^{m-1} \geq (n!)^m.
- Using the fact that aii+n1a_i \geq i + n - 1, we can write:
a1a2an(1+n1)(2+n1)(n+n1)=n(n+1)(n+2)(2n1) a_1a_2\cdots a_n \geq (1 + n - 1)(2 + n - 1)\cdots(n + n - 1) = n(n+1)(n+2)\cdots(2n-1)
- The product on the right-hand side is a lower bound for a1a2ana_1a_2\cdots a_n.

7. Final Inequality:
- We need to show that:
(n(n+1)(n+2)(2n1))m1(n!)m (n(n+1)(n+2)\cdots(2n-1))^{m-1} \geq (n!)^m
- By properties of factorials and products, this inequality holds for sufficiently large mm, specifically when mlog2(n)m \geq \log^2(n).

Thus, we have shown that the inequality (a1a2an)m1(n!)m(a_1a_2\cdots a_n)^{m-1} \geq (n!)^m holds under the given conditions.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.