Iranian Mathematical Olympiad

First we prove some lemmas.

Lemma 1. $a_n\ge 3$ for all natural numbers $n\ge 3$. Proof. Suppose that $a_n<3$ for some natural number $n\ge 3$. If $a_{n-1}\ge a_{n-2}$, then $$\frac{2a_{n-1}}{a_{n-2}}\ge 2\Rightarrow \left[\frac{2a_{n-1}}{a_{n-2}}\right]\ge 2\Rightarrow \left[\frac{2a_{n-2}}{a_{n-1}}\right]=0\Rightarrow a_{n-1}>2a_{n-2}\Rightarrow \frac{2a_{n-1}}{a_{n-2}}>4.$$ This is a contradiction since $a_n<3$. If $a_{n-2}\ge a_{n-1}$, the proof is similar to the former case because the recursive relation for $a_n$ is symmetric with respect to both $a_{n-1}$ and $a_{n-2}$. $\square$

Lemma 2. For each natural number $n\ge 3$, $$a_{n+1}=a_n,\text{ or }{a}_{n+2}<\max \{a_n,a_{n+1}\}.$$ Proof. Suppose that $a_{n+1}\ne a_n$ for some $n\in \mathbb{N}$. If $a_n=\max \{a_n,a_{n+1}\}$, $\frac{2a_{n+1}}{a_n}<2$. On the other hand, $$a_{n+1},a_n\ge 3\Rightarrow \frac{2a_n}{a_{n+1}}\le \frac{2a_n}{3}\Rightarrow a_{n+2}=\left[\frac{2a_{n+1}}{a_n}\right]+\left[\frac{2a_n}{a_{n+1}}\right]\le 1+\frac{2a_n}{3}\le \frac{a_n}{3}+\frac{2a_n}{3}=a_n.$$

Now, if $a_{n+2}\ge \max \{a_n,a_{n+1}\}=a_n$, the above inequalities will become equalities; therefore, $a_n=a_{n+1}=3$ which contradicts our assumption $a_n\ne a_{n+1}$. The case $a_{n+1}=\max \{a_n,a_{n+1}\}$ is proved similarly. $\square$

Lemma 3. There exists some natural number $k$ such that $a_k=a_{k+1}$. Proof. Assume to the contrary that the equality never holds, hence by lemma 2 $a_{n+2}<\max \{a_n,a_{n+1}\},$ and $a_{n+3}<\max \{a_{n+1},a_{n+2}\}<\max \{a_n,a_{n+1}\}.$ Therefore, $\max \{a_{n+2},a_{n+3}\}<\max \{a_n,a_{n+1}\}.$ Thus $\max \{a_{2k},a_{2k+1}\}$ is a strictly decreasing sequence of natural numbers. But there is no such sequence; therefore, our initial assumption is not true and the lemma is proved. $\square$

By lemma 3, there exists some natural number $k\ge 1$ such that $a_k=a_{k+1}$. This implies that $a_{k+2}=4$. Now, if $a_k=a_{k+1}\in \{3,4\}$, then $a_{k+3}\in \{3,4\}$ and there is nothing left to prove, but if $a_k=a_{k+1}>4$, there exists some natural number $m$ such that $a_{k+m}=a_{k+m+1}$. Using the proof of lemma 3, we have: If $m$ is odd, $$\begin{array}{rl}{a}_{k+1}& =\max \{a_{k+1},a_{k+2}=4\}>\max \{a_{k+3},a_{k+4}\}>\dots \\ & >\max \{a_{k+m},a_{k+m+1}\}=a_{k+m}.\end{array}$$ If $m$ is even, $$\begin{array}{rl}{a}_{k+1}& =\max \{a_{k+1},a_{k+2}=4\}>\max \{a_{k+3},a_{k+4}\}>\dots \\ & >\max \{a_{k+m-1},a_{k+m}\}\ge a_{k+m}.\end{array}$$ Therefore, if two equal consecutive terms in the sequence are greater than 4, there is another pair of equal consecutive terms in the sequence with a smaller value. We can continue this until we find two equal consecutive terms less than or equal 4. This completes the proof because the terms after that pair are 4, 3 or 4, 4.