Question

Город имеет форму прямоугольника, улицы идут строго с юга на север или с запада на восток. Улиц первого направления (n+1),второго – (m+1). Сколькими различными путями можно пройти из юго-восточного угла города в северо-западный так, чтобы путь был кратчайшим?

Answer 1

Ответ:

До бесконечности можно перебирать . Ведь улиц неограниченное количество

Answer 2

Для нахождения количества различных кратчайших путей из юго-восточного угла города в северо-западный угол, можно использовать комбинаторику и знание о комбинаторных числах. Для такой задачи можно воспользоваться биномиальным коэффициентом.

Пусть у нас есть город в виде прямоугольника, и у нас есть n+1 улица, идущая с юга на север (вертикальные улицы), и m+1 улица, идущая с запада на восток (горизонтальные улицы).

Для того чтобы попасть из юго-восточного угла в северо-западный угол, нам нужно сделать n шагов на север и m шагов на запад. Порядок, в котором мы делаем эти шаги, не имеет значения, поэтому это задача на количество сочетаний. Мы можем выбрать n моментов для движения на север из n+m моментов (то есть n+m C n).

Таким образом, количество различных кратчайших путей из юго-восточного угла в северо-западный угол города равно n+m C n, что можно выразить как биномиальный коэффициент.