Лягушка находится в первой клетке доски $1\times 10$. Она может прыгать на одну или на две клетки вперёд. Но на шестой клетке находится вкусная муха, которую лягушка хочет съесть — для этого лягушка должна встать на шестую клетку. Сколькими способами лягушка может допрыгать до последней клетки, съев по пути муху?

Лягуша может попасть на шестую клетку 8 способами (см. задачу "Фибоначчи-3"). После этого остаётся пять клеток (включая шестую клетку, на которой сейчас находится лягушка), и преодолеть эти пть клеток можно пятью способами. На каждый способ преодолеть первую часть пути есть пять способов преодолеть вторую часть, поэтому ответ: 40.

Полезно:
Убедиться, что учащиеся понимают условия задачи и важность остановки на шестой клетке.

Попросить учащихся смоделировать движение лягушки по клеткам, чтобы визуализировать возможные пути.

Объяснить, как можно использовать рекурсию для подсчета всех возможных путей к последней клетке, учитывая необходимость остановиться на шестой клетке.

Предложить учащимся создать таблицу, где они будут записывать количество способов добраться до каждой клетки, что поможет им увидеть паттерны.

Лягушка находится в первой клетке доски $1\times 10$. Она может прыгать на одну или на две клетки вперёд. Сколькими способами она может сделать один или несколько прыжков и оказаться в клетке с чётным номером?

Решение 1. Из задачи "Фибоначчи-3" получаем, что нам нужно вычислить сумму второго, четвёртого, шестого, восьмого и десятого чисел Фибоначчи. Складывая эти числа, получаем 88.

Решение 2. Докажем, что указанная сумма на 1 меньше, чем 11-е число Фибоначчи. Для этого рассмотрим полоску 1х11 и лягушку. Как она может добраться до 11-й клетки? Пусть последние несколько ходов (возможно, ноль) она прыгала на две клетки, а перед этим шагала на одну клетку. Откинем эти ходы и получим, что лягушка оказалась на какой-то чётной клетке. Таким образом мы учли все способы перемещения лягушки, кроме одного - когда она пять раз прыгнула на две клетки. Значит, сумма второго, четвёртого, шестого, восьмого и десятого числа Фибоначчи на 1 меньше, чем 11-е число Фибоначчи.

Сколькими способами можно разрезать прямоугольник $2\times 8$ на домино (прямоугольнички $1\times 2$)? Домино можно поворачивать.

Докажем, что количество способов разрезать прямоугольник 2хn на домино есть (n+1)-е число Фионаччи. В самом деле, доску 2х1 можно разрезать единственным способом, доску 2х2 - двумя. От доски 2хn можно отрезать вертикальную домино - останется доска 2х(n-1), а можно две горизонтальные - останется доска 2х(n-2). Поэтому количество способов разрезать на домино доску 2хn есть сумма количества способов разрезать на домино доску 2х(n-1) и количества способов разрезать на домино доску 2х(n-2).

При решении этой задачи:
Можно нарисовать прямоугольник 2×8 и показать, как могут располагаться домино. Это поможет учащимся лучше понять задачу.

Проговорить как можно использовать рекурсивный подход для решения задачи, где каждый раз можно выбирать, как разместить первое домино (вертикально или горизонтально).

Предложить учащимся проверить свои ответы на меньших примерах (например, 2×2 или 2×4) для лучшего понимания.

Попросить учащихся сформулировать рекуррентное соотношение для нахождения количества способов разрезания прямоугольника, что поможет им увидеть взаимосвязь между разными способами отрезания первого домино и размерами оставшихся прямоугольников.

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

Докажем, что количество таких слов длины n - это (n+2)-е число Фибоначчи. В самом деле, слов длины 1 всего два (а и б), длины 2 - три (аа, аб и ба). Любое слово длины n получается так: либо к слову длины n-1 добавляем букву а справа, либо к слову длины n-2 добавляем аб справа. Таким образом, количество слов длины n из букв а и б, так что никакие две б не стоят подряд, равно (n+2)-му числу Фибоначчи.

Кроличьи числа получаются так. Первое кроличье число равно 0, второе — 1, третье — 10, четвёртое — 101, пятое — 10110, и т. д. Каждое следующее кроличье число получается из предыдущего заменой каждого 0 на 1, а каждой 1 — на 10. А сколько нулей в десятом кроличьем числе?

Вспомним задачу "Фибоначчи-2" (про кроликов). Пусть 0 - новорождённая пара кроликов, 1 - взрослая пара кроликов. Тогда превращение 0 в 1 и 1 в 10 в точности соответствует задаче "Фибоначчи-2": новорождённая пара кроликов за месяц превращается во взрослую, а взрослая приносит потомство. Значит, количество нулей в n-м кроличьем числе равно количеству пар новорождённых кроликов в n-й месяц у Фибоначчи, т.е. (n-2)-е число Фибоначчи.

При решении этой задачи:
Во-первых, надо убедиться, что учащиеся понимают процесс генерации кроличьих чисел. Можно предложить им написать несколько первых чисел вручную, чтобы увидеть закономерности.

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

Лягушка находится в первой клетке доски $1\times 10$. Она может прыгать на одну или на две клетки вперёд. Сколькими способами она может допрыгать до последней клетки?

Напишем в каждой клетке количество способов, которым лягушка может допрыгать до данной клетки. В первой клетке написано 1 (лягушка и так сидит в клетке), на второй тоже 1 (лягушке нужно просто передвинуться в соседнюю клетку, больше ей делать ничего не надо). А в n-й клетке будет стоять сумма чисел в (n-1)-й клетке (оттуда лягушка сможет сделать шаг на соседнюю клетку и попасть на n-ю) и в (n-2)-й клетке (оттуда лягушка сможет сделать прыжок на две клетки и тоже оказаться в n-й клетке).

Фибоначчи приобрел пару кроликов. Природа кроликов такова, что каждая пара кроликов раз в месяц производит на свет еще пару кроликов, а новорожденные приносят первое потомство уже через два месяца после рождения. Сколько пар кроликов будет у Фибоначчи на 6 месяц?

Можно непосредственно сосчитать, сколько будет пар кроликов. А можно доказать, что количество пар кроликов на n-й месяц будет n-м числом Фибоначчи.

В самом деле, в первые два месяца у Фибоначчи одна пара кроликов. В начале нового месяца у Фибоначчи сохраняются все прежние пары и нарождаются новые. Сколько новых пар нарождается? Они рождаются у тех пар кроликов, которые к этому моментк стали взрослыми, т.е. которые существовали два месяца назад. То есть количество пар кроликов в начале месяца - это количество пар кроликов месяц назад, сложенное с количеством пар кроликов два месяца назад.

Числа Фибоначчи задаются так. Первое и второе число Фибоначчи равно 1. А каждое следующее число Фибоначчи есть сумма двух предыдущих чисел Фибоначчи. Числа Фибоначчи делятся на 4 тогда и только тогда, когда их номера делятся на… На что?

Рассмотрим остатки чисел Фибоначчи по модулю 4: 1, 1, 2, 3, 1, 0, 1, 1,... После этого остатки зациклятся, т.к. остаток числа Фибоначчи зависит только от остатков двух предыдущих чисел Фибоначчи.

Числа Фибоначчи задаются так. Первое и второе число Фибоначчи равно 1. А каждое следующее число Фибоначчи есть сумма двух предыдущих чисел Фибоначчи. Найдите первые 12 чисел Фибоначчи и запишите их через запятую.