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