Логика и комбинаторика · 8–10 классыКомбинаторика: формулы

Число путей по сетке улиц

Сколько кратчайших маршрутов ведёт по клетчатой сетке улиц из A в B: перекрытые перекрёстки, обязательная точка, формула сочетаний.

Вариант № 31183

Число путей по сетке улиц · Вариант № 31183 · Обычный · Имя: ____________________

1
Из A в B ведут кратчайшие маршруты по сетке улиц 4×3 (только вправо и вверх). Сколько из них проходят через перекрёсток P?
Ответ: 12
Маршрут делится на два участка: от A до P ( $3$ вправо, $1$ вверх) и от P до B ( $1$ вправо, $2$ вверх).
Участки независимы: $C_{4}^{3}\cdot C_{3}^{1}=4\cdot 3=12$ .
2
Из A в B ведут кратчайшие маршруты по сетке улиц 4×4 (только вправо и вверх). Сколько из них проходят через перекрёсток P?
Ответ: 30
Маршрут делится на два участка: от A до P ( $1$ вправо, $2$ вверх) и от P до B ( $3$ вправо, $2$ вверх).
Участки независимы: $C_{3}^{1}\cdot C_{5}^{3}=3\cdot 10=30$ .
3
Робот-пылесос едет к зарядке по сетке улиц: 5 кварталов по горизонтали и 4 по вертикали. Из точки A (слева внизу) в точку B (справа вверху) можно идти только вправо или вверх. Сколько существует кратчайших маршрутов?
Ответ: 126
Любой кратчайший путь — это $5$ шагов вправо и $4$ шагов вверх в каком-то порядке.
Выбираем, какие из $9$ шагов идут вправо: $C_{9}^{5}=126$ .
4
Из A в B ведут кратчайшие маршруты по сетке улиц 3×4 (только вправо и вверх). Сколько из них проходят через перекрёсток P?
Ответ: 18
Маршрут делится на два участка: от A до P ( $2$ вправо, $2$ вверх) и от P до B ( $1$ вправо, $2$ вверх).
Участки независимы: $C_{4}^{2}\cdot C_{3}^{1}=6\cdot 3=18$ .
5
Из A в B ведут кратчайшие маршруты по сетке улиц 6×4 (только вправо и вверх). Сколько из них проходят через перекрёсток P?
Ответ: 24
Маршрут делится на два участка: от A до P ( $1$ вправо, $3$ вверх) и от P до B ( $5$ вправо, $1$ вверх).
Участки независимы: $C_{4}^{1}\cdot C_{6}^{5}=4\cdot 6=24$ .

Коротко о теме

Кратчайший путь из $A$ в $B$ состоит из $a$ шагов вправо и $b$ шагов вверх. Порядок шагов — любой.
Выбрать, на каких из $a+b$ шагов идти вправо: $C_{a+b}^a$ способов.
В каждый перекрёсток маршрут приходит сверху или слева: число путей в узел равно сумме чисел в соседних узлах (как в треугольнике Паскаля).
Закрытый перекрёсток обнуляет число путей в нём; обязательная точка $P$ делит маршрут на два участка — числа перемножаются.

Уровни: Разминка · Обычный · Challenge. Все ответы вычислены программой из тех же чисел, что и условие.

Ещё тренажёры

Раздел «Комбинаторика: формулы»

Другие темы: 8 класс