Маршруты на клетчатой сетке и сочетания
9 класс · Комбинаторика · расширено в v112
Цель и мотивация
Считать кратчайшие пути как последовательности шагов и решать задачи с запрещёнными точками и соседними шагами.
Робот идёт из угла решётки в противоположный и не может отступать назад. Количество маршрутов быстро растёт; простой перебор уже неудобен.
Определения и точные условия
- Кратчайший монотонный путь из (0;0) в (m;n) содержит ровно m шагов вправо и n шагов вверх.
- Число таких маршрутов C(m+n;m) = (m+n)!/(m!n!), где m,n — неотрицательные целые.
- Для прохождения через клетку P маршруты до P и после P выбираются независимо; их количества перемножаются. Для запрета клетки вычитаем пути через неё из всех путей.
Почему это работает: доказательство
Закодируем шаг вправо буквой П, а шаг вверх — буквой В. Любой кратчайший маршрут соответствует слову длины m+n с ровно n буквами В.
Достаточно выбрать, в каких n позициях будут буквы В. Число выборов равно C(m+n;n). Каждый выбор даёт ровно один маршрут, а разные выборы — разные маршруты.
Если последние шаги группировать по направлению, получим рекурсию F(m,n) = F(m−1,n)+F(m,n−1), что одновременно доказывает правило Паскаля для сочетаний.
Чертёж и модель
Подробный пример 1. Без ограничений
Условие. Сколько путей из (0;0) в (4;3), если разрешены только шаги вправо и вверх?
Разбор. Всего 7 шагов, из них 3 вверх. Выбираем места подъёмов: C(7;3) = 7·6·5/(3·2·1) = 35.
Ответ. 35.
Подробный пример 2. Через фиксированную точку
Условие. Сколько маршрутов из (0;0) в (4;3) проходят через (2;1)?
Разбор. До (2;1) нужно 2 шага вправо и 1 вверх: C(3;1)=3. После (2;1) нужно 2 вправо и 2 вверх: C(4;2)=6. По правилу произведения всего 3·6=18.
Ответ. 18.
Подробный пример 3. Запрещённая точка
Условие. Сколько маршрутов из (0;0) в (4;3) НЕ проходят через (2;1)?
Разбор. Из всех 35 маршрутов вычитаем 18 проходящих через запретную точку. Других условий нет, поэтому вычитание не создаёт двойного счёта.
Ответ. 17.
Типичные ошибки
- Считать кратчайшими маршруты, в которых есть шаги назад: минимальность тогда теряется.
- Складывать числа путей до точки и после вместо умножения.
- Забывать, что при нескольких запрещённых точках простое вычитание может дважды учесть один путь.
Упражнения: от простого к сложному
- Сколько путей из (0;0) в (3;2)?
- Сколько путей из (0;0) в (5;3)?
- Сколько путей из (0;0) в (4;4) проходят через (2;2)?
- Сколько путей из (0;0) в (4;4) обходят точку (2;2)?
- Докажите тождество C(n;k)=C(n−1;k)+C(n−1;k−1) разбором последнего шага.
Исследуем закономерность
Посчитайте пути на решётке 3×3 при запрете двух внутренних точек. Когда нужна формула включений–исключений?
Самостоятельные работы и PDF
Пять вариантов по десять заданий; проверка ответов производится на сервере. Обновлённый конспект v112 содержит подробные объяснения, задачи и доказательства. Ученические листы v111 и закрытые учительские решения сохранены.
Подробный конспект PDF (v112) · Листы заданий PDF · Онлайн-проверка
Подведём итог
Выбирайте позиции одинаковых шагов; для обязательной промежуточной точки перемножайте количества маршрутов, для одной запрещённой — вычитайте.