BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Permutation & Combntn

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Newbie | Next Rank: 10 Posts
Posts: 6
Joined: Wed Jul 15, 2009 4:02 pm

Permutation & Combntn

by Abhi81 » Mon Aug 24, 2009 9:16 pm
Can someone please explain how to solve the below 2 problems? Thanks.

1. In how many ways can Ann, Bea, Cam, Don, Ella and Fey be seated if Ann and Bea cannot be seated next to each other?

(a) 240
(b) 360
(c) 480
(d) 600
(e) 720

Answer given is [spoiler](c)[/spoiler]

2. How many positive integers less than 10,000 are there in which sum of digits equals 5?

(a) 31
(b) 51
(c) 56
(d) 62
(e) 93

Answer given is [spoiler](c)[/spoiler]
Top
Source: — Problem Solving |
Legendary Member
Posts: 752
Joined: Sun May 17, 2009 11:04 pm
Location: Tokyo
Thanked: 81 times
GMAT Score:680

by tohellandback » Mon Aug 24, 2009 10:06 pm
your 1st question is not clear. They can be seated in a row or they can be seated around a circular table. Answer differs in both cases.

Answer to your 2nd question
number is of the form ABCD
where A,B,C,D>=0 and A+B+C+D=5
answer is 8C3= 56 (if you don't understand why,
go here https://www.beatthegmat.com/combination-t41362.html)
C
The powers of two are bloody impolite!!
Top
Senior | Next Rank: 100 Posts
Posts: 73
Joined: Tue Aug 11, 2009 2:30 am
Thanked: 2 times
GMAT Score:720

by shanrizvi » Tue Aug 25, 2009 2:20 am
Explanation by Ian Stewart

There are quite a few good ways to do this kind of problem. One way is to imagine nine donuts:

O O O O O O O O O

Now, say we put two partitions ('|') among our donuts:

O O | O O O | O O O O

We've just worked out a way to add three positive integers to get a sum of 9 (just count the donuts in each zone): 2 + 3 + 4 = 9.

For each different partition we can make, we'll get a different set of values for x, y and z that add to 9. There are 8 gaps between pairs of donuts where we could put a partition, so there are 8C2 = 8*7/2 = 28 different ways to choose positive integers for x, y and z so that x+y+z = 9.
Using the above explanation, shouldn't it be 10C3? As the equation will be x+y+z=9, 3 +'s mean 3 dividers. It was 8 in the example quoted because the numbers had to be positive! In this example, however, the numbers can be zero so there are two more places for the divider. Or at least that is what makes :S
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2623
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Tue Aug 25, 2009 8:19 am
shanrizvi wrote: Using the above explanation, shouldn't it be 10C3? As the equation will be x+y+z=9, 3 +'s mean 3 dividers. It was 8 in the example quoted because the numbers had to be positive! In this example, however, the numbers can be zero so there are two more places for the divider. Or at least that is what makes :S
There are quite a few ways to do the problem How many positive integers less than 10,000 are there in which sum of digits equals 5? , but if you want to do it using partitions, you can do as follows: we need to find four digits which add to 5. Draw five donuts:

O O O O O

We need to insert three partitions; for example, if we have partitions as follows:

O | | O O | O

we have the number 1021, and if we have partitions as follows:

| | | O O O O O

we have the number 0005, or 5.

For the first partition, there are 6 possible locations. For the second, there will be 7 possible locations (since we must allow for a digit to equal zero, we can place the second partition immediately to the left or right of the first), and for the last there will be 8 possible locations. We've placed a first, second and third partition, but the order of the 3 partitions doesn't matter, so we need to divide by 3!. That gives us 8*7*6/3! = 56 different ways to get four digits to sum to 5.

Note that we are allowing the first digit(s) of our number to be zero, but that's fine - we need to count one-digit, two-digit and three-digit numbers as well, and we'll be counting those by allowing zeros at the beginning of our number.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com
Top
Newbie | Next Rank: 10 Posts
Posts: 6
Joined: Tue Jul 14, 2009 7:28 am
Location: India

by the_hustler » Tue Aug 25, 2009 10:34 am
Hello Ian

great way to approach the problem.

but can you clarify how there are 6 possible locations for the 1st partition and for the second, there will be 7 possible locations.

In short. can you elaborate in layman terms ? sorry for the trouble
Top
Master | Next Rank: 500 Posts
Posts: 159
Joined: Thu Aug 27, 2009 10:30 am
Thanked: 19 times

by bharathh » Thu Aug 27, 2009 12:41 pm
What is the explanation for the first problem assuming they were to sit at circular table.

What would it be if they were to sit at a non-circular table?

Btw Ian, your method to solve the second flavor of problems is fantastic!
Top
Master | Next Rank: 500 Posts
Posts: 182
Joined: Sun Aug 02, 2009 7:19 pm
Thanked: 18 times
GMAT Score:680

by sanjana » Sat Aug 29, 2009 9:53 am
Answer to Q1.

We are given that A,B,C,D,E,F have to be seated in a row and the restriction is that A and B cannot sit together.
Break the problem into 2 steps,

1)Find the number of ways we can seat the 6 people without any restriction
A B C D E F
This would be 6! = 720 ways.

