Pat will walk from intersection X to intersection Y along a route that : Problem Solving (PS)

bhushangiri

Joined: 15 Jul 2008

Last visit: 18 May 2012

Posts: 69

Own Kudos:

440

[15]

Posts: 69

Kudos: 440

[15]

04 Aug 2008, 06:02

9

Kudos

6

Bookmarks

haidzz

Pat will walk from intersection A to intersection B along a route that is confined to the square grid of four streets and three avenues shown in the map above. How many routes from A to B can Pat take that have the minimum possible length?
A. 6
B. 8
C. 10
D. 14
E. 16

(map is attached)

Attachment:

PS combinatorics.doc

This is a question from the OG-11. Does anyone have a faster/easier solution??

Consider this a as coordinate plane with A as origin and B as (2,3).

The shortest possible way is when you go take either right or up. (lefts and downs make repetitions and thus non shortest paths)

now, to get to (2,3) form (0,0) you need min 5 steps.

so you have to choose all the paths such that you have 2 steps out of 5 along x axis and getting to 3 of y axis.
The number of ways = 5C2 =10

(or alternately all paths that have 3 steps along y and takes you to 2 of x. .. 5C3 = 10)

KASSALMD

Joined: 22 Jul 2008

Last visit: 09 Jan 2009

Posts: 54

Own Kudos:

56

[5]

Posts: 54

Kudos: 56

[5]

04 Aug 2008, 07:25

Kudos

3

Bookmarks

It is a fairly simple problem if one recognizes that there's only one combination of 3 y-coordinates for every pair of x-coordinates. In simpler terms, you can go right in 2 paths, but there's only one unique set of 3 paths going upwards with those 2 paths.
All we have to do is figure out in how many ways we can take 2 paths to the right. For each such path, there will be only 1 combination of 3 paths that will go up to B.
Also note that there are 8 paths going to the right but we cannot do 8C2 because once you take the 1st path going to the right, all the other right-paths above it become redundant.
The number of paths we can take to the right is 1*4 + 1*3 + 1*2 + 1*1 = 10 paths.

bhushangiri

Joined: 15 Jul 2008

Last visit: 18 May 2012

Posts: 69

Own Kudos:

440

[8]

Posts: 69

Kudos: 440

[8]

04 Aug 2008, 07:43

2

Kudos

6

Bookmarks

haidzz

dude you're a genius! kudos to you. I'm really weak in Permutations, combinations and probability. How can I get better at it? Can you suggest a particular book other than GMAT books?

This site is pretty good...
https://www.mansw.nsw.edu.au/members/ref ... no4yen.htm

Thanks to Durgesh79 for pointing me to this page. Awesome summary of all basic concepts.

Also follow his solutions to combinatorial problems.. he comes up with real cool ways to tame these little pups.

TallJTinChina

Joined: 24 May 2010

Last visit: 28 Jun 2011

Posts: 39

Own Kudos:

141

[7]

Given Kudos: 4

Status:Waiting to hear from University of Texas at Austin

Location: Changchun, China

Concentration: MSA - Generalist

Schools:University of Texas at Austin, Michigan State

Q46 V44

GPA: 3.9

Posts: 39

Kudos: 141

[7]

08 Jul 2010, 19:55

4

Kudos

3

Bookmarks

Bringing up an old topic because it is giving me headaches. :shock:

I understand breaking this down into 5 steps (2 Rights, 3 Ups)

So right = R
And Up = U

So we need to see how many permutations include 2 Rights, and 3 Ups

So I made a list

Start to the right
RRUUU
RURUU
RUURU
RUUUR

Start with by moving up
URRUU
URURU
URUUR
UURRU
UURUR
UUURR

Obviously making a list is not the quickest way to solve this problem.

How do I get to it this ----> 5!/2!3! = 10 ????????

It seems to be me are picking 5 out of 5? So we would have 5!/5!0! which equals 1

TallJTinChina

Joined: 24 May 2010

