Сколько маршрутов по сетке: почему не 4 · 3, а 35

Эта задача хорошо показывает разницу между угаданной формулой, перебором наугад и рассуждением по шагам. Приятная новость: задача решается в пятом классе, без готовых формул. Нужен один вопрос, заданный вовремя.

Задача

Сетка — как кварталы на карте города: 4 шага в ширину, 3 шага в высоту. Из угла $A$ нужно дойти до угла $B$, двигаясь по линиям сетки только вправо и вверх. Сколько существует разных маршрутов?

Пара маршрутов рисуется сразу, а дальше начинаются сомнения: этот уже был? все ли нашли? Хочется быстрого способа — и он тут же находится.

Догадка

Вправо — 4 шага, вверх — 3. Значит, способов 4 · 3 = 12: когда выбираем и то и другое, всегда же перемножают.

Умножение появляется здесь не случайно. Правило умножения — настоящий инструмент: 4 вкуса мороженого и 3 сиропа дают $4 \cdot 3 = 12$ сочетаний. Ребёнок увидел два числа и применил лучшее из того, что знает, — так работает интуиция. На занятии такую догадку мы не зачёркиваем, а записываем и проверяем — прямо сейчас.

Рассуждение

Проверим на маленькой сетке. Возьмём сетку $1 \times 1$: один шаг вправо, один вверх. Догадка обещает $1 \cdot 1 = 1$ маршрут. А их два: «вправо, потом вверх» и «вверх, потом вправо». На сетке $2 \times 2$ аккуратный перебор находит 6 маршрутов — умножение обещает 4. Догадка не выдержала самой простой проверки, и узнать это за минуту полезнее, чем после контрольной.

Почему умножение не сработало? Потому что мы выбираем не «сколько вправо и сколько вверх» — это задано условием. Все маршруты состоят из одних и тех же 7 ходов, различается только их порядок. А порядок парой чисел не описывается.

Смотрим на один узел. Вместо всех маршрутов сразу — вопрос про один узел сетки: откуда в него вообще можно прийти? Только из соседа слева (шагом вправо) или из соседа снизу (шагом вверх) — других входов нет. Значит, все маршруты до узла делятся на две стопки: пришедшие слева и пришедшие снизу. Число маршрутов до узла равно сумме этих двух чисел. Это правило сложения.

Запускаем его: вдоль нижней стороны сетки в каждый узел ведёт один маршрут (идти можно только вправо), вдоль левой — тоже один. Дальше узлы заполняются сами:

Доказательство

Почему сложению можно верить до конца? У каждого маршрута есть последний ход — ровно один: либо вправо, либо вверх. Маршруты с последним ходом «вправо» приходят из соседа слева, с последним ходом «вверх» — из соседа снизу. Две группы не пересекаются: последний ход один — либо вправо, либо вверх и вместе исчерпывают всё (третьего направления не дано). Ни один маршрут не потерян, ни один не посчитан дважды.

Есть и независимая проверка для тех, кто хочет пересчитать иначе. Маршрут — это цепочка из 7 ходов, где ровно 3 хода — «вверх»: например, ПВППВПВ. Сосчитаем, сколькими способами можно расставить 3 буквы «В» на 7 местах: первое место для «В» выбирается 7 способами, второе — 6, третье — 5; но каждая тройка мест при этом названа 3 · 2 · 1 = 6 раз в разном порядке, поэтому делим:

$$\frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35.$$

Два разных способа счёта дали одно число — 35.

Ответ: 35 маршрутов.

Догадка «перемножить» проверку не прошла — и принесла больше пользы, чем случайно угаданный ответ: она заставила спросить, что именно мы выбираем.

Что и требовалось — понять

Попробуйте сами

Сетка $3 \times 3$: три шага вправо, три вверх. Единицы вдоль нижней и левой сторон уже расставлены — заполните остальные узлы правилом сложения и найдите число маршрутов из $A$ в $B$. А потом проверьте себя вторым способом: маршрут — слово из 6 ходов, из которых ровно 3 — «вверх».

Показать ответ

Узлы заполняются рядами: над единицами встают $1,\ 2,\ 3,\ 4$, выше — $1,\ 3,\ 6,\ 10$, и наконец $1,\ 4,\ 10,\ 20$. В углу $B$ — 20 маршрутов.

Проверка вторым способом: $\frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$. Оба способа согласны: $20$.