Let $ a_1<a_2<\cdots<a_n $ be positive integers such that for every distinct $1\leq{i,j}\leq{n}$ we have $ a_j-a_i $ divides $ a_i $. Prove that \[ ia_j\leq{ja_i} \qquad \text{ for } 1\leq{i}<j\leq{n} \]
Problem
Source:
Tags: inequalities, induction, number theory proposed, number theory
20.09.2010 18:14
Let $m$ be a positive integer, $1\le m\le n$. Define $k_i=\frac{a_i}{a_m-a_i}=\frac{a_m}{a_m-a_i}-1$. Since $a_1<a_2<\ldots<a_{m-1}$, we get $k_1<k_2<\ldots<k_{m-1}$. So $k_{m-1}\ge m-1$, $\frac{a_{m-1}}{a_m-a_{m-1}}\ge m-1$, $\frac{a_m}{a_{m-1}}\le\frac{m}{m-1}$. Therefore $\frac{a_j}{a_i}=\frac{a_j}{a_{j-1}}\cdot\frac{a_{j-1}}{a_{j-2}}\ldots\frac{a_{i+1}}{a_i}\le\frac{j}{j-1}\cdot\frac{j-1}{j-2}\ldots\frac{i+1}i=\frac{j}i$ and hence $ia_j\le ja_i$ as desired.
02.04.2011 18:21
Johan Gunardi wrote: Since $a_1<a_2<\ldots<a_{m-1}$, we get $k_1<k_2<\ldots<k_{m-1}$. Sorry, could you explain me this step? It's not so clear to me
03.04.2011 03:19
Note that we fixed $m$, so $a_1<\ldots<a_{m-1}\implies a_m-a_1>\ldots>a_m-a_{m-1}\implies\frac{a_m}{a_m-a_1}<\ldots<\frac{a_m}{a_m-a_{m-1}}\implies k_1<k_2<\ldots<k_{m-1}.$
15.04.2012 21:48
at first assume $j>i$ then $a_{j}-a_{i} | a_{i} \Rightarrow a_{j}=\frac{(k_{i}+1)a_{i}}{k_{i}}$ now assume $j>l>i$ $a_{j}=\frac{(k_{i}+1)a_{i}}{k_{i}}$ $a_{j}=\frac{(k_{l}+1)a_{l}}{k_{l}}$ so $\frac{(k_{l}+1)a_{l}}{k_{l}}= \frac{(k_{i}+1)a_{i}}{k_{i}}$ and we know $a_{l}>a_{i}$ we get $ \frac {k_{i}+1}{k_{i}} > \frac {k_{l}+1}{k_{l}} \Rightarrow k_{l} > k_{i}$ and we know that $\min k_{1}=1 $ so by easy induction we can show $k_{i} \geq i $ now go to the problem we have : $ia_{j}\leq ja_{i} \Leftrightarrow \frac{(k_{i}+1)a_{i}}{k_{i}} \leq ja_{i}\Leftrightarrow i(k_{i}+1) \leq jk_{i} \Leftrightarrow i \leq k_{i}(j-i) , i \leq k_{i} \Leftrightarrow i \leq i(j-i) \Leftrightarrow 1 \leq j-i $ and its true because $j>i $ and both are positive integer . solution
27.04.2012 16:11
Solution : Let for $1\leq{c}\leq{n}$ , $a_{c}=(a_{c}-a_{1})l_{1}$ , $a_{c}=(a_{c}-a_{2})l_{2}$ , ... , $a_{c}=(a_{c}-a_{c-1})l_{c-1}$ , $a_{c}-a_{1}>a_{c}-a_{2}>...>a_{c}-a_{c-1}$ , so $2\leq l_{1}<l_{2}<...<l_{c-1}$ , so $c\leq l_{c-1}$ , so $a_{c}\ge c(a_{c}-a_{c-1})$ , $ca_{c-1}\ge a_{c}(c-1)$ , so $ja_{j-1}\ge a_{j}(j-1)$ , $(j-1)a_{j-2}\ge a_{j-1}(j-2)$ , ... , $(i+1)a_{i}\ge a_{i+1}(i)$ , so if we multiply all this , then we get $(i+1)(i+2)...ja_{i}a_{i+2}...a_{j-1}\ge i(i+1)...(j-1)a_{i+1}a_{i+2}...a_{j}$ , so $ja_{i}\ge ia_{j}$ . done
09.01.2022 14:37
aj - ai | ai ---> k(aj - ai) = ai ---> k(aj) = k+1(ai) ---> ai / aj = k / k+1 ≥ i / j.
26.11.2023 21:38
Mahdi_Mashayekhi wrote: aj - ai | ai ---> k(aj - ai) = ai ---> k(aj) = k+1(ai) ---> ai / aj = k / k+1 ≥ i / j. Hello, would you explain the last step? since for k=3 i=6 j=7, as an example, the inequality does't hold.