Maths Olympiad Prep

Track / Stage 7 / 99 of 300 #1499 of 1964

Problem 1499

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 a1a2⋯ana_1a_2\cdots a_n, then prove that
(a1a2⋯an)m−1≥(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.

Next problem →

Official solution

To prove the inequality (a1a2⋯an)m−1≥(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)1−1≥(1!)1  ⟹  1≥1 (a_1)^{1-1} \geq (1!)^1 \implies 1 \geq 1
which is true. Hence, the base case holds.

2. **General Case m≥2m \geq 2**:
- Assume m≥2m \geq 2. We need to show that (a1a2⋯an)m−1≥(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 an≤n2a_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 a1a2⋯ana_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 log⁡2(n)\log^2(n).

5. **Using ai≥i+n−1a_i \geq i + n - 1**:
- Given 1<a1<a2<…<an<2a11 < a_1 < a_2 < \ldots < a_n < 2a_1, we can infer that ai≥i+n−1a_i \geq i + n - 1 for all ii.
- This implies that the product a1a2⋯ana_1a_2\cdots a_n is bounded below by the product of these terms.

6. Combining the Results:
- We need to show that (a1a2⋯an)m−1≥(n!)m(a_1a_2\cdots a_n)^{m-1} \geq (n!)^m.
- Using the fact that ai≥i+n−1a_i \geq i + n - 1, we can write:
a1a2⋯an≥(1+n−1)(2+n−1)⋯(n+n−1)=n(n+1)(n+2)⋯(2n−1) 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 a1a2⋯ana_1a_2\cdots a_n.

7. Final Inequality:
- We need to show that:
(n(n+1)(n+2)⋯(2n−1))m−1≥(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 m≥log⁡2(n)m \geq \log^2(n).

Thus, we have shown that the inequality (a1a2⋯an)m−1≥(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 reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.