Question

Слава выписывает в ряд крестики и нолики, всего 12 символов. Сколько существует таких цепочек, чтобы никакие два крестика НЕ стояли рядом

Answer 1

Ответ: Существует 377  цепочек состоящих из 12 символов, в которых никакие два крестика не стоят рядом

Пошаговое объяснение:

Обозначим количество искомых  цепочек длины n через aₙ

Рассмотрим произвольную цепочку. Если в этой цепочке последний символ нолик, то это не накладывает дополнительных ограничений на предыдущие n − 1  ячеек для символов, и число таких цепочек равно aₙ₋₁
Если же последним стоит  крестик, то предпоследний  символ может быть только нолик, а на предыдущие n−2 ячеек  дополнительных ограничений нет, поэтому количество таких цепочек равно aₙ₋₂

Получаем соотношение

aₙ = aₙ₋₁  +  aₙ₋₂

Легко видеть, что

$1.\large \begin{array}{|c|}\cline{2-2} \circ \cline{3-4}\end{array} ~~~2.\large \begin{array}{|c|}\cline{2-2} \times \cline{3-4}\end{array} \Rightarrow a_1= 2$
$1.\large \begin{array}{|c|c|}\cline{3-4} \circ & \times \cline{3-4}\end{array} ~~~2.\large \begin{array}{|c|c|}\cline{3-4} \times & \circ \cline{3-4}\end{array} ~~3.\large \begin{array}{|c|c|}\cline{3-4} \circ & \circ \cline{3-4}\end{array} \Rightarrow a_2= 3$

Отсюда из полученного ранее соотношения следует

a₃ = 2 + 3 = 5
a₄ = 3 + 5 = 8
a₅ = 5 + 8 = 13
a₆ = 8 + 13 = 21
a₇ = 13 + 21 = 34
a₈ = 21 +  34 = 55
a₉ = 34 + 55 = 89
a₁₀ = 55 + 89 = 144
a₁₁ =  89 + 144 = 233
a₁₂ = 144 + 233 = 377