How many routes from X to Y

[kobel51]

Pat will walk from intersection X to intersection Y along a route that is confined to the square grid of four streets and three avenues shown in the preceding map. How many routes form X to Y can Pat take that have the minimum possible length?

A) 6
B) 8
C) 10
D) 14
E) 16

[Patrick_GMATFix]

To go from X to Y, we need to go right twice (2 R's) and up three times (3 U's). Think of this question as how many ways you can order RRUUU. The answer is C. I go through the question in detail in the full solution below (taken from the GMATFix App).



-Patrick

[GMATGuruNY]

Pat will walk from intersection X to intersection Y along a route that is confined to the square grid of four streets and three avenues shown in the preceding map. How many routes form X to Y can Pat take that have the minimum possible length?

A) 6
B) 8
C) 10
D) 14
E) 16

Let E = traveling one block eastward and N = traveling one block northward.
To travel from X to Y by a route of minimum length, Pat must travel exactly 2 blocks eastward and exactly 3 blocks northward:
EENNN.
Any arrangement of the letters EENNN will yield a viable route.

The number of ways to arrange 5 DISTINCT elements = 5!.
But the elements above are not distinct: there are 2 identical E's and 3 identical N's.
When an arrangement includes IDENTICAL elements, we must DIVIDE by the number of ways to arrange the identical elements.
The reason is that the arrangement doesn't change when the identical elements swap positions, REDUCING the number of unique arrangements:

To illustrate:
The number of ways to arrange the letters in the word SPEED = 5!/2! = 60.
We divide by 2! to account for the 2 E's.
The number of ways to arrange the letters in the word RADAR = 5!/(2!*2!) = 30.
We divide by 2! to account for the 2 A's and by another 2! to account for the 2 R's.
The number of ways to arrange the letters in the word MISSISSIPPI = 11!/(4!*4!*2!).
We divide by 4! to account for the 4 S's, by another 4! to account for the 4 I's, and by 2! to account for the 2 P's.

In the problem at hand:
The number of ways to arrange EENNN = 5!/(2!*3!) = 10.

The correct answer is C.

Check here for a similar -- but trickier -- problem:

https://www.beatthegmat.com/different-routes-t93698.html

[[email protected]]

Hi kobel51,

There are a couple of ways that you can approach this question....

Since the answers are relatively small, there are at least 6 ways to get from X to Y, but no more than 16 ways to get from X to Y. In a pinch, you could draw pictures and physically find all of the possibilities.

If you're more interested in a "math" approach, you'll see that to get from X to Y you'll need to go 3 blocks "up" and 2 blocks "over" no matter how you get from X to Y.

Since you have to make 5 "moves" and 3 of them have to be "up", you have a combination formula situation....In other words...

5c3

5!/[3!2!] = 10

You COULD also say that to make 5 "moves" and 2 of them have to be "over", you could also use the combination formula in this way...

5c2

5!/[2!3!] = 10

It's the same answer because 5c3 is the same as 5c2.

Final Answer: C

GMAT assassins aren't born, they're made,
Rich

[Scott@TargetTestPrep]

Pat will walk from intersection X to intersection Y along a route that is confined to the square grid of four streets and three avenues shown in the preceding map. How many routes form X to Y can Pat take that have the minimum possible length?

A) 6
B) 8
C) 10
D) 14
E) 16

Let V denote a step in the vertical direction and H denote a step in the horizontal direction. For instance, V-V-V-H-H denotes the path of walking along Avenue A until the intersection of 4th street and walking along 4th street until the point Y. Similarly, V-H-V-H-V denotes the path of walking along Avenue A, then walking along 2st street, then walking along Avenue B, then walking along 3rd street and, finally, walking along Avenue C to reach point Y.

We notice that a shortest path between point X and Y must include three V's and two H's. Further, any arrangement of three V's and two H's (i.e., any arrangement of the letters V-V-V-H-H) gives us a shortest path between X and Y. Using the permutations with indistinguishable objects formula, we see that there are 5! / (3!*2!) = (5 x 4)/2 = 10 such arrangements. Thus, there are 10 shortest paths between points X and Y.

Answer: C