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

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

Условие

О том, как прыгают кузнечики. Предположим, что имеется лента, разбитая на клетки и уходящая вправо до бесконечности. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами кузнечик может добраться до n-ой от начала ленты клетки?


Решение

Пусть an — количество способов, которыми кузнечик может добраться до n-ой клетки. Тогда a1 = a2 = 1. Кроме того, в n + 1-ую клетку кузнечик может попасть либо из n-ой клетки, либо перепрыгнув n-ую клетку. Поэтому an + 1 = an - 1 + an. Отсюда an = Fn - 1.

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

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

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

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