XL OM - I - Zadanie 5

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dla danej liczby naturalnej $n$ wyznaczyć liczbę ciągów $(a_1, a_2, \ldots , a_n)$ , których wyrazy $a_i$ należą do zbioru $\{0,1,2,3,4\}$ oraz spełniają warunek $|a_i - a_{i+i}| = 1$ dla $i = 1,2,\ldots,n-1$ .

Rozwiązanie

Wszystkie ciągi spełniające podane w zadaniu warunki podzielimy na trzy rodzaje:

ciągi I rodzaju — kończące się symbolem $0$ lub $4$ ;\\
ciągi II rodzaju — kończące się symbolem $1$ lub $3$ ;\\
ciągi III rodzaju — kończące się symbolem $2$ .

Oznaczmy przez $x_n$ , $y_n$ , $z_n$ odpowiednio liczbę $n$ --wyrazowych ciągów I, II, III rodzaju. Każdy ciąg I rodzaju (długości $n$ ) można przedłużyć w jeden tylko sposób do ciągu długości $n + 1$ ; będzie to ciąg II rodzaju (bowiem po zerze może być tylko jedynka, a po czwórce może być tylko trójka). Z każdego ciągu II rodzaju (długości $n$ ) można utworzyć dwa ciągi długości $n+1$ , jeden I rodzaju i jeden III rodzaju (po jedynce zero, po trójce czwórka, bądź też, po jedynce lub trójce - dwójka). Wreszcie ciąg III rodzaju (długości $n$ ) da życie dwóm ciągom długości $n+1$ , obu II rodzaju (po dwójce - trójka lub jedynka).

Otrzymujemy więc zależność

$ (1) \qquad \left\{ \begin{split} x_{n+1} &= y_n\\ y_{n+1} &=x_n + 2z_n\\ z_{n+1} &= y_n, \end{split}\right. $

a z niej:

$ (2) \qquad \left\{ \begin{split} x_{n+2} &= y_{n+1}=x_n+2z_n\\ y_{n+2} &=x_{n+1} + 2z_{n+1}=3y_n\\ z_{n+2} &= y_{n+1}=x_n+2-z_n, \end{split} \right. $

Z wzorów (1) widać, że

$ (3) \qquad x_n = z_n \quad \textrm{dla } n \geq 2. $

Oznaczmy sumę $x_n + y_n + z_n$ (czyli liczbę wszystkich dopuszczalnych ciągów długości $n$ ) przez $s_n$ . Dodając stronami wzory (2) i uwzględniając równość (3) otrzymujemy związek:

$ (4) \qquad s_{n+2} = 3s_n \quad \textrm{dla } n \geq 2. $

Musimy jeszcze znać wartości $s_1$ $s_2$ i $s_3$ . Ciąg długości $1$ to pojedynczy symbol. Mamy do dyspozycji pięć symboli, więc $s_1 = 5$ . Wypiszmy teraz wszystkie dopuszczalne ciągi długości 2 oraz 3: