Question Number 17612 by Tinkutara last updated on 08/Jul/17
$$\mathrm{The}\:\mathrm{accompanying}\:\mathrm{diagram}\:\mathrm{is}\:\mathrm{a}\:\mathrm{road}- \\ $$$$\mathrm{plan}\:\mathrm{of}\:\mathrm{a}\:\mathrm{city}.\:\mathrm{All}\:\mathrm{the}\:\mathrm{roads}\:\mathrm{go}\:\mathrm{east}- \\ $$$$\mathrm{west}\:\mathrm{or}\:\mathrm{north}-\mathrm{south},\:\mathrm{with}\:\mathrm{the} \\ $$$$\mathrm{exception}\:\mathrm{of}\:\mathrm{one}\:\mathrm{shown}.\:\mathrm{Due}\:\mathrm{to}\:\mathrm{repairs} \\ $$$$\mathrm{one}\:\mathrm{road}\:\mathrm{is}\:\mathrm{impassable}\:\mathrm{at}\:\mathrm{the}\:\mathrm{point}\:\mathrm{X}, \\ $$$$\mathrm{Of}\:\mathrm{all}\:\mathrm{the}\:\mathrm{possible}\:\mathrm{routes}\:\mathrm{from}\:\mathrm{P}\:\mathrm{to}\:\mathrm{Q}, \\ $$$$\mathrm{there}\:\mathrm{are}\:\mathrm{several}\:\mathrm{shortest}\:\mathrm{routes}.\:\mathrm{How} \\ $$$$\mathrm{many}\:\mathrm{such}\:\mathrm{shortest}\:\mathrm{routes}\:\mathrm{are}\:\mathrm{there}? \\ $$
Commented by Tinkutara last updated on 08/Jul/17
Commented by alex041103 last updated on 08/Jul/17
$$\mathrm{14} \\ $$
Answered by alex041103 last updated on 09/Jul/17
Commented by Tinkutara last updated on 09/Jul/17
$$\mathrm{Thanks}\:\mathrm{Sir}! \\ $$
Commented by alex041103 last updated on 09/Jul/17
$${Because}\:{we}\:{are}\:{aiming}\:{for}\:{the}\:{shortest} \\ $$$${paths}\:{we}\:{will}\:{allow}\:{ourselfs}\:{to}\:{go}\:{only} \\ $$$${up}\:{or}\:{right}.\:{Also}\:{we}\:{have}\:{to}\:{go}\:{through}\:{the}\: \\ $$$${diagonal}\:{road}\left({because}\:{the}\:{lenght}\:{of}\:{one}\:{side}\:{in}\right. \\ $$$${a}\:{triangle}\:{is}\:{allways}\:{smaller}\:{than} \\ $$$$\left.{the}\:{sum}\:{of}\:{lenghts}\:{other}\:{two}\:{sides}\right) \\ $$$${Because}\:{of}\:{the}\:{repairs}\:{and}\:{the}\:{restrictions}\:{we} \\ $$$${made}\:{we}\:{cannot}\:{go}\:{through}\:{the}\:{roads} \\ $$$${in}\:{greenish}\:{color}. \\ $$$${As}\:{seen}\:{in}\:{the}\:{lower}−{right}\:{corner}\:{of}\:{the}\:{figure} \\ $$$${the}\:{number}\:{of}\:{ways}\:{for}\:{reaching}\:{a}\:{point} \\ $$$${is}\:{equal}\:{to}\:{the}\:{sum}\:{of}\:{the}\:{ways}\:{for}\:{reaching} \\ $$$${the}\:{points}\:{on}\:{left}\:{and}\:{down}\left({i}.{e}.\:{the}\:{posable}\right. \\ $$$$\left.{last}\:{points}\left({crossroad}\right)\right)\:{which}\:{makes}\:{sense}. \\ $$$${Also}\:{the}\:{number}\:{of}\:{ways}\:{for}\:{reaching} \\ $$$${to}\:{the}\:{point}\:{right}\:{or}\:{up}\:{to}\:{some}\:{point}\:{N} \\ $$$${is}\:{the}\:{same}\:{as}\:{then}\:{umber}\:{of}\:{ways} \\ $$$${for}\:{reaching}\:{point}\:{N}. \\ $$$${rom}\:{here}\:{as}\:{shown}\:{in}\:{the}\:{photo}\:{we}\:{just} \\ $$$${do}\:{the}\:{suming}\:{and}\:{get}\:{for}\:{the}\:{shortest}\:{paths} \\ $$$${the}\:{number}\:\mathrm{14}. \\ $$