Логика и комбинаторика · 7–9 классыКомбинаторика: основы

Лесенка и числа Фибоначчи

Сколькими способами подняться по лестнице шагами в 1 и 2 ступени, вымостить дорожку плитками, составить цепочку без соседних единиц — всюду возникают числа Фибоначчи.

Вариант № 28929

Лесенка и числа Фибоначчи · Вариант № 28929 · Обычный · Имя: ____________________

1
Аня идёт вверх по ступенькам из 10 ступенек. За один шаг можно подняться на 1 или на 2 ступеньки. Сколькими способами Аня может подняться на самый верх?
Ответ: 89
Пусть $a_k$ — число способов подняться на $k$ -ю ступеньку. На неё приходят с $(k-1)$ -й или с $(k-2)$ -й, значит $a_k=a_{k-1}+a_{k-2}$ .
Считаем: $a_{1}=1$ , $a_{2}=2$ , $a_{3}=3$ , $a_{4}=5$ , $a_{5}=8$ , $a_{6}=13$ , $a_{7}=21$ , $a_{8}=34$ , $a_{9}=55$ , $a_{10}=89$ .
Ответ: $89$ .
2
Сколько существует последовательностей из 6 цифр, каждая из которых 0 или 1, в которых никакие две единицы не стоят рядом?
Ответ: 21
Если последовательность заканчивается нулём, перед ним любая допустимая цепочка из $m-1$ цифр. Если единицей, то перед ней обязательно 0, а перед ним — допустимая цепочка из $m-2$ цифр.
Значит, снова $b_m=b_{m-1}+b_{m-2}$ , числа Фибоначчи со сдвигом.
Ответ: $21$ .
3
Дорожку шириной в одну плитку и длиной 9 плиток выкладывают плитками двух видов: квадратными (занимают 1 клетку) и прямоугольными (занимают 2 клетки подряд). Сколькими способами можно выложить дорожку?
Ответ: 55
Посмотри на первую плитку: она занимает 1 клетку (остаётся $n-1$ ) или 2 клетки (остаётся $n-2$ ).
Значит, $a_n=a_{n-1}+a_{n-2}$ : числа Фибоначчи.
$a_{1}=1$ , $a_{2}=2$ , $a_{3}=3$ , $a_{4}=5$ , $a_{5}=8$ , $a_{6}=13$ , $a_{7}=21$ , $a_{8}=34$ , $a_{9}=55$ . Ответ: $55$ .
4
Дорожку шириной в одну плитку и длиной 10 плиток выкладывают плитками двух видов: квадратными (занимают 1 клетку) и прямоугольными (занимают 2 клетки подряд). Сколькими способами можно выложить дорожку?
Ответ: 89
Посмотри на первую плитку: она занимает 1 клетку (остаётся $n-1$ ) или 2 клетки (остаётся $n-2$ ).
Значит, $a_n=a_{n-1}+a_{n-2}$ : числа Фибоначчи.
$a_{1}=1$ , $a_{2}=2$ , $a_{3}=3$ , $a_{4}=5$ , $a_{5}=8$ , $a_{6}=13$ , $a_{7}=21$ , $a_{8}=34$ , $a_{9}=55$ , $a_{10}=89$ . Ответ: $89$ .
5
Егор взбирается на горку из 9 ступенек. За один шаг можно подняться на 1 или на 2 ступеньки. Сколькими способами Егор может подняться на самый верх?
Ответ: 55
Пусть $a_k$ — число способов подняться на $k$ -ю ступеньку. На неё приходят с $(k-1)$ -й или с $(k-2)$ -й, значит $a_k=a_{k-1}+a_{k-2}$ .
Считаем: $a_{1}=1$ , $a_{2}=2$ , $a_{3}=3$ , $a_{4}=5$ , $a_{5}=8$ , $a_{6}=13$ , $a_{7}=21$ , $a_{8}=34$ , $a_{9}=55$ .
Ответ: $55$ .

Коротко о теме

Последний шаг на ступеньку $n$ делается с ступеньки $n-1$ (шаг 1) или $n-2$ (шаг 2). Поэтому $a_n=a_{n-1}+a_{n-2}$ — каждое число равно сумме двух предыдущих.
Начало: $a_1=1$ , $a_2=2$ , дальше $3,5,8,13,21,34,\dots$ — числа Фибоначчи.
Те же числа считают плитки $1\times 1$ и $1\times 2$ в полосе и двоичные слова без двух единиц подряд.
Если одна ступенька запрещена, путь делится на два независимых участка — ответы перемножаются.

Уровни: Разминка · Обычный · Challenge. Все ответы вычислены программой из тех же чисел, что и условие.

Ещё тренажёры

Раздел «Комбинаторика: основы»

Другие темы: 7 класс