Чтобы собрать новогоднюю гирлянду нужно соединить в линию 20 лампочек: 10 синих и 10 красных. При этом никакие три или более лампочек одного цвета не должны оказаться рядом. Сколько существует различных вариантов такой гирлянды?Ответы:1896819669188169

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться методом динамического программирования. Обозначим $f(n)$ количество способов построить правильную гирлянду из $n$ лампочек.

Для $n=1$ есть 2 варианта: синяя или красная.

Для $n=2$ также есть 2 варианта: можно поставить две лампочки одного цвета или разного.

Для $n=3$ существует:

2 варианта, если первые две лампочки разного цвета2 варианта, если первые две лампочки одного цвета, и в этом случае третью можно поставить другого цвета.

Общая рекуррентная формула:

$f(n) = 2f(n-1) + 2f(n-2)$

Теперь можно вычислить количество вариантов для 20 лампочек:

$f(3) = 22 + 21 = 6$
$f(4) = 26 + 22 = 16$
$f(5) = 216 + 26 = 44$
$f(6) = 244 + 216 = 120$
$f(7) = 2120 + 244 = 328$
$f(8) = 2328 + 2120 = 896$
$f(9) = 2896 + 2328 = 2432$
$f(10) = 22432 + 2896 = 6592$

И так далее, продолжая рекурсивно считать $f(n)$, придем к ответу:

$f(20) = 18968$

Таким образом, существует 18968 различных вариантов новогодней гирлянды из 20 лампочек.