ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35468
Тема:    [ Числа Фибоначчи ]
Сложность: 3
Классы: 8,9
В корзину
Прислать комментарий

Условие

Найдите количество слов длины 10, состоящих только из букв "а" и "б" и не содержащих в записи двух букв "б" подряд.

Подсказка

Обозначьте за an количество слов длины n, состоящих только из букв "а" и "б" и не содержащих в записи двух букв "б" подряд. В последовательности a1, a2, ..., an выразите каждый следующий член через предыдущие.

Решение

Обозначим за an количество слов длины n, состоящих только из букв "а" и "б" и не содержащих в записи двух букв "б" подряд. Таким образом, находим a1=2, a2=3. Покажем, что an можно выразить через an-1 и an-2. Количество слов длины n, не содержащих в записи двух букв "б" подряд и начинающихся с буквы "а", равно an-1, так как после первой буквы может следовать любое слово длины n-1, не содержащее двух "б" подряд. Пусть слово длины n начинается с буквы "б". Если в этом слове нет двух "б" подряд, то вторая буква - "а", а далее может следовать любое слово длины n-2, не содержащее двух "б" подряд. Таким образом, количество слов длины n, не содержащих в записи двух букв "б" подряд и начинающихся с буквы "б", равно an-2. Тем самым, мы показали, что an=an-1+an-2. Теперь последовательно вычисляем a3=a2+a1=3+2=5, a4=a3+a2=5+3=8 и т.д., a10=a9+a8=144. Заметим, что получающиеся числа an - это хорошо известные числа Фибоначчи.

Ответ

144

Источники и прецеденты использования

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .