LVIII OM - I - Zadanie 4

Dla każdej liczby naturalnej $ n\ge 3 $ wyznaczyć liczbę ciągów $ (c_1,c_2,\ldots,c_n) $, gdzie $ {c_i\in\{0,1,\ldots,9\}} $, o następującej własności:\break w każdej trójce kolejnych wyrazów są co najmniej dwa wyrazy równe.

Rozwiązanie

Niech $ z_n $ będzie liczbą ciągów $ n $-wyrazowych mających żądane własności (będziemy je dalej nazywać ciągami {\it dobrymi}). Niech $ x_n $ będzie liczbą dobrych ciągów $ (c_1,c_2,\ldots,c_n) $, których dwa ostatnie wyrazy $ c_{n-1} $ i $ c_n $ są równe, natomiast $ y_n $ niech oznacza liczbę dobrych ciągów $ (c_1,c_2,\ldots,c_n) $, w których $ c_{n-1}\ne c_n $. Oczywiście spełniona jest równość $ z_n=x_n+y_n $.

Każdy dobry ciąg $ (n+1) $-wyrazowy $ (c_1,c_2,\ldots,c_{n+1}) $, w którym dwa ostatnie wyrazy $ c_n $ i $ c_{n+1} $ są równe, powstaje z dokładnie jednego dobrego ciągu $ (c_1,c_2,\ldots,c_n) $ przez dodanie warunku $ c_{n+1}=c_n $. Prawdziwa jest zatem zależność

\[<br />
(1) \qquad x_{n+1}=z_n=x_n+y_n.<br />
\]

Natomiast dobry ciąg $ (n+1) $-wyrazowy $ (c_1,c_2,\ldots,c_{n+1}) $, w którym dwa ostatnie wyrazy $ c_n $ i $ c_{n+1} $ są różne, możemy otrzymać na dwa sposoby. W pierwszym sposobie należy wziąć dobry $ n $-wyrazowy ciąg $ (c_1,c_2,\ldots,c_n) $, w którym $ c_{n-1}=c_n $, zaś za $ c_{n+1} $ przyjąć dowolną liczbę ze zbioru $ \{0,1,\ldots,9\} $ różną od $ c_n $. Tak postępując otrzymamy $ 9x_n $ różnych dobrych $ (n+1) $-wyrazowych ciągów. W drugim sposobie wybieramy dobry $ n $-wyrazowy ciąg $ (c_1,c_2, \ldots,c_n) $, w którym $ c_{n-1}\ne c_n $ i przyjmujemy $ c_{n+1}=c_{n-1} $. Tym razem uzyskamy $ y_n $ różnych ciągów. Ponadto żaden ciąg nie może być otrzymany oboma sposobami. Wynika stąd równość

\[<br />
(2) \qquad y_{n+1}=9x_n+y_n.<br />
\]

Ze związków (1) i (2) dostajemy

\[<br />
(3) \qquad z_{n+1}=x_{n+1}+y_{n+1}=10x_n+2y_n=2z_n+8x_n=2z_n+8z_{n-1}<br />
\]

dla $ n=4,5,6,\ldots $. Zastosujemy teraz metodę rozwiązywania rekurencji liniowych (zob. L Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Warszawa 2000, Dodatek A, str. 103). Równaniem charakterystycznym rekurencji (3) jest $ t^2=2t+8 $, które ma dwa różne pierwiastki rzeczywiste: $ t=4 $ oraz $ t=-2 $. Zatem istnieją takie liczby rzeczywiste $ a $, $ b $, że zachodzi równość

\[<br />
(4) \qquad z_n=a\cdot 4^n+b\cdot(-2)^n\qquad\hbox{dla }n=3,4,5,\ldots.<br />
\]

Do zakończenia rozwiązania pozostaje wyznaczyć wartości $ a $, $ b $. W tym celu obliczymy liczby $ z_3 $, $ z_4 $. Ze wzorów (1) i (2) wynika, że

\[<br />
z_3=x_3+y_3,\qquad z_4=x_4+y_4=10x_3+2y_3.<br />
\]

Liczba dobrych ciągów $ (c_1,c_2,c_3) $, w których $ c_2=c_3 $, wynosi $ 10^2=100 $, gdyż wartości $ c_1 $, $ c_2 $ możemy wybrać dowolnie, natomiast liczba dobrych ciągów $ (c_1,c_2,c_3) $, w których $ c_2\ne c_3 $, wynosi $ 2\cdot 10\cdot 9=180 $, bowiem parę różnych liczb $ (c_2,c_3) $ można wybrać dowolnie i $ c_1 $ musi być równe $ c_2 $ lub $ c_3 $. Zatem

\[<br />
x_3=100,\quad y_3=180,\qquad z_3=280,\quad z_4=1360.<br />
\]

Łącząc obliczone wyżej wartości z warunkiem (4) otrzymujemy układ równań

\[<br />
\begin{cases}<br />
64a-8b & =280  \\<br />
256a+16b &=1360<br />
\end{cases}<br />
\]

którego rozwiązaniem są liczby $ a=b=5 $.

Odpowiedź: Szukana liczba ciągów wynosi $ 5\cdot(4^n+(-2)^n) $.

Uwaga:Po uzyskaniu zależności (1) i (2) można dokończyć rozwiązanie zadania bez stosowania metody rozwiązywania rekurencji liniowych (aczkolwiek wymaga to zgadnięcia właściwych współczynników). Mianowicie, ze związków (1) i (2) dostajemy

\[<br />
3x_{n+1}+y_{n+1}=12x_n+4y_n\,,\quad 3x_{n+1}-y_{n+1}=-6x_n+2y_n .<br />
\]

Przyjmując teraz oznaczenia

\[<br />
u_n=3x_n+y_n\,,\quad v_n=3x_n-y_n<br />
\]

mamy więc

\[<br />
(5) \qquad u_{n+1}=4u_n\,,\quad v_{n+1}=-2v_n\qquad\hbox{dla }n=3,4,5,\ldots\ .<br />
\]

Obliczamy ponadto, że $ x_3=100 $, $ y_3=180 $, czyli $ u_3=480 $, $ v_3=120 $; wobec tego z zależności (5) przez indukcję uzyskujemy wzory

\[<br />
u_n=480\cdot 4^{n-3}=15\cdot 2^{2n-1}\,,\quad<br />
v_n=120\cdot(-2)^{n-3}=-15\cdot(-2)^n\,.<br />
\]

Stąd ostatecznie

\[<br />
z_n=x_{n+1}={u_{n+1}+v_{n+1}\over 6}={15\cdot(2^{2n+1}-(-2)^{n+1})\over 6}=5\cdot(4^n+(-2)^n)\,.<br />
\]

Komentarze

Dodaj nową odpowiedź