Bogosonov I.I.  Petya wants to list all possible sequences of 100 natural numbers, in each of which a three appears at least once, and any two adjacent members differ by no more than 1. How many sequences will he have to list?
Let's find the answer for similar sequences of $n$ natural numbers.

First method. We call a sequence of $n$ natural numbers, any two adjacent members of which differ by no more than 1, interesting. 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, let's count the number $S$ of all interesting sequences, the minimum member of which does not exceed 3. Consider an arbitrary difference sequence $b_{1}, b_{2}, \ldots, b_{n-1}$. 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. It is clear that 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 method. We call a sequence of $n$ natural numbers good if it contains at least one three. Denote by $S_{n}$ 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 ($n=1$) is obvious.

Inductive step. We call a good $(n+1)$-member sequence $A$ distinct if among its first $n$ members, there is a three. Remove the last member from each distinct sequence; in each case, we will 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 distinct sequences ending with 1 or 2. If $A^{\prime}$ ends with a number $k>1$, then it is obtained from three distinct 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 distinct $(n+1)$-member sequences is $2 T_{n} + 3(S_{n} - T_{n}) = 3 S_{n} - T_{n}$.

It remains to count the number of non-distinct $(n+1)$-member sequences. 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 exactly from $2^{n-1}$ non-distinct sequences.

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. In total, there are $T_{n} + 2^{n-1}$ sequences of the latter type.

Thus, $S_{n+1} = (3 S_{n} - T_{n}) + 2^{n-1} + (T_{n} + 2^{n-1}) = 3 S_{n} + 2^{n} = 3^{n+1} - 2^{n+1}$.

## Answer

$3^{100} - 2^{100}$.

Send a comment