Iranian Mathematical Olympiad

First we prove a lemma.

Lemma. Let $a>b$ be two positive integers such that $\frac{a}{b}>4$. Then there exist some positive integer $l$ such that $b<\varphi (2^l)=2^{l-1}<2^l<a$.

Proof of lemma. There exists some positive integer $m$ such that $2^{m-1}\le b<2^m$. So $a>4b\ge 2^{m+1}$ and hence for $l=m+1$ we have $b<2^{l-1}<2^l<a$, as claimed. $\square$

We construct the sequence in the problem inductively. The assertion for $n=1$ is obvious. Now, suppose that $a_1<a_2<\cdots <a_n$ is a sequence such that $\varphi (a_1)>\varphi (a_2)>\cdots >\varphi (a_n)$. Let $p_N$ be the greatest prime factor of $a_i$'s ($p_j$ is the $j$th prime number), $1\le i\le n$. Since for every $x$ with prime factors greater than $p_N$, the greatest common divisor of $x$ and $a_i$ is 1 for all $1\le i\le n$, we deduce that the sequence $a_{1}x<a_{2}x<\cdots <a_{n}x$ also satisfies the condition of the problem (because $\varphi (a_{i}x)=\varphi (a_i)\varphi (x)$). Now, our goal is to find such $x$ and some positive integer $y$ such that $y<a_{1}x$ and $\varphi (y)>\varphi (a_{1}x)$. First we claim that there is a positive integer $x$ with prime factors greater than $p_N$ such that $\frac{a_{1}x}{\varphi (a_1)\varphi (x)}>4$ or equivalently, $\frac{x}{\varphi (x)}>4\frac{\varphi (a_1)}{a_1}$.

To prove this, let $x_m=p_{N+1}{p}_{N+2}\dots p_{N+m}$ ($m\in \mathbb{N}$). We have $$\frac{x_m}{\varphi (x_m)}=\prod _{i=N+1}^{N+m}\frac{p_i}{p_i-1}=\prod _{i=N+1}^{N+m}\left(1+\frac{1}{p_i-1}\right)\ge \sum _{i=N+1}^{N+m}\frac{1}{p_i-1}.$$ The sum ${\sum }_{i=N+1}^{\infty }\frac{1}{p_i-1}>{\sum }_{i=N+1}^{\infty }\frac{1}{p_i}$ diverges by a well-known fact, so we can find $m$ such that $\frac{x_m}{\varphi (x_m)}>4\frac{\varphi (a_1)}{a_1}$. We let $x=x_m$. Now, since $\frac{a_{1}x}{\varphi (a_1)\varphi (x)}>4$, according to the lemma there is some positive integer $l$ such that $\varphi (a_{1}x)<\varphi (2^l)<2^l<a_{1}x$. So putting $y=2^l$ leads to the new sequence $$y<a_{1}x<a_{2}x<\cdots <a_{n}x$$ which has $n+1$ terms and satisfies the problem's condition. $\square$