11.8. Petya wants to list all possible sequences of 100 natural numbers, in each of which the number 4 or 5 appears at least once, and any two adjacent members differ by no more than 2. How many sequences will he have to list?

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

First solution. Let $n=100$. We will call a sequence of $n$ natural numbers interesting if any two adjacent members differ by no more than 2. 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, \pm 1$ or $\pm 2$, so the number of all possible difference sequences is $5^{n-1}$.

First, we count the number $S$ of all interesting sequences whose minimum member does not exceed 5. 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,3,4$ or 5. Thus, $S=5 \cdot 5^{n-1}=5^{n}$.

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

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

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

We will make the transition from $n$ to $n+1$. Consider an arbitrary $n$-member good sequence; let it end with the number $k$. Then we can append any number from $k-2$ to $k+2$ to it; the resulting sequence will be good if the appended number is natural. If the appended number is non-positive (i.e., 0 or -1), then after appending, we add 5 to all numbers in the sequence. The resulting sequence will end with the number 4 or 5, and thus will be good.

Note that all the resulting sequences are different. For sequences obtained without adding 5, this is obvious; in this way, we obtain exactly all good sequences among which the first $n$ members contain 4 or 5. The sequences obtained by adding 5 are also pairwise different; in this way, we obtain exactly all good sequences whose first $n$ members are greater than 5, and among which 9 or 10 appear. In particular, these sequences are different from those described earlier. Thus, we have constructed $5 S_{n}$ good $(n+1)$-member sequences.

It remains to count the number of uncounted sequences. In each uncounted sequence, among the first $n$ members, there are no numbers 4, 5, 9, or 10, and the last member is 4 or 5. Therefore, either the first $n$ members are ones, twos, and threes, or they are sixes, sevens, and eights. We will count the number of the first; the number of the second is counted similarly.

Consider any sequence of $n$ ones, twos, and threes (the adjacent members of which automatically differ by at most 2). If it ends with the number 3, then we can append 4 or 5, obtaining an uncounted sequence. If it ends with the number 2, then we can append only 4; if its last number is 1, then we cannot obtain a good sequence from it. Therefore, the number of obtained uncounted sequences is $2 \cdot 3^{n-1}+3^{n-1}=3^{n}$ (and the same number is obtained from sequences with numbers 6, 7, and 8).

Thus, we get $S_{n+1}=5 S_{n}+2 \cdot 3^{n}=5\left(5^{n}-3^{n}\right)+2 \cdot 3^{n}=$ $=5^{n+1}-3^{n+1}$, as required.

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 6$) are considered - 0 points.

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

In an inductive approach similar to the second solution, the counting of sequences in which the numbers 4 and 5 appear only in the last place is incorrect - no more than 3 points are given.