Задача 3. Пути Али-бабы

Что такое путь и почему пути трудно пересчитать

В лабиринте $5$ рядов по $7$ комнат. Али-баба входит в левую нижнюю комнату, а в пещеру попадает из правой верхней. Двигаться можно только направо или вверх, поэтому назад он не возвращается. Чтобы дойти от левого столбца до правого, нужно $6$ раз пройти по коридору направо (столбцов $7$), а чтобы подняться с нижнего ряда на верхний — $4$ раза вверх (рядов $5$). Пути отличаются только порядком этих шагов: например, «$6$ раз направо, потом $4$ раза вверх» или «вверх, направо, вверх, направо, …».

Таких путей много. Если выписывать их подряд, легко пропустить какой-нибудь путь или записать один и тот же дважды, а потом ещё проверять каждый, не проходит ли он через $A$ или $B$. Поэтому поступим иначе: для каждой комнаты узнаем, сколько путей ведёт в неё от входа. Начнём с комнат у самого входа — там пути легко пересчитать прямо по схеме — и будем продвигаться дальше.

Число путей в комнату — сумма двух соседей

В каждую комнату нижнего ряда ведёт ровно один путь: чтобы остаться внизу, можно идти только направо. Точно так же в каждую комнату левого столбца ведёт один путь — только вверх. Закрытых комнат на этих путях нет: $A$ и $B$ стоят не в нижнем ряду и не в левом столбце.

Теперь комната на одну правее и на одну выше входа. В неё ведут два пути: «направо, вверх» и «вверх, направо». Первый входит в неё из комнаты слева, второй — из комнаты снизу. Это наблюдение и подсказывает общее правило.

Возьмём любую комнату. Последний шаг в неё сделан либо из соседней комнаты слева, либо из соседней комнаты снизу — третьего не бывает. Пути, пришедшие слева, — это пути в комнату слева, продолженные одним шагом направо; их ровно столько, сколько путей ведёт в комнату слева. Пути, пришедшие снизу, — это пути в комнату снизу плюс шаг вверх. Ни один путь не попадёт сразу в обе группы: последний шаг у него один. И ни один путь не потеряется. Значит,

число путей в комнату равно сумме двух чисел: числа путей в комнату слева и числа путей в комнату снизу.

Например, во втором ряду снизу получаем $1$, $1+1=2$, $2+1=3$, а в третьем ряду — $1$, $1+2=3$ и $3+3=6$. В комнату с числом $6$ ведут $3$ пути слева и $3$ пути снизу (см. рисунок).

Закрытые комнаты: пишем 0

Через комнаты $A$ и $B$ проходить нельзя, поэтому ни один разрешённый путь в них не входит — в этих комнатах пишем $0$. Дальше правило работает само: закрытый сосед добавляет к сумме $0$, то есть пути через него просто не считаются.

Продолжим второй ряд снизу: после $1$, $2$, $3$ идут $3+1=4$ и $4+1=5$, затем комната $B$ — $0$. В последнюю комнату ряда можно войти слева, из $B$, или снизу. Слева путей нет, снизу ведёт $1$ путь, всего $0+1=1$. Проверим по схеме: действительно, туда ведёт единственный путь — по нижнему ряду до конца и шаг вверх.

Заполняем лабиринт ряд за рядом

Каждое число — сумма числа слева и числа снизу. Поэтому заполняем ряды снизу вверх, а каждый ряд — слева направо: тогда оба нужных числа к этому моменту уже известны. В записи ниже первое слагаемое — число слева, второе — число снизу.

• Третий ряд снизу: $1$, $1+2=3$, $3+3=6$, $6+4=10$, $10+5=15$; над $B$ — $15+0=15$; последняя комната — $15+1=16$.
• Четвёртый ряд, в нём комната $A$: $1$, $1+3=4$, $4+6=10$, в $A$ — $0$; справа от $A$ — $0+15=15$, дальше $15+15=30$ и $30+16=46$.
• Верхний ряд: $1$, $1+4=5$, $5+10=15$, над $A$ — $15+0=15$, дальше $15+15=30$, $30+30=60$ и $60+46=106$.

В правую верхнюю комнату ведут $106$ путей, а из неё каждый путь продолжается в пещеру. Значит, в пещеру ведут $106$ различных путей.