В гирлянде 31 лампочек, каждая может гореть или не гореть. Какое наибольшее возможное количество различных состояний может быть у гирлянды, если в ней не могут быть выключенными две соседние лампочки? Например, у гирлянды из двух лампочек три возможных состояния: обе горят; первая горит, а вторая не горит; первая не горит, а вторая горит.

Возьмём для начала гирлянду из двух лампочек и рассмотрим всевозможные её состояния:

Г Г; Г Н; Н Г.

Всего 3 состояния.

Теперь возьмём 3 лампочки:

Г Г Г; Н Г Г; Г Н Г; Г Г Н; Н Г Н.

Получается 5 состояний.

Возьмём 4 лампочки:

Г Г Г Г; Н Г Г Г; Г Н Г Г; Г Г Н Г; Г Г Г Н; Г Н Г Н; Н Г Н Г; Н Г Г Н.

Получается 8 состояний.

Таким образом, получим:

2 лампы могут иметь 3 состояния.

3 лампы могут иметь 5 состояния.

4 лампы могут иметь 8 состояния.

Обозначим количество лампочек в предыдущей цепи как (N - 1), а в следующей как N.

Очевидно, что прибавляя каждый раз на одну лампочку больше в гирлянду, количество состояний равно сумме двух предыдущих состояний:

F (N - 1) + F (N), F - состояние ламп в гирлянде.

То есть, 5 лампочек в гирлянде будут иметь 8 + 5 = 13 состояний.

Ряд будет выглядеть следующим образом:

3, 5, 8, 13 ...

Далее складываем 8 и 13 и так далее, продолжим ряд:

3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,

28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578.

Итого, 3524578 состояний лампочек в гирлянде из 31 лампочки.