All-Soviet-Union Mathematical Olympiad

Solution:
Answer 2998.
The sequence is completely determined by its first two elements. If the largest element of the sequence is $n$, then it must occur as one of the first two elements. Because $x_{3}$ and $x_{4}$ are both smaller than the largest of the first two elements and hence all subsequent elements are too.

Let $f(n, m)$ be the length of the sequence with $x_{1} = n$, $x_{2} = m$. It is straightforward to verify by induction that $f(1,2n) = f(2n - 1,2n) = 3n + 1$, $f(2n,1) = f(2n,2n - 1) = 3n$, $f(2n,2n + 1) = 3n + 3$, $f(1,2n + 1) = f(2n + 1,1) = 3n + 2$, $f(2n + 1,2n) = 3n + 1$. A rather more fiddly induction then shows that these are the best possible lengths. Hence the longest sequence with no element more than 1998 is that starting $1, 1998$ which has length 2998.