Last visit: 28 Jun 2011

Posts: 39

Own Kudos:

141

Given Kudos: 4

Status:Waiting to hear from University of Texas at Austin

Location: Changchun, China

Concentration: MSA - Generalist

Schools:University of Texas at Austin, Michigan State

Q46 V44

GPA: 3.9

Posts: 39

Kudos: 141

08 Jul 2010, 22:10

Kudos

Bookmarks

Quote:

The formula for arranging n objects where some objects recur is: n!/(r!*s!) in which "r" and "s" are the number of times objects of a certain kind appear.

Thanks for your help, just to make sure I understand if I had MISSISSIPPI

The number of ways to arrange it would be 11! / (4!*4!*2!) = 34,650 ???

Testluv

Kaplan GMAT Instructor

Joined: 21 Jun 2010

Last visit: 10 Dec 2010

Posts: 55

Own Kudos:

470

[3]

Given Kudos: 2

Location: Toronto

Posts: 55

Kudos: 470

[3]

08 Jul 2010, 22:12

3

Kudos

Bookmarks

TallJTinChina

Quote:

The formula for arranging n objects where some objects recur is: n!/(r!*s!) in which "r" and "s" are the number of times objects of a certain kind appear.

Thanks for your help, just to make sure I understand if I had MISSISSIPPI

The number of ways to arrange it would be 11! / (4!*4!*2!) = 34,650 ???

Haha! That's probably the best example one can come up with. Yes, that is indeed correct....thanks for making me count all the "I"s and "S"s!

ezinis

Joined: 27 Oct 2009

Last visit: 04 Feb 2011

Posts: 87

Own Kudos:

423

Given Kudos: 18

Location: Montreal

Concentration: Finance

Schools:Harvard, Yale, HEC

Posts: 87

Kudos: 423

21 Jan 2011, 17:42

Kudos

Bookmarks

bhushangiri

haidzz

Pat will walk from intersection A to intersection B along a route that is confined to the square grid of four streets and three avenues shown in the map above. How many routes from A to B can Pat take that have the minimum possible length?
A. 6
B. 8
C. 10
D. 14
E. 16

(map is attached)

Attachment:

PS combinatorics.doc

This is a question from the OG-11. Does anyone have a faster/easier solution??

Consider this a as coordinate plane with A as origin and B as (2,3).

The shortest possible way is when you go take either right or up. (lefts and downs make repetitions and thus non shortest paths)

now, to get to (2,3) form (0,0) you need min 5 steps.

so you have to choose all the paths such that you have 2 steps out of 5 along x axis and getting to 3 of y axis.
The number of ways = 5C2 =10

(or alternately all paths that have 3 steps along y and takes you to 2 of x. .. 5C3 = 10)

Can you explicate your combinatorial method a bit more. For example, If I add another Avenue, eg, Avenue D, and another street, Street 5, I will have to go 3 steps right and 4 steps up to get to point C.

Therefore, the total number of route will be 7C3 = 35? Am I correct?

ezinis

Joined: 27 Oct 2009

Last visit: 04 Feb 2011

Posts: 87

Own Kudos:

423

Given Kudos: 18

Location: Montreal

Concentration: Finance

Schools:Harvard, Yale, HEC

Posts: 87

Kudos: 423

21 Jan 2011, 18:19

Kudos

Bookmarks

You're the best Bunuel, +1

mymbadreamz

Joined: 15 Apr 2011

Last visit: 10 Mar 2022

Posts: 56

Own Kudos:

109

Given Kudos: 45

Products:

Posts: 56

Kudos: 109

13 Apr 2012, 11:31

Kudos

Bookmarks

I didn't understand this part "In order the length to be minimum Pat should only go UP and RIGHT: namely thrice UP and twice RIGHT.". He could also go twice RIGHT and then thrice UP. I didn't follow how this was chosen.

Bunuel

Math Expert

Joined: 02 Sep 2009

Last visit: 25 Jan 2025

