Хорошая логическая задачка

[oip]

Цитата:

Сообщение от Косых Артём

А вот еще задача, недавно одному знакомому ее на собеседовании задавали...
Есть последовательность из 8 ячеек, в каждой ячейке могут быть либо ноль либо единица (байт и биты если по-нашему). Вопрос: как посчитать количество комбинаций расположения нулей и единиц, в которых нет двух рядом стоящих нулей???

Не знаю, правильно или нет, но у меня числа Фибоначчи получились.

Теорема: для n ячеек число таких способов равно F(n+1), т.е. n+1-му числу Фибоначчи. Докажем ее.

Для начала докажем лемму: при расположении, удовлетворяющему условиям задачи, число последовательностей, заканчивающихся на 1 равно F(n), а на 0 - F(n-1).

Докажем с помощью метода математической индукции.

Предпосылка: для n=2 имеем 1-1, 1-0 и 0-1, Т.е. на 1 оканчиваются F(2)=2, на 0 - F(1)=1.

Предположим теперь что это верно для n=k и докажем для n=k+1.
Очевидно, что к любому из этих k-значеых "чисел" можно приписать 1 и последовательность по-прежнему будет удовлетворять условию задачи. Т.е. на 1 будут оканчиваться F(k)+F(k-1)=F(k+1).
Ноль можно приписать только к последлвательностям, оканчивающимся на 1, т.е. их будет F(k). Таким образом лемма доказана.

Из доказанной леммы следует доказательство теоремы: число таких n-значных последовательностей равно числу последовательностей, заканчивающихся на 1 плюс заканчивающихся на 0, т.е. F(n)+F(n-1)=F(n+1). Теорема доказана.

P.S. Для n=8, F(n+1)=F(9)=55. Вроде так.