Областная олимпиада по математике, 2001 год, 10 класс

Дана последовательность $x_1, x_2, \dots , x_n$ состоящая из чисел $0,\ 1,\ 2,\ 3$. Для любого $i=1$, $2$, $\dots$, $n-1$, $\overline{x_ix_{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)$