Induction (other). $\quad]$

[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's denote by $\lceil x\rceil$ the smallest integer not less than $x$, and by $\lfloor x\rfloor$ 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 for which $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 for which $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 a longer sequence does not exist, 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, does not exceed $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)$. Thus, 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)=\left\{\begin{array}{l}2, \\ \left\lceil\frac{3 M}{2}\right\rceil+1,\end{array}\right.$

if $M=1$,

if $M \neq 1$.

| Problem 78671 | [ Processes and operations | Difficulty: 4 |
| :---: | :---: | :---: |
|  | [ Theory of algorithms (other). |  |

Two painters are painting a fence that surrounds the plots of a summer cottage. They come every other day and paint one plot each (there are 100 plots) in red or green. The first painter is colorblind and confuses the colors; he remembers which and in what color he painted himself, and sees what the second painter painted, but does not know the color. The first painter aims to achieve the maximum number of places where a green plot borders a red one. What is the maximum number of transitions he can achieve (regardless of how the second painter acts)?

Note. It is assumed that the summer cottage plots are arranged in a single line.

## Solution

First, let's show how the first painter can ensure at least 49 transitions. We divide the plots into pairs: (1, 2), (3, 4), ..., (99, 100). Then the first painter can ensure that in each pair with an even number, there is a red color, and in each pair with an odd number, there is a green color. For this, it is sufficient to act as follows: if the second painter paints a plot, then the first painter paints the other plot from the same pair so that the pair definitely contains the required color; if the other plot from the pair is already painted, then the first painter paints any plot in the required color. Thus, in each pair, there will be at least one plot of the required color, and therefore, the number of transitions will be at least 49. Now, let's show how the second painter can ensure that the number of transitions does not exceed 49. For this, it is sufficient to paint the plot from the same pair in the same color after each move of the first painter. Then each pair will be monochromatic, and therefore, the total number of transitions will not exceed 49.

## Answer

49 transitions.