191*. The sequence of natural numbers $a_{0}, a_{1}$, $a_{2}, a_{3}, \ldots$ is formed according to the following rule:

$$
a_{0}, a_{1}, a_{2}=\left|a_{0}-a_{1}\right|, a_{3}=\left|a_{1}-a_{2}\right|, \ldots
$$

(and generally $a_{n}=\left|a_{n-2}-a_{n-1}\right|$ for all $n \geqslant 2$); the sequence continues until the first zero. It is known that each number in the sequence does not exceed 1967. What is the maximum number of terms that such a sequence can contain?
191. It is not difficult to understand that the largest number in our sequence can only be one of the first two numbers $a_{0}$ and $a_{1}$ (since each $a_{k}$ for $k \geqslant 2$ is necessarily $a_{2}$, the sequence can be "extended backwards" without changing it, by agreeing to start as follows: $a_{0}=a_{1}-a_{2}, \quad a_{1}, \quad a_{2}=\left|a_{1}-a_{0}\right|, a_{3}, \ldots$ (here, obviously, $a_{1}>$ $>a_{0}=a_{1}-a_{2}$ ). Therefore, in the future, we will limit ourselves to considering sequences that start with the largest number $a_{1}$ (we will only have to increase the length of the sequence by 1 in the final answer to account for the "zeroth" number $\left.a_{0}=a_{1}-a_{2}\right)$.

It is clear that if the largest member of the sequence $a_{1}=1$, then the sequence consists of no more than two numbers (it can only be continued by one number $a_{2}=1$); if the largest member of the sequence $a_{1}=2$, then the number of numbers in the sequence $\leqslant 3$ (if $a_{2}=2$, then the sequence is: 2, 2, and if $a_{2}=1$, then it is: $2,1,1$); if $a_{1}=3$, then the number of numbers in the sequence $\leqslant 5$ (assuming that $a_{2}=3,2$ or 1, we arrive at the sequences: 3,3; or 3,2,1; or, finally, $3,1,2,1,1$). These examples suggest the conclusion that the "optimal" sequence, apparently, should start with the numbers $a_{1}=n, a_{2}=1$. In this case, the beginning of it looks like this:

$$
n, 1, n-1, n-2,1, \ldots
$$

from which it follows that, denoting the number of numbers that make up the sequence ( $\left.{ }^{*}\right)$ by $k_{n}$, we get:

$$
k_{n}=3+k_{n-2}
$$

(since, starting from the 4th term $a_{4}=n-2$, we come to a similar sequence where $n$ is replaced by $n-2$).

1) Compare with the footnote on p. 228.

From the relation ( ${ }^{* *}$ ) we find:

$$
\begin{aligned}
k_{1}=2, k_{2}=3, k_{3}=3+2=5, k_{4} & =3+3=6 \\
k_{5}=3+5 & =8, k_{8}=3+6=9, \ldots
\end{aligned}
$$

all these numbers $k_{n}$ are given by the following formula:

$$
k_{n}=\left[\frac{3 n+1}{2}\right]
$$

where the square brackets, as always (compare p. 37), denote the integer part of the number. (The formula (***), of course, is quite easy to derive from (**) using the method of mathematical induction: for $n=1$ and $n=2$ it, as we have seen, is valid; if (**) is true for the value $n-2$, then for the value $n$ this relation is also true:

$$
\left.k_{n}=k_{n-2}+3=\left[\frac{3(n-2)+1}{2}\right]+3=\left[\frac{3 n+1}{2}\right] \cdot\right)
$$

So, we have already constructed (starting with the largest number!) the sequence (*), the length $k_{n}$ of which is related to the value $n$ of the largest number by the relation (***); let us now show that if the sequence described in the problem statement starts with the largest number $a_{1}=n$, then its length cannot exceed the number $k_{n}$ specified by the formula (***). We will prove this, of course, by induction: suppose that the italicized statement has already been proved for all values of $n$ less than some (and the validity of it for the values $n=1,2$ and 3 we have already verified), and show that then it will be true for the value $n$. Indeed, let a sequence satisfying the conditions of the problem be given, starting with the numbers:

$$
n, m, \ldots
$$

where $m \leqslant n$. Let us then consider the cases corresponding to different values of $m$.

$1^{0}$. If $m=n$, then the sequence ends at the 2nd term; for it, our statement is, of course, satisfied.