Условие
По сетке нужно пройти из (0;0) в (5;3), каждый шаг — на единицу вправо или вверх. Через точку (1;1) проходить нельзя. Сколько существует путей?
Подсказка
Всего 8 шагов, из которых 3 вверх. Выбираем их места: C(8,3)=56.
До (1;1) есть 2 пути. От неё остаются 4 шагов вправо и 2 вверх: C(6,2)=15. Запрещённых путей 2·15=30.
Показать ответ
26
Пошаговое решение
- Считаем все кратчайшие пути
Всего 8 шагов, из которых 3 вверх. Выбираем их места: C(8,3)=56.
- Считаем запрещённые пути
До (1;1) есть 2 пути. От неё остаются 4 шагов вправо и 2 вверх: C(6,2)=15. Запрещённых путей 2·15=30.
- Вычитаем
Каждый запрещённый путь проходит эту точку ровно один раз. Допустимых 56−30=26.
Ответ: 26