\section*{Problem 7}

What is the maximum possible length of a sequence of natural numbers \(\mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3}, \ldots\) such that \(\mathrm{x}_{\mathrm{i}} \leq 1998\) for \(\mathrm{i}>=1\), and \(\mathrm{x}_{\mathrm{i}}=\left|\mathrm{x}_{\mathrm{i}-1}-\mathrm{x}_{\mathrm{i}-2}\right|\) for \(\mathrm{i} \geq 3\).


\section*{Solution}

Answer 2998.

The sequence is completely determined by its first two elements. If the largest element of the sequence is \(\mathrm{n}\), then it must occur as one of the first two elements. Because \(\mathrm{x}_{3}\) and \(\mathrm{x}_{4}\) are both smaller than the largest of the first two elements and hence all subsequent elements are too.

Let \(\mathrm{f}(\mathrm{n}, \mathrm{m})\) be the length of the sequence with \(\mathrm{x}_{1}=\mathrm{n}, \mathrm{x}_{2}=\mathrm{m}\). It is straightforward to verify by induction that \(f(1,2 n)=f(2 n-1,2 n)=3 n+1, f(2 n, 1)=f(2 n, 2 n-1)=3 n, f(2 n, 2 n+1)=3 n+3\), \(\mathrm{f}(1,2 \mathrm{n}+1)=\mathrm{f}(2 \mathrm{n}+1,1)=3 \mathrm{n}+2, \mathrm{f}(2 \mathrm{n}+1,2 \mathrm{n})=3 \mathrm{n}+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.

