Induction (other).

[Integer and fractional parts. Archimedes' principle]

Given a sequence of positive integers $X_{1}, X_{2} \ldots X_{n}$, all elements of which do not exceed some number $M$. It is known that for all $k>2$, $X_{\mathrm{k}}=\left|X_{\mathrm{k}-1}-X_{\mathrm{k}-2}\right|$. What can be the maximum length of this sequence?
Let $\lceil x\rceil$ denote the smallest integer not less than $x$, and $\lfloor x\rfloor$ denote the largest integer not exceeding $x$. We will prove that the maximum length $L(M)$ of such a sequence is

$$
L(M)= \begin{cases}2, & \text { if } M=1 \\ \left\lceil\frac{3 M}{2}\right\rceil+1, & \text { if } M \neq 1\end{cases}
$$

First, let's find the length $L_{1}(M)$ of the sequence where $X_{1}=1, X_{2}=M$. For this sequence, we get $X_{3}=M-1, X_{4}=1, X_{5}=M-2$, and thus $L_{1}(M)=L_{1}(M-2)+3$ for $M \geq 3, L_{1}(1)=2, L_{1}(2)=4$. Therefore,

$$
L_{1}(M)= \begin{cases}2, & \text { if } M=1 \\ \left\lfloor\frac{3 M}{2}\right\rfloor+1, & \text { if } M \neq 1\end{cases}
$$

Now, let's find the length of the sequence where $X_{1}=M-1, X_{2}=M$. For this sequence, $X_{3}=1$, $X_{4}=M-1$, so this length is $L_{1}(M-1)+2=L(M)$ for $M>1$. Thus, we have constructed a sequence whose length is $L(M)$. We will now prove that no longer sequence exists, by induction on $M$. The base cases $M=1,2,3$ are left to the reader as an exercise. Now, let $M \geq 4$. First, note that if $X_{1}<M$ and $X_{2}<M$, then all terms of the sequence do not exceed $M-1$, and thus its length does not exceed $L(M-1)<L(M)$. If $X_{1}=M=X_{2}$, then the length of the sequence is two, and thus not greater than $L(M)$. If $X_{1}=M, X_{2}<M$, then $X_{3}<M$, and thus the length of the sequence does not exceed $L(M-1)+1 \leq L(M)$. Therefore, the remaining case is $X_{1}<M, X_{2}=M$. For $X_{1}=1$ and $X_{1}=M-1$, the length of the sequence has already been calculated and does not exceed $L(M)$. If $1<X_{1}<M-1$, then $X_{3}<M-1$ and $X_{4}<M-1$, and thus the length of the sequence does not exceed $2+L(M-2)<L(M)$. Therefore, the maximum length of such a sequence is $L(M)$.

## Answer

$L(M)= \begin{cases}2, & \text { if } M=1, \\ \left\lceil\frac{3 M}{2}\right\rceil+1, & \text { if } M \neq 1\end{cases}$