Математикадан облыстық олимпиада, 2000-2001 оқу жылы, 10 сынып

0, 1, 2, 3 сандарынан құралған ${{x}_{1}}{{x}_{2}}\ldots {{x}_{n}}$ тізбегі берілген. Кез келген $i=1,2,\ldots ,n-1$ үшін $\overline{{{x}_{i}}{{x}_{i+1}}}$ мынадай мәндерді қабылдамайды: 12, 13, 32 және 33. Осындай қанша тізбек бар?

Комментарий/решение

Ответ:

$4\cdot 3^{n-1}, ~ \forall ~ n\in\mathbb{N}$

$E(n)$ количество правильных последовательностей оканчивающиеся на четную цифру, $NE(n)$ количество правильных последовательностей оканчивающиеся на нечетную цифру.

$E(1)=2, ~ NE(1)=2, ~ E(2)=4\cdot 2 -2=6, ~ NE(2)=4\cdot 2 -2=6$

Правильные последовательности длины $n+1$ содержат в себе правильные последовательности длины $n$.

Мы можем построить рекуррентные соотношения:

$NE(n+1)=NE(n)+E(n)\cdot 2, \quad E(n+1)=NE(n)+E(n)\cdot 2$

Получается $NE(n)=E(n), ~ \forall ~ n\in\mathbb{N}.$

$2E(n+1)=6E(n)=\dots=3^n \cdot 2E(1)$