Prove that there exists a real number $C > 1$ with the following property. Whenever $n > 1$ and $a_0 < a_1 < a_2 <\cdots < a_n$ are positive integers such that $\frac{1}{a_0},\frac{1}{a_1} \cdots \frac{1}{a_n}$ form an arithmetic progression, then $a_0 > C^n$.
Problem
Source: CIIM 2015, India Postal Coaching 2015
Tags: number theory, bounded
Satyaprakash2009rta
04.12.2015 16:18
Put $lcm(a_0,a_1,\dots,a_n)=q$ and $\frac1{a_i}=\frac{r_i}{q}$, then $r_0>r_1>\dots>r_n$ is an arithmetic sequence and $q/r_i=a_i$ $\implies$ $r_i|q$ for each $i$. So we have $a_0=\frac{q}{r_0}$ where $lcm(r_0,r_1,\dots,r_n)|q$. So $a_0\ge \frac{lcm(r_0,r_1,\dots,r_n)}{r_0}$. Now we wish to estimate $\frac{lcm(r_0,r_1,\dots,r_n)}{r_0}$. This follows from the following lemma (easy to prove using reasoning similar to Legendre's formula): if $0<u_1<u_2<\dots$ is an arithmetic progression of integers relatively prime to its difference, and $L=lcm(u_1,u_2,\dots,u_n)$, $T=\frac{u_1u_2\dots u_n}{n!}$, then for any prime $p$, $v_p(T)\le v_p(L)$, and as a corollary, $T\le L$.
Let $q$ be some prime power. Then $q$ divides exactly $[n/q]+1$ numbers amongst $u_1,u_2,\dots,u_{q([n/q]+1)}$, and it divides exactly $[n/q]$ numbers amongst $1,2,\dots,n$.
Let $p$ be any prime. Note that $v_p(T)=\sum_{k\ge 1}x_k$, where $x_k=|\{1\le i\le n:p^k\mid u_i\}|-|\{1\le i\le n:p^k\mid i\}|$. We have just proven that $x_k\le 1$ for any $k$, and also, if $k>v_p(L)$, then $x_k\le 0$, because $p^k$ doesn't divide any of the $u_i$'s. It follows that $v_p(T)=\sum_{k\ge 1} x_k\le v_p(L)$.
Claim: for any arithmetic sequence $r_0,r_1,\dots,r_n>0$, we have $\frac{lcm(r_0,r_1,\dots,r_n)}{r_0}\ge \frac{r_1r_2r_3\dots r_{[n/2]}}{([n/2]+1)!}$.
WLOG $gcd(r_0,r_0-r_1)=1$, because we may divide through by the gcd of the sequence.
Now the claim follows from the Lemma applied to the sequence $r_0,r_1,\dots,r_{[n/2]}$.
From here, we are done, because $\frac{r_1r_2r_3\dots r_{[n/2]}}{([n/2]+1)!}\ge \binom{n}{[n/2]}>\frac{2^n}{n+1}$
Satyaprakash2009rta
04.12.2015 16:24
btw here is the official solution from KOMAL http://www.komal.hu/verseny/feladat.cgi?a=feladat&f=A652&l=en
i_atmmaths
04.12.2015 16:35
can anyone please give me the details of this competition?
Satyaprakash2009rta
04.12.2015 16:37
i_atmmaths wrote: can anyone please give me the details of this competition? Which competiotion? Do you mean KOMAL?
i_atmmaths
04.12.2015 16:52
Satyaprakash2009rta wrote: i_atmmaths wrote: can anyone please give me the details of this competition? Which competiotion? Do you mean KOMAL? yes
Satyaprakash2009rta
04.12.2015 16:56
You can visit to its official website. http://www.komal.hu