Подсчёт маршрутов в прямоугольной сетке без возвратов: задания от простого к сложному, 9 класс

Диагностическая карточка, 9 класс. Под «маршрутом без возвратов» здесь понимается путь по линиям прямоугольной сетки, в котором разрешены только шаг вправо и шаг вверх. Из левого нижнего узла надо попасть в правый верхний. Если разрешить другие движения, ответ изменится, поэтому ограничение важно прочитать до начала счёта.

Проверь начальный навык

Для перехода на 3 узла вправо и 2 вверх нужен маршрут ровно из пяти шагов. Какую информацию достаточно записать, чтобы определить весь маршрут: а) только общее число шагов; б) позиции двух шагов «вверх» среди пяти; в) только первую стрелку? Верен вариант б: оставшиеся позиции автоматически будут заняты шагами вправо.

Если путь состоит из a шагов вправо и b вверх, число разных маршрутов равно C(a+b, a) = (a+b)!/(a!·b!). Например, для четырёх шагов вправо и одного вверх нужно выбрать позицию единственного подъёма среди пяти: 5 маршрутов. Сами маршруты не должны выходить за границы прямоугольника.

Тренировка: от прямых подсчётов к запретам

Для задач 1–8 указан размер прямоугольника в шагах от старта до финиша. На чертеже можно отмечать путь буквами П (вправо) и В (вверх). Запишите количество путей; порядок ходов важен, но число ходов каждого типа фиксировано.

1. От старта до финиша нужно сделать 2 шага вправо и 1 вверх. Сколько существует маршрутов?
2. От старта до финиша нужно сделать 3 шага вправо и 2 вверх. Сколько существует маршрутов?
3. От старта до финиша нужно сделать 4 шага вправо и 2 вверх. Сколько существует маршрутов?
4. От старта до финиша нужно сделать 2 шага вправо и 3 вверх. Сколько существует маршрутов?
5. От старта до финиша нужно сделать 5 шагов вправо и 1 вверх. Сколько существует маршрутов?
6. От старта до финиша нужно сделать 3 шага вправо и 3 вверх. Сколько существует маршрутов?
7. От старта до финиша нужно сделать 4 шага вправо и 3 вверх. Сколько существует маршрутов?
8. От старта до финиша нужно сделать 5 шагов вправо и 2 вверх. Сколько существует маршрутов?

Задачи с условием прохождения узла

Обозначим начало координатами (0; 0). Запись (x; y) показывает, на сколько шагов вправо и вверх продвинулся путешественник. При прохождении обязательного узла число вариантов для двух участков перемножается. Для запретного узла из общего числа вычитаем пути, проходящие через него.

1. В сетке 4 × 4 пройдите обязательно через (2; 1). Сколько монотонных маршрутов до (4; 4)?
2. В сетке 4 × 3 путь не должен проходить через (1; 1). Сколько допустимых маршрутов?
3. Для 6 шагов вправо и 2 вверх посчитайте маршруты, начинающиеся с подъёма. Сравните с количеством маршрутов, начинающихся с шага вправо.
4. В сетке 3 × 3 нельзя заходить в узел (1; 2). Сколько маршрутов остаётся?

Таблица самопроверки

При проверке не путайте размер сетки в клетках с числом узлов: путь с тремя шагами вправо проходит через четыре вертикальные линии. Условие «не заходить в узел» запрещает и путь, который только касается этого узла.

Три ошибки, из-за которых результат неверен

Ошибка 1. Считать только количество шагов и отвечать «пять маршрутов» при любых пяти шагах. Исправление: для 3 вправо и 2 вверх существует C(5,2)=10 разных порядков.

Ошибка 2. При обязательном узле складывать количества маршрутов до него и после. Их нужно перемножать: каждый первый отрезок сочетается с каждым вторым.

Ошибка 3. Исключать запрещённый узел из числа шагов. Шаги до финиша не меняются; следует вычесть все полные пути, проходящие через запрещённый узел. Итог: определите набор разрешённых направлений, подсчитайте сочетания позиций, затем учтите ограничения.