A grid walk

How many ways are there to get from point P to point Q in the grid road below, given that the roads to take must be the shortest possible?


The answer is 200.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Sharky Kesa
Jan 21, 2017

Let P P be point ( 0 , 0 ) (0, 0) and Q Q be point ( 5 , 5 ) (5,5) . Note that any path from P P to Q Q must pass through either ( 2 , 3 ) (2,3) or ( 3 , 2 ) (3,2) . There are ( 5 2 ) = 10 \dbinom{5}{2} = 10 ways of getting from ( 0 , 0 ) (0,0) to one of those points, and ( 5 2 ) = 10 \dbinom{5}{2} = 10 ways of getting from one of those points to ( 5 , 5 ) (5,5) . Thus, there are a total 2 × 10 × 10 = 200 2 \times 10 \times 10 = 200 ways of getting to Q Q from P P .

Anirudh Sreekumar
Jan 29, 2017

Let P P be point ( 0 , 0 ) (0,0) and Q Q be point ( 5 , 5 ) (5,5)

The total number of ways from P P to Q Q on a complete grid is given by ( 10 5 ) = 252 \dbinom{10}{5}=252

However here we have portions of the grid removed (denoted by red lines).Consider the upper left removed portion,any path from P P to Q Q involving a red line would pass through exactly one of the black points( ( 1 , 4 ) (1,4) and ( 0 , 5 ) (0,5) ) in the region.

no of paths through ( 1 , 4 ) (1,4) is given by ( 5 4 ) × ( 5 1 ) = 25 \dbinom{5}{4}\times\dbinom{5}{1}=25

no of paths through ( 0 , 5 ) (0,5) is given by ( 5 0 ) × ( 5 5 ) = 1 \dbinom{5}{0}\times\dbinom{5}{5}=1

thus total number of paths involving red lines in upper left region is ( 25 + 1 ) = 26 (25+1)=26

similarly we have 26 26 paths involving red lines in lower right region,

Thus total number of valid paths from P P to Q Q is given by 252 ( 26 + 26 ) = 200 252-(26+26)=\boxed{200}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...