РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 7739 Добавить в вариант

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

Спрятать решение

Решение.

Найдем рекуррентную формулу, которая выражает число N_k способов для десятиклассника Васи спуститься по лестнице, состоящей из k ступенек, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки.

Если $k=0,$ тогда у Васи имеется только единственный способ остаться на начальном месте  — не шагать, поэтому $N_0=1.$

Если $k=1,$ тогда у Васи имеется только один способ спуститься по лестнице, состоящей из одной ступеньки, то есть шагнуть на следующую ступеньку с начальной нулевой ступеньки, то есть $N_1=N_0=1.$

Если $k=2,$ тогда у Васи имеется два способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через ступеньку с начальной нулевой ступеньки, то есть

$N_2=N_0 плюс N_1=1 плюс 1=2.$

Если $k=3,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку со второй ступеньки, на которую можно попасть двумя способами, или перешагнуть через ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через две ступеньки с начальной нулевой ступеньки, то есть

$N_3=N_0 плюс N_1 плюс N_2=1 плюс 1 плюс 2=4.$

Если $k=4,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с третьей ступеньки, на которую можно попасть $N_3=4$ способами, или перешагнуть через ступеньку со второй ступеньки, на которую можно попасть $N_2=2$ способами, или перешагнуть через две ступеньки с первой ступеньки, на которую можно попасть $N_1=1$ способом; то есть

$N_4=N_1 плюс N_2 плюс N_3=1 плюс 2 плюс 4=7 .$

Если $k=5,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с четвертой ступеньки, на которую можно попасть $N_4=7$ способами, или перешагнуть через ступеньку с третьей ступеньки, на которую можно попасть $N_3=4$ способами, или перешагнуть через две ступеньки со второй ступеньки, на которую можно попасть $N_2=2$ способом, то есть

$N_5=N_2 плюс N_3 плюс N_4=2 плюс 4 плюс 7=13 .$

Если $k=6,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с пятой ступеньки, на которую можно попасть $N_5=13$ способами, или перешагнуть через ступеньку с четвертой ступеньки, на которую можно попасть $N_4=7$ способами, или перешагнуть через две ступеньки с третьей ступеньки, на которую можно попасть $N_3=4$ способом, то есть

$N_6=N_3 плюс N_4 плюс N_5=4 плюс 7 плюс 13=24 .$

Если $k=7,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с шестой ступеньки, на которую можно попасть $N_6=24$ способами, или перешагнуть через ступеньку с пятой ступеньки, на которую можно попасть $N_5=13$ способами, или перешагнуть через две ступеньки с четвертой ступеньки, на которую можно попасть $N_4=5$ способом, то есть

$N_7=N_4 плюс N_5 плюс N_6=7 плюс 13 плюс 24=44 .$

Если $k=8,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с седьмой ступеньки; на которую можно попасть $N_7=44$ способами, или перешагнуть через ступеньку с шестой ступеньки, на которую можно попасть $N_6=24$ способами, или перешагнуть через две ступеньки с пятой ступеньки, на которую можно попасть $N_5=13$ способом; то есть

$N_8=N_5 плюс N_6 плюс N_7=13 плюс 24 плюс 44=81.$

Наконец, если $k=9,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с восьмой ступеньки, на которую можно попасть $N_8=81$ способами, или перешагнуть через ступеньку с седьмой ступеньки, на которую можно попасть $N_7=44$ способами, или перешагнуть через две ступеньки с шестой ступеньки, на которую можно попасть $N_6=24$ способом, то есть

$N_9=N_6 плюс N_7 плюс N_8=24 плюс 44 плюс 81=149.$

Так как на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, поэтому нужно перемножить полученные два числа вариантов N₈ и N₉, то есть искомое число вариантов равно произведению

$M=N_8 умножить на N_9=81 умножить на 149=12 069.$

Заметим, что нами получена рекуррентная формула $N_k плюс 3=N_k плюс N_k плюс 1 плюс N_k плюс 2 :$ которая справедлива для любого натурального k.

Ответ: $M=12 069.$

Приведем другое решение.

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

Решим задачу для пролета, состоящего из 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

Таким образом, получаем $n_2=9$ вариантов.

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

Число	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 из-за симметрии относительно середины лестничного пролета. Таким образом, получаем $n_1=2 умножить на 19=38$ вариантов. Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.

Если Вася перепрыгнул через одну ступеньку четыре раза, то такой вариант один: 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 также есть $C_4 в квадрате =6$   — шесть вариантов расставить единички не рядом.

Число ступенек	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

А также есть $C_5 в квадрате =10$   — десять вариантов расставить двойки не рядом.

Число ступенек	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.

Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно

$n_0=1 плюс 4 плюс 6 плюс 5 плюс 10 плюс 7 плюс 1=34.$

Таким образом, искомое число вариантов для пролета из 8 ступенек равно

$N_8=n_2 плюс n_1 плюс n_0=9 плюс 38 плюс 34=81.$

Теперь решим задачу для пролета, состоящего из 9 ступенек. Будем нумеровать ступеньки цифрами от 0 до 9, где цифра 0 означает самую верхнюю ступеньку, цифра 9  — самую нижнюю ступеньку.

Вася может перепрыгнуть через две ступеньки на третью ступеньку не более трех paз.

Если Вася перепрыгнул через две ступеньки на третью ступеньку три раза, то имеется только один вариант: 0−3−6−9. Поэтому получаем $m_3=1$ вариант.

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

Если он один раз перепрыгивает через одну ступеньку, то имеется двенадцать вариантов:

Шаги	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

Таким образом, получаем $m_2=12 плюс 10=22$ варианта.

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

Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить три двойки рядом с одной тройкой, то есть имеется четыре варианта. Для каждого варианта запишем для краткости только число ступенек.

Число ступенек

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

Таким образом, получаем $m_1=4 плюс 30 плюс 30 плюс 7=71$ вариант.

Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.

Если Вася перепрыгнул через одну ступеньку четыре раза, то таких вариантов несколько. Это число равно числу вариантов расставить одну единицу рядом с четырьмя Двойками, то есть имеется пять вариантов.

Число ступенек	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

И есть $4 умножить на 3=12$   — двенадцать вариантов расставить только две единицы рядом.

Число ступенек	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

А также есть $C_4 в кубе =4$   — четыре варианта расставить единички не рядом.

Число ступенек

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

А также есть $C_6 в квадрате =15$   — пятнадцать вариантов расставить двойки не рядом.

Число ступенек	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.

Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно

$n_0=5 плюс 4 плюс 12 плюс 4 плюс 6 плюс 15 плюс 8 плюс 1=55.$

Таким образом, искомое число вариантов для пролета из 9 ступенек равно

$N_9=m_3 плюс m_2 плюс m_1 плюс m_0=1 плюс 22 плюс 71 плюс 55=149.$

Наконец, искомое число вариантов равно произведению

$M=N_8 умножить на N_9=81 умножить на 149=12 069.$

Межрегиональная олимпиада школьников по математике САММАТ, 10 класс, 2 тур (заключительный), 2022 год

Классификатор: Комбинаторика, вероятность, статистика. Размещения, перестановки и сочетания, Комбинаторика, вероятность, статистика. Рекуррентные соотношения в комбинаторике

Спрятать решение · Помощь