Menu Close

The-accompanying-diagram-is-a-road-plan-of-a-city-All-the-roads-go-east-west-or-north-south-with-the-exception-of-one-shown-Due-to-repairs-one-road-is-impassable-at-the-point-X-Of-all-the-possib




Question Number 17612 by Tinkutara last updated on 08/Jul/17
The accompanying diagram is a road-  plan of a city. All the roads go east-  west or north-south, with the  exception of one shown. Due to repairs  one road is impassable at the point X,  Of all the possible routes from P to Q,  there are several shortest routes. How  many such shortest routes are there?
$$\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
14
$$\mathrm{14} \\ $$
Answered by alex041103 last updated on 09/Jul/17
Commented by Tinkutara last updated on 09/Jul/17
Thanks Sir!
$$\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(because the lenght of one side in  a triangle is allways smaller than  the sum of lenghts other two sides)  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(i.e. the posable  last points(crossroad)) 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 14.
$${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}. \\ $$

Leave a Reply

Your email address will not be published. Required fields are marked *