Integers $a_1, a_2, \ldots, a_n$ satisfy $$1<a_1<a_2<\ldots < a_n < 2a_1.$$If $m$ is the number of distinct prime factors of $a_1a_2\cdots a_n$, then prove that $$(a_1a_2\cdots a_n)^{m-1}\geq (n!)^m.$$
Problem
Source: Polish Mathematical Olympiad Finals, Problem 3
Tags: number theory, Poland
06.04.2017 21:32
As a participant of Polish MO who saw the solution to this problem, I can honestly say, this is one of the hardest and most marvelous problems I've ever come across...
06.04.2017 21:39
And no one solved it during the contest, even the current IMO participants, so yes, this problem takes patience .
06.04.2017 23:51
If $m$ is 1, the result is obvious because $n$ must also be 1. Suppose $m\geq 2$. Here if $a_n > n^2$, the inequality can be directly proved. Otherwise we have $n$ positive integers below $n^2$ whose distinct prime factors are at most $m$ in total. From this one can show that $m \gg log(n)$, which again implies the inequality using $a_i \geq i+n-1$. Unfortunately I can't think of an elementary way to prove the crucial claim regarding the size of $m$. The theory of smooth numbers does tell us that in fact $m$ has to be as large as $log^2(n)$.
07.04.2017 00:31
Definitely, one of the most beautiful problems I have ever seen. I was so impressed when I saw the solution after the contest!
07.04.2017 00:32
Care posting it here?
07.04.2017 03:34
Maybe like this?
07.04.2017 12:30
This problem was proposed by Burii The idea is to write $a_i = p^{k_i} \cdot b_i$, where $p \nmid b_i$ for a prime divisor $p$ of $a_1a_2\ldots a_n$. Then, due to $a_1<a_2<\ldots<a_n<2a_1$ we get that $b_i$ are pairwise distinct. Thus $$b_1b_2\ldots b_n \ge n!$$ Multiplying such inequalities for each $p$ we get $(a_1a_2\ldots a_n)^{m-1} \ge (n!)^{m}$
10.04.2017 02:18
Beautiful!
06.12.2017 08:47
Awesome !!
06.12.2017 09:17
timon92 wrote: This problem was proposed by Burii The idea is to write $a_i = p^{k_i} \cdot b_i$, where $p \nmid b_i$ for a prime divisor $p$ of $a_1a_2\ldots a_n$. Then, due to $a_1<a_2<\ldots<a_n<2a_1$ we get that $b_i$ are pairwise distinct. Thus $$b_1b_2\ldots b_n \ge n!$$ Multiplying such inequalities for each $p$ we get $(a_1a_2\ldots a_n)^{m-1} \ge (n!)^{m}$
15.12.2017 00:44
Same idea as Imo shortlist 1985, identical
15.12.2017 02:00
angiland wrote: If $m$ is 1, the result is obvious because $n$ must also be 1. Suppose $m\geq 2$. Here if $a_n > n^2$, the inequality can be directly proved. Otherwise we have $n$ positive integers below $n^2$ whose distinct prime factors are at most $m$ in total. From this one can show that $m \gg log(n)$, which again implies the inequality using $a_i \geq i+n-1$. Unfortunately I can't think of an elementary way to prove the crucial claim regarding the size of $m$. The theory of smooth numbers does tell us that in fact $m$ has to be as large as $log^2(n)$. What's the difference between $>>$ and $>?$
15.12.2017 15:33
I don't understand is it the product of ${a}_{i}$ or what ?
13.05.2018 09:57
Just use the result here: https://artofproblemsolving.com/community/c6h364207p2000897