Рассмотрим алфавит из 2 букв. Словом будем считать любое конечное сочетание букв. Назовём слово непроизносимым, если в нём встречается больше двух одинаковых букв подряд. Сколько всего существует непроизносимых слов из 7 букв?

Ответ: 86

Решение:

Всего есть слов из 7 букв, каждую из которых можно выбрать из двух вариантов. Посчитаем, сколько из этих слов произносимые.

Введём a и b - количество произносимых слов, оканчивающихся не на две одинаковые буквы и на две одинаковые буквы. Будем вычислять a и b для каждой длины слова n. Общее количество произносимых слов будет вычисляться по формуле a + b.

Для n = 1, очевидно, a = 2, b = 0. Значения для следующих n можно получить из предыдущих: новое a будет равно сумме предыдущих a и b (можно получить произносимое слово из любого слова с меньшей длиной путем приписывания в конец буквы, которая будет отлична от последней); новое b будет равно предыдущему a (на пару одинаковых букв будут оканчиваться только те слова, у которых на прошлом шаге буквы были разные - иначе в конце появятся как минимум 3 одинаковые буквы).

Заполненная таблица имеет вид:

Итак, произносимых слов длины 7 всего 42, тогда непроизносимых - .

(Кстати, в последовательности количества произносимых слов можно заметить удвоенную последовательность Фибоначчи - последовательности, начинающейся с 0 и 1, в которой каждый новый член равен сумме двух предыдущих)