Всего: 5 1–5
Добавить в вариант
Симметричную монету подбросили n раз. Найдите вероятность того, что не встретились два последовательных броска, в которых наблюдался орел?
Введем обозначения: О — орел, Р — решка. Пусть Sn — число последовательностей из О и Р длины n, в которых нет двух последовательных символов О (такие последовательности будем называть корректными). Очевидно, что и Найдем рекуррентную формулу для вычисления Sn при Рассмотрим всевозможные последовательности длины n оканчивающиеся на P. Очевидно, что такая последовательность будет корректной, тогда и только тогда, когда будет корректной последовательность без последнего символа Р. Но таких последовательностей ровно Теперь рассмотрим все последовательности длины n оканчивающиеся на О. Очевидно, что такая последовательность будет корректной, тогда и только тогда, когда будет корректной последовательность без последних двух символов Р и О (предпоследний символ
Получаем рекуррентную формулу для вычисления Sn:
Ответ:
Имеется пирамида, составленная из 10 колец разного диаметра, надетых на палочку так, что меньшее кольцо всегда лежит на большем. Требуется переложить эти кольца на другую палочку (используя вспомогательную третью); при этом запрещено класть большее кольцо на меньшее. Какое наименьшее число перекладываний потребуется?
Это известная задача о Ханойской башне, которую часто рассматривают среди первых задач на метод математической индукции. Собственно говоря, для решения этой задачи нам не требуется использовать метод математической индукции, поскольку в ее условии дано конкретное число колец. Разобрав случаи получим, что потребуются, соответственно, одно, три или семь перекладываний. Для того, чтобы переложить «башню» из четырех колец, необходимо: снять верхние три кольца, затем переложить нижнее кольцо на свободную палочку и, наконец, положить на него три кольца меньшего диаметра. Таким образом, потребуются перекладываний. Решим задачу для произвольного числа n колец. Из приведенного рассуждения сразу следует рекуррентная формула для чисел pn наименьшего числа перекладываний для башни, состоящей из n колец:
Действительно, для того, чтобы переложить нижнее, -е, кольцо, нам вначале надо переложить n лежащих над ним колец, на что будут затрачено pn перекладываний. Затем мы переложим нижнее кольцо и потратим еще pn перекладываний, чтобы поместить на нем n верхних колец. Нетрудно догадаться, что После этого осталось сделать последний шаг, состоящий в применении метода математической индукции для доказательства найденной формулы. Таким образом, осталось решить следующую задачу: известно, что и для всех n Докажите, что База индукции: Индукционный переход: если то
Задача о ханойской башне является одной из лучших задач на индукционный метод рассуждения, в ее решении собственно «метод математической индукции» играет не слишком содержательную роль. Анализ приведенного решения показывает, что существо решения — в построении так называемого рекурсивного алгоритма.
Ответ:
В задаче номер 4 мы описывали все слова в алфавите {a, b}, разбивающиеся на чередующиеся блоки из букв a и букв b нечётной длины.
Найдите количество таких слов длины 8.
Переборное решение.
Поскольку каждый блок имеет нечётную длину, в слово длины 8 состоит из чётного числа блоков (от 2 до 8). Посчитаем количество способов разбить 8 букв на блоки, а затем умножим это количество на 2, так как каждому разбиению соответствуют два слова, одно из которых начинается на a, а второе на b. Если блоков 8, разбиение на блоки однозначно: в каждом по одной букве. Если блоков 6, то у нас 6 способов выбрать среди них тот, который будет иметь
Если блока 4, то у нас два случая: один блок имеет длину 5, остальные длину 1 (это 4 варианта) или два блока имеют длину 3, а оставшиеся два длину 1 (ещё 6 вариантов).
Наконец, если блоков 2, то всё определяется длиной первого блока, которая может принимать нечётные значения от 1 до 7 (4 варианта). Итоговый ответ
Рекуррентное решение.
Заметим, что количество слов длины n, начинающихся с а и с b совпадают. Обозначим это количество за Слово, начинающееся с буквы a может начинаться с ab, если вторая буква b, таких слов Если же вторая буква a, то и третья тоже a. Отделим первые две буквы, и у нас получится слово из букв, начинающееся на a. Таких слов Получаем рекуррентную формулу то есть формулу для чисел Фибоначчи. Значит, ответ это удвоенное число Фибоначчи с соответствующим номером, т. е.
Ответ: 42.
Найдите и докажите явное выражение (в терминах известных операций на целых числах) для общего члена последовательности, заданной следующей рекуррентным отношением: и для
Начнём с того, что вычислим несколько первых членов последовательности:
1) по определению;
2)
3)
4)
Можно заметить, что ! для первых пяти членов последовательности (то есть для всех [0. .4]).
Докажем индукцией по n, что для всех
База индукции, и уже рассмотрена выше (см. вычисление первых членов последовательности).
Индукционная гипотеза: пусть для всех
Шаг индукции:
Ответ: в соответствии с принципом математической индукции, для всех
В школе математики и программирования лестница с первого этажа на второй этаж состоит из двух пролетов, состоящих из 8 и 9 ступенек. Сколькими способами десятиклассник Вася может спуститься по ней, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки?
Найдем рекуррентную формулу, которая выражает число Nk способов для десятиклассника Васи спуститься по лестнице, состоящей из k ступенек, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки.
Если тогда у Васи имеется только единственный способ остаться на начальном месте — не шагать, поэтому
Если тогда у Васи имеется только один способ спуститься по лестнице, состоящей из одной ступеньки, то есть шагнуть на следующую ступеньку с начальной нулевой ступеньки, то есть
Если тогда у Васи имеется два способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через ступеньку с начальной нулевой ступеньки, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку со второй ступеньки, на которую можно попасть двумя способами, или перешагнуть через ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через две ступеньки с начальной нулевой ступеньки, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с третьей ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку со второй ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с первой ступеньки, на которую можно попасть способом; то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с четвертой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с третьей ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки со второй ступеньки, на которую можно попасть способом, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с пятой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с четвертой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с третьей ступеньки, на которую можно попасть способом, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с шестой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с пятой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с четвертой ступеньки, на которую можно попасть способом, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с седьмой ступеньки; на которую можно попасть способами, или перешагнуть через ступеньку с шестой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с пятой ступеньки, на которую можно попасть способом; то есть
Наконец, если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с восьмой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с седьмой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с шестой ступеньки, на которую можно попасть способом, то есть
Так как на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, поэтому нужно перемножить полученные два числа вариантов N8 и N9, то есть искомое число вариантов равно произведению
Заметим, что нами получена рекуррентная формула которая справедлива для любого натурального k.
Ответ:
Приведем другое решение.
Заметим, на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, поэтому можно найти число способов спуститься для каждого пролета в отдельности и перемножить полученные два числа вариантов.
Решим задачу для пролета, состоящего из 8 ступенек. Будем нумеровать ступеньки цифрами от 0 до 8, где цифра 0 означает самую верхнюю ступеньку, цифра 8 самую нижнюю ступеньку, а один шаг будем обозначать в виде a – b, где a и b — номера ступенек, на которых находился Вася за время этого шага. Также будем писать число ступенек, которые преодолел Вася за время шага.
Вася может перепрыгнуть через две ступеньки на третью ступеньку не более двух раз. Он может перепрыгнуть через две ступеньки два раза несколькими способами.
Если оставшиеся две ступеньки он преодолевает одним шагом, то имеется всего три варианта:
Шаги | 0−3−6−8 | 0−3−5−8 | 0−2−5−8 |
Число ступенек | 3, 3, 2 | 3, 2, 3 | 2, 3, 3 |
Если же оставшиеся две ступеньки он преодолевает двумя шагами, то имеется всего шесть вариантов:
Шаги | 0−3−6−7−8 | 0−3−4−5−8 | 0−1−2−5−8 |
Число ступенек | 3, 3, 1, 1 | 3, 1, 1, 3 | 1, 1, 3, 3, |
Шаги | 0−3−4−7−8 | 0−1−4−5−8 | 0−1−4−7−8 |
Число ступенек | 3, 1, 3, 1 | 1, 3, 1, 3 | 1, 3, 1, 3 |
Таким образом, получаем вариантов.
Вася перепрыгнуть через две ступеньки один раз несколькими способами, для каждого варианта запишем для краткости только число ступенек.
Число | 3, 1, 1, 1, 1, 1 | 3, 1, 1, 1, 2 | 3, 1, 1, 2, 1 | 3, 1, 2, 1, 1 | 3, 2, 1, 1, 1 |
ступенек | 3, 1, 2, 2 | 3, 2, 1, 2 | 3, 2, 2, 1 | ||
1, 3, 1, 1, 1, 1 | 1, 3, 1, 1, 2 | 1, 3, 1, 2, 1 | 1, 3, 2, 1, 1 | 1, 3, 2, 2 | |
1, 1, 3, 1, 1, 1 | 1, 1, 3, 1, 2 | 1, 1, 3, 2, 1 | |||
2, 3, 1, 1, 1 | 2, 3, 1, 2 | 2, 3, 2, 1 |
Полученное число вариантов нужно умножить н 2 из-за симметрии относительно середины лестничного пролета. Таким образом, получаем вариантов. Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.
Если Вася перепрыгнул через одну ступеньку четыре раза, то такой вариант один: 0−2−4−6−8.
Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить две единицы рядом с тремя двойками. При этом есть четыре вариант а расставить единицы рядом.
Число ступенек | 2, 2, 2, 1, 1 | 2, 2, 1, 1, 2 | 2, 1, 1, 2, 2 | 1, 1, 2, 2, 2 |
A также есть
Число ступенек | 2, 2, 1, 2, 1 | 2, 1, 2, 2, 1 | 1, 2, 2, 2, 1 | 2, 1, 2, 1, 2 |
1, 2, 2, 1, 2 | 1, 2, 1, 2, 2 |
Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки рядом с четырьмя единицами.
При этом есть пять вариантов расставить двойки рядом.
Число ступенек | 2, 2, 1, 1, 1, 1 | 1, 2, 2, 1, 1, 1 | 1, 1, 2, 2, 1, 1 | 1, 1, 1, 2, 2, 1 |
1, 1, 1, 1, 2, 2 |
А также есть — десять вариантов расставить двойки не рядом.
Число ступенек | 2, 1, 2, 1, 1, 1 | 2, 1, 1, 2, 1, 1 | 2, 1, 1, 1, 2, 1 | 2, 1, 1, 1, 1, 2 |
1, 2, 1, 2, 1, 1 | 1, 2, 1, 1, 2, 1 | 1, 2, 1, 1, 1, 2 | 1, 1, 2, 1, 2, 1 | |
1, 1, 2, 1, 1, 2 | 1, 1, 1, 2, 1, 2 |
Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить одну двойку рядом с шестью единицами, то есть имеется семь вариантов.
Число ступенек | 2, 1, 1, 1, 1, 1, 1 | 1, 2, 1, 1, 1, 1, 1 | 1, 1, 2, 1, 1, 1, 1 | 1, 1, 1, 2, 1, 1, 1 |
1, 1, 1, 1, 2, 1, 1 | 1, 1, 1, 1, 1, 2, 1 | 1, 1, 1, 1, 1, 1, 2 |
Наконец, если Вася вообще не перепрыгивал через ступеньки, тогда имеется только один вариант: 0−1−2−3−4−5−6−7−8 с числом ступенек 1, 1, 1, 1, 1, 1, 1, 1.
Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно
Таким образом, искомое число вариантов для пролета из 8 ступенек равно
Теперь решим задачу для пролета, состоящего из 9 ступенек. Будем нумеровать ступеньки цифрами от 0 до 9, где цифра 0 означает самую верхнюю ступеньку, цифра 9 — самую нижнюю ступеньку.
Вася может перепрыгнуть через две ступеньки на третью ступеньку не более трех paз.
Если Вася перепрыгнул через две ступеньки на третью ступеньку три раза, то имеется только один вариант: 0−3−6−9. Поэтому получаем вариант.
Вася может перепрыгнуть через две ступеньки дв раза несколькими способами. Оставшиеся три ступеньки он может преодолеть по разному.
Если он один раз перепрыгивает через одну ступеньку, то имеется двенадцать вариантов:
Шаги | 0−3−6−8−9 | 0−3−5−8−9 | 0−2−5−8−9 |
Число ступенек | 3, 3, 2, 1 | 3, 2, 3, 1 | 2, 3, 3, 1 |
Шаги | 0−3−6−7−9 | 0−3−5−6−9 | 0−2−5−6−9 |
Число ступенек | 3, 3, 1, 2 | 3, 2, 1, 3 | 2, 3, 1, 3 |
Шаги | 0−3−4−7−9 | 0−3−4−6−9 | 0−2−3−6−9 |
Число ступенек | 3, 1, 3, 2 | 3, 1, 2, 3 | 2, 1, 3, 3 |
Шаги | 0−1−4−7−9 | 0−1−4−6−9 | 0−1−3−6−9 |
Число ступенек | 1, 3, 3, 2 | 1, 3, 2, 3 | 1, 2, 3, 3 |
Если же оставшиеся три ступеньки он преодолевает тремя шагами, то имеется всего десять вариантов:
Шаги | 0−3−6−7−8−9 | 0−3−4−5−6−9 | 0−1−2−3−6−9 |
Число ступенек | 3, 3, 1, 1, 1 | 3, 1, 1, 1, 3 | 1, 1, 1, 3, 3 |
Шаги | 0−3−4−7−8−9 | 0−1−4−7−8−9 | 0−3−4−5−8−9 |
Число ступенек | 3, 1, 3, 1, 1 | 1, 3, 3, 1, 1 | 3, 1, 1, 3, 1 |
Шаги | 0−1−4−5−6−9 | 0−1−2−5−8−9 | 0−1−2−5−6−9 |
Число ступенек | 1, 3, 1, 1, 3 | 1, 1, 3, 3, 1 | 1, 1, 3, 1, 3 |
Шаги | 0−1−4−5−8−9 | ||
Число ступенек | 1, 3, 1, 3, 1 |
Таким образом, получаем варианта.
Вася может перепрыгнуть через две ступеньки один раз несколькими способами. Оставшиеся шесть ступенек он может преодолеть по разному.
Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить три двойки рядом с одной тройкой, то есть имеется четыре варианта. Для каждого варианта запишем для краткости только число ступенек.
Число ступенек | 2, 2, 2, 3 | 2, 2, 3, 2 | 2, 3, 2, 2 | 3, 2, 2, 2 |
Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки и две единицы рядом с одной тройкой, то есть имеется тридцать таких вариантов.
Число | 2, 2, 3, 1, 1 | 2, 2, 1, 1, 3 | 2, 1, 1, 2, 3 | 1, 1, 2, 2, 3 | |
ступенек | 2, 2, 1, 3, 1 | 2, 1, 2, 3, 1 | 1, 2, 2, 3, 1 | 2, 1, 2, 1, 3 | 1, 2, 2, 1, 3 |
1, 2, 1, 2, 3 | |||||
2, 3, 2, 1, 1 | 2, 3, 1, 1, 2 | 2, 1, 1, 3, 2 | 1, 1, 2, 3, 2 | ||
2, 3, 1, 2, 1 | 2, 1, 3, 2, 1 | 1, 2, 3, 2, 1 | 2, 1, 3, 1, 2 | 1, 2, 3, 1, 2 | |
1, 2, 1, 3, 2 | |||||
3, 2, 2, 1, 1 | 3, 2, 1, 1, 2 | 3, 1, 1, 2, 2 | 1, 1, 3, 2, 2 | ||
3, 2, 1, 2, 1 | 3, 1, 2, 2, 1 | 1, 3, 2, 2, 1 | 3, 1, 2, 1, 2 | 1, 3, 2, 1, 2 | |
1, 3, 1, 2, 2 |
Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить четыре единицы рядом с одной двойкой и одной тройкой, то есть имеется тридцать таких вариантов.
Число | 2, 3, 1, 1, 1, 1 | 2, 1, 1, 1, 1, 3 | 1, 1, 1, 1, 2, 3 | ||
ступенек | 2, 1, 3, 1, 1, 1 | 1, 2, 3, 1, 1, 1 | 2, 1, 1, 1, 3, 1 | 1, 2, 1, 1, 1, 3 | 1, 1, 1, 2, 3, 1 |
1, 1, 1, 2, 1, 3 | |||||
2, 1, 1, 3, 1, 1 | 1, 1, 2, 3, 1, 1 | 1, 1, 2, 1, 1, 3 | |||
1, 2, 1, 3, 1, 1 | 1, 2, 1, 1, 3, 1 | 1, 1, 2, 1, 3, 1 | |||
3, 1, 2, 1, 1, 1 | 1, 3, 2, 1, 1, 1 | 3, 1, 1, 1, 2, 1 | 1, 3, 1, 1, 1, 2 | 1, 1, 1, 3, 2, 1 | |
1, 1, 1, 3, 1, 2 | |||||
3, 1, 1, 2, 1, 1 | 1, 1, 3, 2, 1, 1 | 1, 1, 3, 1, 1, 2 | |||
1, 3, 1, 2, 1, 1 | 1, 3, 1, 1, 2, 1 | 1, 1, 3, 1, 2, 1 |
Если же Вася ни разу не перепрыгнул через одну ступеньку, то таких вариантов несколько. Это число равно числу вариантов расставить шесть единиц рядом с одной тройкой, то есть имеется семь таких вариантов.
Число ступенек | 3, 1, 1, 1, 1, 1, 1 | 1, 3, 1, 1, 1, 1, 1 | 1, 1, 3, 1, 1, 1, 1 | 1, 1, 1, 3, 1, 1, 1 |
1, 1, 1, 1, 3, 1, 1 | 1, 1, 1, 1, 1, 3, 1 | 1, 1, 1, 1, 1, 1, 3 |
Таким образом, получаем вариант.
Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.
Если Вася перепрыгнул через одну ступеньку четыре раза, то таких вариантов несколько. Это число равно числу вариантов расставить одну единицу рядом с четырьмя Двойками, то есть имеется пять вариантов.
Число ступенек | 2, 2, 2, 2, 1 | 2, 2, 2, 1, 2 | 2, 2, 1, 2, 2 | 2, 1, 2, 2, 2 |
1, 2, 2, 2, 2 |
Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить три единицы рядом с тремя двойками.
При этом есть четыре варианта расставить единицы рядом.
Число ступенек | 2, 2, 2, 1, 1, 1 | 2, 2, 1, 1, 1, 2 | 2, 1, 1, 1, 2, 2 | 1, 1, 1, 2, 2, 2 |
И есть
Число ступенек | 2, 2, 1, 2, 1, 1 | 2, 1, 2, 2, 1, 1 | 1, 2, 2, 2, 1, 1 | |
2, 2, 1, 1, 2, 1 | 2, 1, 2, 1, 1, 2 | 1, 2, 2, 1, 1, 2 | ||
2, 1, 1, 2, 2, 1 | 2, 1, 1, 2, 1, 2 | 1, 2, 1, 1, 2, 2 | ||
1, 1, 2, 2, 2, 1 | 1, 1, 2, 2, 1, 2 | 1, 1, 2, 1, 2, 2 |
А также есть — четыре варианта расставить единички не рядом.
Число ступенек | 2, 1, 2, 1, 2, 1 | 1, 2, 2, 1, 2, 1 | 1, 2, 1, 2, 2, 1 | 1, 2, 1, 2, 1, 2 |
Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки рядом с пятью единицами.
При этом есть шесть вариантов расставить двойки рядом.
Число ступенек | 2, 2, 1, 1, 1, 1, 1 | 1, 2, 2, 1, 1, 1, 1 | 1, 1, 2, 2, 1, 1, 1 | 1, 1, 1, 2, 2, 1, 1 |
1, 1, 1, 1, 2, 2, 1 | 1, 1, 1, 1, 1, 2, 2 |
А также есть — пятнадцать вариантов расставить двойки не рядом.
Число ступенек | 2, 1, 2, 1, 1, 1, 1 | 2, 1, 1, 2, 1, 1, 1 | 2, 1, 1, 1, 2, 1, 1 | 2, 1, 1, 1, 1, 2, 1 |
2, 1, 1, 1, 1, 1, 2 | 1, 2, 1, 2, 1, 1, 1 | 1, 2, 1, 1, 2, 1, 1 | 1, 2, 1, 1, 1, 2, 1 | |
1, 2, 1, 1, 1, 1, 2 | 1, 1, 2, 1, 2, 1, 1 | 1, 1, 2, 1, 1, 2, 1 | 1, 1, 2, 1, 1, 1, 2 | |
1, 1, 1, 2, 1, 2, 1 | 1, 1, 1, 2, 1, 1, 2 | 1, 1, 1, 1, 2, 1, 2 |
Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить одну двойку рядом с семью единицами, то есть имеется восемь вариантов.
число ступенек | 2, 1, 1, 1, 1, 1, 1, 1 | 1, 2, 1, 1, 1, 1, 1, 1 | 1, 1, 2, 1, 1, 1, 1, 1 | 1, 1, 1, 2, 1, 1, 1, 1 |
1, 1, 1, 1, 2, 1, 1, 1 | 1, 1, 1, 1, 1, 2, 1, 1 | 1, 1, 1, 1, 1, 1, 2, 1 | 1, 1, 1, 1, 1, 1, 1, 2 |
Наконец, если Вася вообще не перепрыгивал через ступеньки, тогда имеется только один вариант: 0−1−2−3−4−5−6−7−8−9 с числом ступенек 1, 1, 1, 1, 1, 1, 1, 1, 1.
Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно
Таким образом, искомое число вариантов для пролета из 9 ступенек равно
Наконец, искомое число вариантов равно произведению
Наверх