XL OM - I - Zadanie 5

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ść

\[<br />
(1) \qquad \left\{ \begin{split}<br />
 x_{n+1} &= y_n\\<br />
 y_{n+1} &=x_n + 2z_n\\<br />
 z_{n+1} &= y_n,<br />
\end{split}\right.<br />
\]

a z niej:

\[<br />
(2) \qquad<br />
\left\{<br />
\begin{split}<br />
 x_{n+2} &= y_{n+1}=x_n+2z_n\\<br />
 y_{n+2} &=x_{n+1} + 2z_{n+1}=3y_n\\<br />
 z_{n+2} &= y_{n+1}=x_n+2-z_n,<br />
\end{split}<br />
\right.<br />
\]

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

\[<br />
(3) \qquad x_n = z_n \quad   \textrm{dla }  n \geq 2.<br />
\]

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:

\[<br />
(4) \qquad s_{n+2} = 3s_n  \quad  \textrm{dla  } n \geq 2.<br />
\]

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:

\[<br />
(01),\  (10),\  (12),\  (21),\  (23),\  (32),\  (34),\  (43)<br />
\]

oraz

\[<br />
(010),\  (012),\  (101),\  (121),\  (123),\  (210),\  (212),<br />
\]
\[<br />
(232),\  (234),\  (321),\  (323),\  (343),\  (432),\  (434).<br />
\]

Wobec tego

\[<br />
s_1 = 5,\quad   s_2 = 8, \quad  s_3 = 14.<br />
\]

Stąd i z wzoru rekurencyjnego (4) otrzymujemy przez oczywistą indukcję odpowiedź:

\[<br />
s_{2k} = 8 \cdot 3^{k-1} ,\quad   s_{2k+1} = 14 \cdot 3^{k-1}   \textrm{dla } k \geq 1.<br />
\]

Komentarze

Dodaj nową odpowiedź