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

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

Условие

Рассмотрим множество последовательностей длины n, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно Fn + 2. Найдите взаимно-однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи 3.109.


Подсказка

Найдите рекуррентную формулу для числа таких последовательностей. Можно также воспользоваться результатом задачи 3.109. Для этого нужно каждую единицу интерпретировать как прыжок кузнечика через клетку.

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

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 3
Название Алгоритм Евклида и основная теорема арифметики
Тема Алгебра и арифметика
параграф
Номер 4
Название О том, как размножаются кролики
Тема Классическая комбинаторика
задача
Номер 03.124

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

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