Выберите серию
Найдите количество слов длины 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)-е число Фибоначчи.
При решении этой задачи:
Во-первых, надо убедиться, что учащиеся понимают процесс генерации кроличьих чисел. Можно предложить им написать несколько первых чисел вручную, чтобы увидеть закономерности.
Во-вторых, обратить внимание на структуру кроличьих чисел. Можно попросить учащихся проанализировать, как количество нулей и единиц меняется с каждым шагом.
Кроличьи числа получаются так. Первое кроличье число равно 0, второе — 1, третье — 10, четвёртое — 101, пятое — 10110, и т. д. Каждое следующее кроличье число получается из предыдущего заменой каждого 0 на 1, а каждой 1 — на 10. Сколько цифр в десятом кроличьем числе?
Ответ:
Варианты ответов:
Вспомним задачу "Фибоначчи-2" (про кроликов). Пусть 0 - новорождённая пара кроликов, 1 - взрослая пара кроликов. Тогда превращение 0 в 1 и 1 в 10 в точности соответствует задаче "Фибоначчи-2": новорождённая пара кроликов за месяц превращается во взрослую, а взрослая приносит потомство. Значит, количество цифр в n-м кроличьем числе равно количеству пар кроликов в n-й месяц у Фибоначчи.
Лягушка находится в первой клетке доски $1\times 10$. Она может прыгать на одну или на две клетки вперёд. Сколькими способами она может допрыгать до последней клетки?
Ответ:
Варианты ответов:
Напишем в каждой клетке количество способов, которым лягушка может допрыгать до данной клетки. В первой клетке написано 1 (лягушка и так сидит в клетке), на второй тоже 1 (лягушке нужно просто передвинуться в соседнюю клетку, больше ей делать ничего не надо). А в n-й клетке будет стоять сумма чисел в (n-1)-й клетке (оттуда лягушка сможет сделать шаг на соседнюю клетку и попасть на n-ю) и в (n-2)-й клетке (оттуда лягушка сможет сделать прыжок на две клетки и тоже оказаться в n-й клетке).
Фибоначчи приобрел пару кроликов. Природа кроликов такова, что каждая пара кроликов раз в месяц производит на свет еще пару кроликов, а новорожденные приносят первое потомство уже через два месяца после рождения. Сколько пар кроликов будет у Фибоначчи на 6 месяц?
Ответ:
Варианты ответов:
Можно непосредственно сосчитать, сколько будет пар кроликов. А можно доказать, что количество пар кроликов на n-й месяц будет n-м числом Фибоначчи.
В самом деле, в первые два месяца у Фибоначчи одна пара кроликов. В начале нового месяца у Фибоначчи сохраняются все прежние пары и нарождаются новые. Сколько новых пар нарождается? Они рождаются у тех пар кроликов, которые к этому моментк стали взрослыми, т.е. которые существовали два месяца назад. То есть количество пар кроликов в начале месяца - это количество пар кроликов месяц назад, сложенное с количеством пар кроликов два месяца назад.