bhandariavi wrote:
In city A, the streets are aligned in a grid (see attachment), where the east-west roads are called 1st Rd, 2nd Rd, 3rd Rd, etc, increasing in number as one moves northward. The north-south roads are called 1st Ave, 2nd Ave, 3rd Ave, etc, increasing in number as one moves eastward. There is a park that runs from 5th Ave to 7th Ave and from 3rd Rd to 5th Rd, as pictured. If Bill needs to walk from the corner of 2nd Rd and 3rd Ave to the corner of 6th Rd and 8th Ave in the shortest possible time without walking through the park, how many different routes could he take?
1. 45
2. 54
3. 66
4. 98
5. 19
There must be some short cut ways to solve this problem with combination factorial formula.
Can anyone shed light on this?
Good effort bagrettin. thanks and kudos.
After struggling a lot, this is my way of approaching this problem;
I am going to represent Avenues with suffix A and Roads with suffix R
e.g. (3A,2R) is the intersection of 3rd Avenue and 2nd Road.
Total number of shortest ways from (3A,2R) to (8A,6R) will be \(C^{9}_{5} = \frac{9!}{5!4!} = 126\). Think it like a string "EEEEENNNN" 5 blocks east and 4 blocks north and a total of 9 blocks.
Now we need to subtract the routes that are actually not there because of the park;
We just need to consider 2 intersections for that;
(6A,3R), (5A,4R)
Ways to get to (6A,3R) from (3A,2R) = \(C^{4}_{3}=4\)
"From (6A,3R) to (6A,5R) via (6A,4R)" AND "From (6A,3R) to (7A,4R) via (6A,4R)" are two routes that need to be subtracted.
All we need to do now is to find out the number of ways to reach (8A,6R) from (6A,5R) & (7A,4R)
Ways from (6A,5R) to (8A,6R) = \(C^{3}_{2}=3\)
Ways from (7A,4R) to (8A,6R) = \(C^{3}_{1}=3\)
Number of ways to be subtracted = 4*3+4*3 = 12+12=24
Similarly, we can repeat it for intersection (5A,4R)
Ways to reach (5A,4R) from (3A,2R) = \(C^{4}_{2} = 6\)
"From (5A,4R) to (6A,5R) via (6A,4R)" AND "From (5A,4R) to (7A,4R) via (6A,4R)" are two routes that need to be subtracted.
All we need to do now is to find out the number of ways to reach (8A,6R) from (6A,5R) & (7A,4R)
We already found that;
Ways from (6A,5R) to (8A,6R) = \(C^{3}_{2}=3\)
Ways from (7A,4R) to (8A,6R) = \(C^{3}_{1}=3\)
Number of ways to be subtracted= 6*3+6*3 = 18+18=36
Total number of ways to be subtracted = 24+36=60
Number of possible shortest ways = 126-60 = 66.
Ans: "C"