Posts: 99,010

Own Kudos:

696,661

[6]

Given Kudos: 91,919

Products:

Expert reply

Posts: 99,010

Kudos: 696,661

[6]

13 Apr 2012, 11:44

3

Kudos

3

Bookmarks

mymbadreamz

I didn't understand this part "In order the length to be minimum Pat should only go UP and RIGHT: namely thrice UP and twice RIGHT.". He could also go twice RIGHT and then thrice UP. I didn't follow how this was chosen.

Y is 3 moves UP and 2 moves RIGHT from X (Pat). Now, in order to minimize the route from X to Y only those moves should be taken, how else? But Pat can make these moves (3 Ups, 2 RIGHT) in several different ways:
Up, Up, Up, Right, Right;
Up, Up, Right, Up, Right;
Right, Up, Up, Right, Up;
...
Just look at the diagram to check.

Now, how, many combinations of those moves are possible? # of combination of Up, Up, Up, Right, Right or combinations UUUPP is 5!/(3!2!)=10.

Hope it's clear.

sofiak1985mailru

Joined: 21 May 2012

Last visit: 31 Aug 2012

Posts: 11

Own Kudos:

12

Given Kudos: 17

Location: United States

Concentration: Finance, Real Estate

GPA: 3.86

Posts: 11

Kudos: 12

29 Jul 2012, 16:35

Kudos

Bookmarks

Bunuel, great example & explanation! Thank you

EvaJager

Joined: 22 Mar 2011

Last visit: 31 Aug 2016

Posts: 515

Own Kudos:

2,229

[1]

Given Kudos: 43

WE:Science (Education)

Posts: 515

Kudos: 2,229

[1]

30 Jul 2012, 03:24

1

Kudos

Bookmarks

haidzz

Pat will walk from intersection A to intersection B along a route that is confined to the square grid of four streets and three avenues shown in the map above. How many routes from A to B can Pat take that have the minimum possible length?
A. 6
B. 8
C. 10
D. 14
E. 16

(map is attached)

Attachment:

PS combinatorics.doc

This is a question from the OG-11. Does anyone have a faster/easier solution??

Looking at the map, we can see that a route of minimal length is any route that takes only steps up (U) and to the right(R), never to the left or down.
Necessarily, such a route has two Right walks and three Up walks. One have to count all the orderings to have in a sequence of 5 walks 2Rs and 3Us.
So, there are 5C2 possibilities for a minimal route, which is 5*4/2=10.

Answer C

fozzzy

Joined: 29 Nov 2012

Last visit: 17 May 2015

Posts: 575

Own Kudos:

6,397

Given Kudos: 543

Posts: 575

Kudos: 6,397

21 Jan 2013, 02:47

Kudos

Bookmarks

Great explanation Bunuel, thanks a lot.

russ9

Joined: 15 Aug 2013

Last visit: 20 Apr 2015

Posts: 176

Own Kudos:

356

Given Kudos: 23

Posts: 176

Kudos: 356

23 Apr 2014, 19:25

Kudos

Bookmarks

Testluv

Quote:

How do I get to it this ----> 5!/2!3! = 10 ????????

by using the formula for arranging n objects where some objects recur. We know that there are n! ways of arranging n distinct objects. So, for example, the number of words (both sensical and nonsensical) that can be made from the letters in this word:

GMAT

is 4!.

What about the number of words that can be created from this word:

DESERT?

Well, we have 6 objects. If they were all distinct, there would be 6! ways of arranging all the letters, and thus 6! words would be made. HOWEVER, not all of the letters are distinct. In particular, "E" shows up twice. So, there are actually 6!/2! words we can create. What about this word:

DESSERT?

Now, we have 7 objects. But both "S" and "E" show up twice. So, there are 7!/(2!*2!) ways of arranging.

And how about:

DESSERTS?

Now, there are 8!/(3!*2!) ways of arranging.

What about this word:

SSS

