Question

Вася стоит на первой ступеньке свежепокрашенной лестницы и собирается подняться на самую верхнюю, двенадцатую ступеньку. Некоторые ступеньки лестницы, а именно, ступеньки с номерами 4 и 10 еще не до конца высохли, и наступать на них Вася не намерен. Сколькими способами Вася может добраться до последней ступеньки, если он готов шагнуть на следующую ступеньку или перешагнуть через одну ступеньку. Вниз Вася ни в какой момент не спускается. Комментарий. Если бы лестница состояла из четырех высохших ступенек, то Вася смог бы подняться с первой на четвертую тремя способами — шагая каждый раз на следующую ступеньку; сначала сделав шаг с первой на вторую, а потом сразу на четвертую; сначала с первой шагнув на третью, а потом с третьей на четвертую. Я рассматривал эту задачу постепенно - с 1 до 3 ступени - 2 способа (с 1-2-3 ступень и 1-3) 4 и 10 не считаем делаем шаг через ступеньку с 5 до 9 четыре способа (5-6-7-8-9) (5-7-9) (5-7-8-9) (5-6-8-9) делаем шаг через ступеньку - на 11ую с 11 на 12 можно попасть только одним способом - сделать шаг вверх получается всего 2+4+1=7 способов Правильно?

Answer 1

Все правильные способы

Answer 2

Нет, вы неправильно рассчитали количество способов. Давайте разберемся:

1. Сначала Вася может перейти с первой ступеньки на вторую.
2. Затем он может перейти с второй на третью.
3. Далее он может перейти с третьей на пятую ступеньку (пропуская четвертую).
4. С пятой ступеньки он может перейти на шестую, затем на седьмую, восьмую, девятую и десятую ступеньки.
5. Теперь Вася стоит на десятой ступеньке и готов перейти на одиннадцатую (пропустив одиннадцатую).
6. Наконец, он переходит с одиннадцатой ступеньки на двенадцатую (пропуская ее).

Таким образом, Вася может добраться до последней ступеньки 1 способом. Всего 1 способ, а не 7.