Question

A number of streets in a large city make up a perfect 8-by-8 grid. The street corners occur at integer lattice points (2,y), where I and y are integers between 0 and 8 (including 0 and 8). Any given street corner , y) is connected to (-1,y), (+1, y), (Oy - 1), and (2,4 + 1) by streets (assuming that all of the numbers in question are between 0 and 8). (a) How many different shortest paths can we take from (0,0) to (8,8)? (b) If the streets from (1, 1) to (1,2), (3, 4) to (4,4), and (5,6) to (6,6) are all closed, then how many shortest paths are there from (0,0) to (8,8) (avoiding those streets)?

Answer 1

(0o) coll (0,21 (0,3) (94) (0,5) 10 2 (0,3) (0,4) (0,5) 10,67 (0,7) (0,8) (1,0) (2,0) (3,0) (4,0) (5,0) (6,o) A (8,8) Fig. (Ignore the Imperfections) (a) Obserce that to take shortest path from (0,o) to (8,8) we must not take any toin on left ar & up at any point of time. At each step we must either choose a stop at right or down. But we will have to take total 16 steps then, 8 steps on the reight and 8 on down. At each of the 16 steps we can choose either to go right or to down (if available). Therefore we have to choose 8 steps to right from the total 16 steps towards down). can do this in 16Cg many ways. (The other 8 steps will then automatically be Hence we can do this in 16c. le we are choosing 8 times from total 16 when we will go right. Therese different shortest paths = 180g = 12870

This part is more combinatorial we will have to abood act paths. such that (1, 1) to (1,22 Observe that there are the ways to Freach CP.) once Bacon szobzs (1,12 (Some argument as in @). But ant of them half ways Can't be taken as the right side path is blocked. So we will have to aboid the many faths Similarly once reached (34) we will have to avoid aco many ways reached (5.5) we caill have to paths we have done many pathe But while aloiding the path Some ouer counting such as the path arch we have abiad excluded alter seachine (1, 1) as we can't go on (1.2) from there if it leads to (34) then we are excluding that path toile do to balance that we will have 6 d Be namber in the path we of have excluded pat paths B .2) 3.4). To ne moze of such Maths 46. Similarly fan baths (4.9) to (5,5) extra paths = 30 From (1,2) to (5,6) avoiding the path 03.4) to (44) is 8 - So, Total paths to be avoided are es 1907904.50 -46-34-8

Therefore number of available paths are 16 - Ź (14 ext9 eq 4 5 6 + 462) the +3 et den = 16 eg - 3574 +79 = 11162 2

[Ask in the comments if you have difficulty in any step. Also ask in the comments if there is any minor error while calculating. I am always happy to answer. Thank you]