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?
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.
Let P be point ( 0 , 0 ) and Q be point ( 5 , 5 )
The total number of ways from P to Q on a complete grid is given by ( 5 1 0 ) = 2 5 2
However here we have portions of the grid removed (denoted by red lines).Consider the upper left removed portion,any path from P to Q involving a red line would pass through exactly one of the black points( ( 1 , 4 ) and ( 0 , 5 ) ) in the region.
no of paths through ( 1 , 4 ) is given by ( 4 5 ) × ( 1 5 ) = 2 5
no of paths through ( 0 , 5 ) is given by ( 0 5 ) × ( 5 5 ) = 1
thus total number of paths involving red lines in upper left region is ( 2 5 + 1 ) = 2 6
similarly we have 2 6 paths involving red lines in lower right region,
Thus total number of valid paths from P to Q is given by 2 5 2 − ( 2 6 + 2 6 ) = 2 0 0
Problem Loading...
Note Loading...
Set Loading...
Let P be point ( 0 , 0 ) and Q be point ( 5 , 5 ) . Note that any path from P to Q must pass through either ( 2 , 3 ) or ( 3 , 2 ) . There are ( 2 5 ) = 1 0 ways of getting from ( 0 , 0 ) to one of those points, and ( 2 5 ) = 1 0 ways of getting from one of those points to ( 5 , 5 ) . Thus, there are a total 2 × 1 0 × 1 0 = 2 0 0 ways of getting to Q from P .