9.8. Pete wants to list all possible sequences of 100 natural numbers, in each of which a triple appears at least once, and any two adjacent members differ by no more than 1. How many sequences will he have to list?

(I. Bogdanov)
Answer. $3^{100}-2^{100}$.

First solution. Let $n=100$. We call a sequence of $n$ natural numbers interesting if any two adjacent members differ by no more than 1. To each interesting sequence $a_{1}, a_{2}, \ldots, a_{n}$, we associate a difference sequence $b_{i}=a_{i+1}-a_{i}(i=1,2, \ldots, n-1)$. All members of the difference sequence are 0 or $\pm 1$, so the number of all possible difference sequences is $3^{n-1}$.

First, we count the number $S$ of all interesting sequences whose minimum member does not exceed 3. Consider an arbitrary difference sequence $b_{1}, b_{2}, \ldots, b_{99}$. Any two interesting sequences corresponding to it differ by adding the same number to each member. Therefore, among them, there is exactly one sequence with the minimum member equal to 1, 2, and 3. Thus, $S=3 \cdot 3^{n-1}=3^{n}$.

In $S$, all sequences written by Petya are counted, and some extra ones - those in which 3 does not appear. Clearly, if an interesting sequence contains both numbers greater than 3 and less than 3, then 3 also appears. But the minimum member of each extra sequence does not exceed 2, meaning that all its members do not exceed 2. Therefore, all extra sequences consist of ones and twos. On the other hand, every sequence of ones and twos is interesting and, therefore, extra.

Thus, there are exactly $2^{n}$ extra sequences, and the desired number is $S-2^{n}=3^{n}-2^{n}$.

Second solution. We call a sequence of $n$ natural numbers good if it contains at least one three, and any two adjacent members differ by no more than 1. Let $S_{n}$ be the number of good sequences of length $n$. We will prove by induction on $n$ that $S_{n}=3^{n}-2^{n}$. The base case for $n=1$ is obvious.

We make the transition from $n$ to $n+1$. We call a good $(n+1)$-member sequence $A$ different if among its first $n$ members, there is a three. Remove the last member from each different sequence; in each case, we get a good $n$-member sequence. If a good $n$-member sequence $A^{\prime}$ ends with the number 1, then it is obtained in this way from two different sequences - ending with the number 1 or 2. If $A^{\prime}$ ends with the number $k>1$, then it is obtained from three different sequences, which end with $k-1, k$, or $k+1$. Thus, if the number of $n$-member good sequences ending with the number 1 is $T_{n}$, then the number of different $(n+1)$-member sequences is $2 T_{n}+3\left(S_{n}-T_{n}\right)=3 S_{n}-T_{n}$.

It remains to count the number of non-different $(n+1)$-member sequences. Clearly, each of them ends with the number 3; if we remove this three, we get an $n$-member sequence $A^{\prime}$ without threes. Since its adjacent members differ by no more than 1, either all of them are greater than 3 or all are less than 3.

If all members of $A^{\prime}$ are less than 3, then $A^{\prime}$ consists of the numbers 1 and 2, ending with the number 2. Any such sequence, appended with a three at the end, gives a good sequence. Therefore, such sequences $A^{\prime}$ are obtained from exactly $2^{n-1}$ non-different sequences.

Now suppose all members of $A^{\prime}$ are greater than 3; then it ends with the number 4. Subtracting 3 from all its members, we get either a good sequence ending with the number 1 (if the resulting sequence contains 3) - there are exactly $T_{n}$ such sequences; or a sequence of ones and twos, ending with the number 1 - there are exactly $2^{n-1}$ such sequences. Thus, there are $T_{n}+2^{n-1}$ sequences of the latter type.

In the end, we get that $S_{n+1}=\left(3 S_{n}-T_{n}\right)+2^{n-1}+\left(T_{n}+\right.$ $\left.+2^{n-1}\right)=3 S_{n}+2^{n}=3^{n+1}-2^{n+1}$. The transition is proved.

Comment. Only the answer - 1 point.

If the problem is solved for sequences of $n$ numbers, but only cases of small values of $n$ (say, $n \leqslant \leqslant 6)-0$ points.

If the approach is similar to the first solution, but the number of extra sequences is incorrectly counted - deduct 3 points.

If the inductive approach is similar to the second solution, but the counting of sequences where the three appears only at the last position is incorrect - give no more than 3 points.

## 10th grade