2)Consider the restriction given.
We will find the number of ways to arrange them considering A and B are always together
Picture the arrangement treating A and B as one unit
AB C D E F
Number of ways the above arrangement is possible is
5!=120
Now AB could be BA as well,therefore total possibilities is 120*2=240

2)Therefore the total number of ways to seat A,B,C,D,E,F, without A and B sitting together is
720-240=480
Top
User avatar
GMAT Instructor
Posts: 3225
Joined: Tue Jan 08, 2008 2:40 pm
Location: Toronto
Thanked: 1710 times
Followed by:614 members
GMAT Score:800

by Stuart@KaplanGMAT » Sat Aug 29, 2009 10:15 am
shanrizvi wrote:
Using the above explanation, shouldn't it be 10C3? As the equation will be x+y+z=9, 3 +'s mean 3 dividers. It was 8 in the example quoted because the numbers had to be positive! In this example, however, the numbers can be zero so there are two more places for the divider. Or at least that is what makes :S
Here's how I applied Ian's donut solution (which is brilliant!) to this problem - a slightly different way of thinking about it:

We can use the same trick, but it's a bit more complicated since we can also use 0 in this question (and in the previous question we knew that x, y and z were all positive).

Here, we have 4 digits (positive integer less than 10000 means that 9999 is the biggest and we can pretend that "5" is "0005") that must sum to 5.

Since we have 4 digits, we'll have 3 partitions. We're summing to 5, so we have 5 "donuts".

O O O O O

Since we can use 0, we can have multiple partitions in the same spot. For example, we could have:

|||OOOOO (which translates to 0005)

we could have:

||O|OOOO (which translates to 0014, or 14).

So, we view this as a permutation question: we have 8 total objects, 3 of which are identical to each other (the partitions) and 5 of which are identical to each other (the donuts). Using the permutation formula for which some objects are identical:

Total permutations = n!/r!s!

Total permutations = 8!/3!5! = 8*7*6/3*2*1 = 8*7 = 56... choose (C).

* * *

The bolded statement above is the big reason why this question demands a different approach.
Image

Stuart Kovinsky | Kaplan GMAT Faculty | Toronto

Kaplan Exclusive: The Official Test Day Experience | Ready to Take a Free Practice Test? | Kaplan/Beat the GMAT Member Discount
BTG100 for $100 off a full course
Top
Legendary Member
Posts: 869
Joined: Wed Aug 26, 2009 3:49 pm
Location: California
Thanked: 13 times
Followed by:3 members

by heshamelaziry » Sat Aug 29, 2009 2:09 pm
sanjana wrote:Answer to Q1.

We are given that A,B,C,D,E,F have to be seated in a row and the restriction is that A and B cannot sit together.
Break the problem into 2 steps,

1)Find the number of ways we can seat the 6 people without any restriction
A B C D E F
This would be 6! = 720 ways.

2)Consider the restriction given.
We will find the number of ways to arrange them considering A and B are always together
Picture the arrangement treating A and B as one unit
AB C D E F
Number of ways the above arrangement is possible is
5!=120
Now AB could be BA as well,therefore total possibilities is 120*2=240

2)Therefore the total number of ways to seat A,B,C,D,E,F, without A and B sitting together is
720-240=480
How about if the question asked A and B always next to each other. What the solution would be ?
Top
Legendary Member
Posts: 869
Joined: Wed Aug 26, 2009 3:49 pm
Location: California
Thanked: 13 times
Followed by:3 members

by heshamelaziry » Sat Aug 29, 2009 2:10 pm
How about if the first question asked A and B always next to each other. What the solution would be ?
Top
Legendary Member
Posts: 869
Joined: Wed Aug 26, 2009 3:49 pm
Location: California
Thanked: 13 times
Followed by:3 members

by heshamelaziry » Sat Aug 29, 2009 2:42 pm
sanjana wrote:Answer to Q1.

We are given that A,B,C,D,E,F have to be seated in a row and the restriction is that A and B cannot sit together.
Break the problem into 2 steps,

1)Find the number of ways we can seat the 6 people without any restriction
A B C D E F
This would be 6! = 720 ways.

2)Consider the restriction given.
We will find the number of ways to arrange them considering A and B are always together
Picture the arrangement treating A and B as one unit
AB C D E F
Number of ways the above arrangement is possible is
5!=120
Now AB could be BA as well,therefore total possibilities is 120*2=240

2)Therefore the total number of ways to seat A,B,C,D,E,F, without A and B sitting together is
720-240=480
Disregard my last question.

Thanks
Top
Post new topic Post Reply
• Page 1 of 1