Well, there are 3!/3! or 1 way of arranging all the letters.

The formula for arranging n objects where some objects recur is: n!/(r!*s!) in which "r" and "s" are the number of times objects of a certain kind appear.

So, with:

UUURR,

there are 5!/(3!*2!) ways of arranging.

This makes complete sense when we think about just the different permutations available with the various streets and avenues. I couldn't get myself to use this because I wasn't sure if this would totally eliminate the possibility of moving left or down instead of just up and right?

How can we be certain that this wouldn't count the negative distances?

Bunuel

Math Expert

Joined: 02 Sep 2009

Last visit: 25 Jan 2025

Posts: 99,010

Own Kudos:

696,661

[1]

Given Kudos: 91,919

Products:

Expert reply

Posts: 99,010

Kudos: 696,661

[1]

24 Apr 2014, 01:12

Kudos

1

Bookmarks

russ9

Testluv

Quote:

How do I get to it this ----> 5!/2!3! = 10 ????????

by using the formula for arranging n objects where some objects recur. We know that there are n! ways of arranging n distinct objects. So, for example, the number of words (both sensical and nonsensical) that can be made from the letters in this word:

GMAT

is 4!.

What about the number of words that can be created from this word:

DESERT?

Well, we have 6 objects. If they were all distinct, there would be 6! ways of arranging all the letters, and thus 6! words would be made. HOWEVER, not all of the letters are distinct. In particular, "E" shows up twice. So, there are actually 6!/2! words we can create. What about this word:

DESSERT?

Now, we have 7 objects. But both "S" and "E" show up twice. So, there are 7!/(2!*2!) ways of arranging.

And how about:

DESSERTS?

Now, there are 8!/(3!*2!) ways of arranging.

What about this word:

SSS

Well, there are 3!/3! or 1 way of arranging all the letters.

The formula for arranging n objects where some objects recur is: n!/(r!*s!) in which "r" and "s" are the number of times objects of a certain kind appear.

So, with:

UUURR,

there are 5!/(3!*2!) ways of arranging.

This makes complete sense when we think about just the different permutations available with the various streets and avenues. I couldn't get myself to use this because I wasn't sure if this would totally eliminate the possibility of moving left or down instead of just up and right?

How can we be certain that this wouldn't count the negative distances?

How can arrangements of Up's and Right's give Left and Down? The following post shows all the possible routs: pat-will-walk-from-intersection-a-to-intersection-b-along-a-68374.html#p1073473

Hope it helps.

russ9

Joined: 15 Aug 2013

Last visit: 20 Apr 2015

Posts: 176

Own Kudos:

356

Given Kudos: 23

Posts: 176

Kudos: 356

24 Apr 2014, 19:32

Kudos

Bookmarks

Bunuel

russ9

This makes complete sense when we think about just the different permutations available with the various streets and avenues. I couldn't get myself to use this because I wasn't sure if this would totally eliminate the possibility of moving left or down instead of just up and right?

How can we be certain that this wouldn't count the negative distances?

How can arrangements of Up's and Right's give Left and Down? The following post shows all the possible routs: pat-will-walk-from-intersection-a-to-intersection-b-along-a-68374.html#p1073473

Hope it helps.

Ahh - makes sense because we are trying to "minimize" the routed. If that wasn't the case then I guess this formula wouldn't apply.

kzivrev

Joined: 06 Jun 2014

Last visit: 19 Sep 2016

Posts: 34

Own Kudos:

85

[1]

Given Kudos: 105

Posts: 34

Kudos: 85

[1]

16 Apr 2015, 17:43

1

Kudos

Bookmarks

I solved this problem using the Pascal's Triangle, however the permutation solution is a bit faster, of course only if you now how to set up the equation.

Pat will walk from intersection X to intersection Y along a route that

Prep Toolkit

My Rewards

GMAT Problem Solving (PS) Questions

Pat will walk from intersection X to intersection Y along a route that

Prep Toolkit

My Rewards