МЕХМАТИК / Математический центр знаний и творчестваОТ ЧИСЕЛ К ИДЕЯМ · ∀ x ∈ ℝ
МехматикМатематическая библиотека
Открытое обучение
КЛАССЫ1 класс2 класс3 класс4 класс5 класс6 класс7 класс8 класс9 класс10 класс11 класс

Маршруты на клетчатой сетке и сочетания

9 класс · Комбинаторика · расширено в v112

Цель и мотивация

Считать кратчайшие пути как последовательности шагов и решать задачи с запрещёнными точками и соседними шагами.

Робот идёт из угла решётки в противоположный и не может отступать назад. Количество маршрутов быстро растёт; простой перебор уже неудобен.

Определения и точные условия

  1. Кратчайший монотонный путь из (0;0) в (m;n) содержит ровно m шагов вправо и n шагов вверх.
  2. Число таких маршрутов C(m+n;m) = (m+n)!/(m!n!), где m,n — неотрицательные целые.
  3. Для прохождения через клетку 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.

Типичные ошибки

  1. Считать кратчайшими маршруты, в которых есть шаги назад: минимальность тогда теряется.
  2. Складывать числа путей до точки и после вместо умножения.
  3. Забывать, что при нескольких запрещённых точках простое вычитание может дважды учесть один путь.

Упражнения: от простого к сложному

  1. Сколько путей из (0;0) в (3;2)?
  2. Сколько путей из (0;0) в (5;3)?
  3. Сколько путей из (0;0) в (4;4) проходят через (2;2)?
  4. Сколько путей из (0;0) в (4;4) обходят точку (2;2)?
  5. Докажите тождество C(n;k)=C(n−1;k)+C(n−1;k−1) разбором последнего шага.

Исследуем закономерность

Посчитайте пути на решётке 3×3 при запрете двух внутренних точек. Когда нужна формула включений–исключений?

Самостоятельные работы и PDF

Пять вариантов по десять заданий; проверка ответов производится на сервере. Обновлённый конспект v112 содержит подробные объяснения, задачи и доказательства. Ученические листы v111 и закрытые учительские решения сохранены.

Подробный конспект PDF (v112) · Листы заданий PDF · Онлайн-проверка

Подведём итог

Выбирайте позиции одинаковых шагов; для обязательной промежуточной точки перемножайте количества маршрутов, для одной запрещённой — вычитайте.

Все уроки класса · Интерактивные лаборатории