Десятизначное положительное целое число называется «хорошим», если его цифры взяты из множества {1, 2, 3}, и каждые две соседние цифры отличаются на 1. Найдите общее количество таких «хороших» чисел.

Цифры могут быть только \(1\), \(2\), \(3\). Соседние цифры должны отличаться на \(1\), значит возможны только переходы:

• после \(1\) обязательно идёт \(2\);
• после \(3\) обязательно идёт \(2\);
• после \(2\) может идти \(1\) или \(3\).

Посчитаем количество чисел длины \(n\), оканчивающихся на каждую цифру.

Для \(n=1\):

\[a_1=1,\quad b_1=1,\quad c_1=1\]

где \(a_n\) — оканчиваются на \(1\), \(b_n\) — на \(2\), \(c_n\) — на \(3\).

Переходы такие:

\[a_{n+1}=b_n,\quad b_{n+1}=a_n+c_n,\quad c_{n+1}=b_n\]

Считаем до \(10\):

Ответ: \(64\) хороших числа.

0 0 Пожаловаться