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

$ (1) \qquad x_{n+1}=z_n=x_n+y_n. $

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

$ (2) \qquad y_{n+1}=9x_n+y_n. $

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

$ (3) \qquad z_{n+1}=x_{n+1}+y_{n+1}=10x_n+2y_n=2z_n+8x_n=2z_n+8z_{n-1} $

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

$ (4) \qquad z_n=a\cdot 4^n+b\cdot(-2)^n\qquad\hbox{dla }n=3,4,5,\ldots. $

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

$ z_3=x_3+y_3,\qquad z_4=x_4+y_4=10x_3+2y_3. $

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

$ x_3=100,\quad y_3=180,\qquad z_3=280,\quad z_4=1360. $

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

$ \begin{cases} 64a-8b & =280 \\ 256a+16b &=1360 \end{cases} $

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

$ 3x_{n+1}+y_{n+1}=12x_n+4y_n\,,\quad 3x_{n+1}-y_{n+1}=-6x_n+2y_n . $