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

Redeem

permutation

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Source: — Problem Solving |
User avatar
Legendary Member
Posts: 1556
Joined: Tue Aug 14, 2012 11:18 pm
Thanked: 448 times
Followed by:34 members
GMAT Score:650

by theCodeToGMAT » Tue Nov 26, 2013 11:53 pm
11 # signs and 8* signs

_#_#_#_#_#_#_#_#_#_#_#_

12C8
R A H U L
Top
Master | Next Rank: 500 Posts
Posts: 447
Joined: Fri Nov 08, 2013 7:25 am
Thanked: 25 times
Followed by:1 members

by Mathsbuddy » Thu Nov 28, 2013 1:49 am
Here's an improvised method that probably needs some adjusting:

Let # = 0 and * = 1

Example combinations:
1010101010101010000 (Legal)
1010101010101100000 (Illegal)

We can break the combinations into pairs like this:
PAIR TYPE A:
10 10 10 10 10 10 10 10 00 0 (Legal)
10 10 10 10 10 10 11 00 00 0 (Illegal)
Given that the maximum number of 11s is 4,
the number of ways of getting any 11s is 2^4 * 6

We can also break the combinations into pairs like this:
PAIR TYPE B:
0 10 10 10 10 10 10 10 10 00 (Legal)
0 10 10 10 10 10 10 11 00 00 (Illegal)
Given that the maximum number of 11s is 4,
the number of ways of getting any 11s is 2^4 * 6

So the total number of illegal pairs 2^4 * 12 (including overlaps between pair types A and B)

We can break the combinations into triples like this:
101 010 101 010 101 000 0 (Legal)
101 010 101 010 110 000 0 (Illegal)
Given that the maximum number of 111s is 2,
the number of ways of getting any 111s is 2^2 * 5

We can also break the combinations into triples like this:
0 101 010 101 010 101 000 (Legal)
0 101 010 101 010 110 000 (Illegal)
Given that the maximum number of 111s is 2,
the number of ways of getting any 111s is 2^2 * 5

So the total number of illegal triplets is 2^2 * 10

Illegal eights, sevens, sixes, fives and fours all include the illegal triples and illegal pairs.

The illegal triples occur when Pair type A and B overlap,
for example:
...0 111 0... = ...01 11 0... = ...0 11 10...
Therefore we must delete half of the the illegal triples:

Half of illegal triplets is 2^2 * 10 / 2 = 2^2 * 5

Hence the total number of illegal pairs is
2^4 * 12 - 2^2 * 5 = 16 * 12 - 4 * 5 = 172

This is merely a concept, and I've not had time to check it through.
So if anyone has any comments, they would be most welcome.
Thanks.
Top
User avatar
GMAT Instructor
Posts: 15539
Joined: Tue May 25, 2010 12:04 pm
Location: New York, NY
Thanked: 13060 times
Followed by:1906 members
GMAT Score:790

by GMATGuruNY » Thu Nov 28, 2013 3:57 am
parulmahajan89 wrote:In how many ways can 11 A's and 8 B's be arranged in a row so that no two B's occupy adjacent positions?
Since there is no constraint on the 11 A's, first place them in a row as follows:
_A_A_A_A_A_A_A_A_A_A_A_

To ensure that no two B's occupy adjacent positions, each must occupy one of the empty slots shown above.
Number of options for the 1st B = 12.
Number of options for the 2nd B = 11.
Number of options for the 3rd B = 10.
Number of options for the 4th B = 9.
Number of options for the 5th B = 8.
Number of options for the 6th B = 7.
Number of options for the 7th B = 6.
Number of options for the 8th B = 5.
To combine these options, we multiply:
12*11*10*9*8*7*6*5.

Since the B's are identical, the ORDER of the occupied positions doesn't matter.
Whether the 8 identical B's occupy positions 1-3-5-7-9-11-13-15 or 3-1-15-13-5-9-7-11, the arrangement stays the same.
Thus, so that we don't overcount the total number of unique arrangements, we divide by the number of ways that the 8 occupied positions can be ARRANGED (8!):
(12*11*10*9*8*7*6*5)/(8*7*6*5*4*3*2*1) = 495.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
Top
Master | Next Rank: 500 Posts
Posts: 447
Joined: Fri Nov 08, 2013 7:25 am
Thanked: 25 times
Followed by:1 members

by Mathsbuddy » Thu Nov 28, 2013 7:08 am
GMATGuruNY wrote:
parulmahajan89 wrote:In how many ways can 11 A's and 8 B's be arranged in a row so that no two B's occupy adjacent positions?
Since there is no constraint on the 11 A's, first place them in a row as follows:
_A_A_A_A_A_A_A_A_A_A_A_

To ensure that no two B's occupy adjacent positions, each must occupy one of the empty slots shown above.
Number of options for the 1st B = 12.
Number of options for the 2nd B = 11.
Number of options for the 3rd B = 10.
Number of options for the 4th B = 9.
Number of options for the 5th B = 8.
Number of options for the 6th B = 7.
Number of options for the 7th B = 6.
Number of options for the 8th B = 5.
To combine these options, we multiply:
12*11*10*9*8*7*6*5.

Since the B's are identical, the ORDER of the occupied positions doesn't matter.
Whether the 8 identical B's occupy positions 1-3-5-7-9-11-13-15 or 3-1-15-13-5-9-7-11, the arrangement stays the same.
Thus, so that we don't overcount the total number of unique arrangements, we divide by the number of ways that the 8 occupied positions can be ARRANGED (8!):
(12*11*10*9*8*7*6*5)/(8*7*6*5*4*3*2*1) = 495.
A tremendous solution! I like the addition of 'extra slots' to make it possible.
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 16207
Joined: Mon Dec 08, 2008 6:26 pm
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1268 members
GMAT Score:770

by Brent@GMATPrepNow » Thu Nov 28, 2013 7:31 am
parulmahajan89 wrote:In how many ways can 11 A's and 8 B's be arranged in a row so that no two B's occupy adjacent positions?
I just want to elaborate on theCodeToGMAT's excellent solution so that others can see what's he's doing.

Arrange the 11 A's as follows: _A_A_A_A_A_A_A_A_A_A_A_
Notice if we place a B in any of the 12 blank spaces, we can be guaranteed that no 2 B's occupy adjacent positions.
For example, here's one possible arrangement: _ABABABABA_ABABA_A_ABABAB

So, at this point, we need only determine the number of different ways to select 8 blank spaces (in which to place a B).
Since the order in which we select the blank spaces does not matter, we can use combinations.
We can select 8 of the 12 blank spaces in 12C8 ways.

Aside: When calculating combinations, it's useful to apply the following rule: nCr = nC(n-r). In other words, "n choose r" is equal to "n choose n - r"
So, for example: 10C7 = 10C3
15C11 = 15C4
8C7 = 8C1
etc.

So, 12C8 = 12C4 = 495

If anyone is interested, we have a free video on calculating combinations (like 12C4) in your head: https://www.gmatprepnow.com/module/gmat-counting?id=789

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image
Top
Senior | Next Rank: 100 Posts
Posts: 37
Joined: Wed Sep 11, 2013 4:33 am

by vishalpathak » Thu Nov 28, 2013 10:52 am
Mathsbuddy wrote:
GMATGuruNY wrote:
parulmahajan89 wrote:In how many ways can 11 A's and 8 B's be arranged in a row so that no two B's occupy adjacent positions?
Since there is no constraint on the 11 A's, first place them in a row as follows:
_A_A_A_A_A_A_A_A_A_A_A_

To ensure that no two B's occupy adjacent positions, each must occupy one of the empty slots shown above.
Number of options for the 1st B = 12.
Number of options for the 2nd B = 11.
Number of options for the 3rd B = 10.
Number of options for the 4th B = 9.
Number of options for the 5th B = 8.
Number of options for the 6th B = 7.
Number of options for the 7th B = 6.
Number of options for the 8th B = 5.
To combine these options, we multiply:
12*11*10*9*8*7*6*5.

Since the B's are identical, the ORDER of the occupied positions doesn't matter.
Whether the 8 identical B's occupy positions 1-3-5-7-9-11-13-15 or 3-1-15-13-5-9-7-11, the arrangement stays the same.
Thus, so that we don't overcount the total number of unique arrangements, we divide by the number of ways that the 8 occupied positions can be ARRANGED (8!):
(12*11*10*9*8*7*6*5)/(8*7*6*5*4*3*2*1) = 495.
A tremendous solution! I like the addition of 'extra slots' to make it possible.
Apologies for this dumb questions but I want to understand my error here. I tried solving by first arranging all Bs

_B_B_B_B_B_B_B_B_

Now we must place 7 A's between these 8 B's in order to ensure that no 2 B's are together.

So we get

_B A B A B A B A B A B A B A B_

Now we are left with 11-7 = 4 A's. These A's can be place in any of the 9 places (2 at the ends and 7 between B's)

No of ways to place each A = 9
Therefore no of ways = 9^4.
We can divide this by 4! inorder to avoid double counting.

Kindly point my mistake

Tegards,
Vishal
Top
Master | Next Rank: 500 Posts
Posts: 447
Joined: Fri Nov 08, 2013 7:25 am
Thanked: 25 times
Followed by:1 members

by Mathsbuddy » Fri Nov 29, 2013 9:27 am
GMATGuruNY wrote:
parulmahajan89 wrote:In how many ways can 11 A's and 8 B's be arranged in a row so that no two B's occupy adjacent positions?
Since there is no constraint on the 11 A's, first place them in a row as follows:
_A_A_A_A_A_A_A_A_A_A_A_

To ensure that no two B's occupy adjacent positions, each must occupy one of the empty slots shown above.
Number of options for the 1st B = 12.
Number of options for the 2nd B = 11.
Number of options for the 3rd B = 10.
Number of options for the 4th B = 9.
Number of options for the 5th B = 8.
Number of options for the 6th B = 7.
Number of options for the 7th B = 6.
Number of options for the 8th B = 5.
To combine these options, we multiply:
12*11*10*9*8*7*6*5.

Since the B's are identical, the ORDER of the occupied positions doesn't matter.
Whether the 8 identical B's occupy positions 1-3-5-7-9-11-13-15 or 3-1-15-13-5-9-7-11, the arrangement stays the same.
Thus, so that we don't overcount the total number of unique arrangements, we divide by the number of ways that the 8 occupied positions can be ARRANGED (8!):
(12*11*10*9*8*7*6*5)/(8*7*6*5*4*3*2*1) = 495.
Hi there,

I already praised the beauty of the simplicity of your solution. However, on further reflection, I have thought that it is not explicit in the question that each combination MUST be unique. It just asks "how many ways", and I would say that the number of ways of arranging two As is 2 (AA or AA). Just because they are identical doesn't mean we can ignore the alternative arrangements. And similarly for the Bs too!

Therefore I propose that Bs can be arranged 12*11*10*9*8*7*6*5 ways = 12!-4!
and As can be arranged 11! ways.
Hence there are 11! * (12! - 4!) ways altogether. The question did not use the term "unique".

So ANSWER = 11! * (12! - 4!) = 1.9 x 10^16 (2 s.f.)

If we are to be outstanding GMat problem solvers, we must not make assumptions. OK, I know the answers given guide us, but without the word "unique" how are we to know what the question wants.
If I were doing a probability question, I might want to know the (non-unique) number of ways as a denominator. How do we not know that the examiner does not want this also?

Do you think I have a valid point? :)
Top
User avatar
GMAT Instructor
Posts: 15539
Joined: Tue May 25, 2010 12:04 pm
Location: New York, NY
Thanked: 13060 times
Followed by:1906 members
GMAT Score:790

by GMATGuruNY » Sun Dec 01, 2013 4:50 am
vishalpathak wrote:
Apologies for this dumb questions but I want to understand my error here. I tried solving by first arranging all Bs

_B_B_B_B_B_B_B_B_

Now we must place 7 A's between these 8 B's in order to ensure that no 2 B's are together.

So we get

_B A B A B A B A B A B A B A B_

Now we are left with 11-7 = 4 A's. These A's can be place in any of the 9 places (2 at the ends and 7 between B's)

No of ways to place each A = 9
Therefore no of ways = 9^4.
We can divide this by 4! inorder to avoid double counting.

Kindly point my mistake

Tegards,
Vishal
Let's examine a subset:
BAB.

Applying your reasoning, there are 3 options for each A that is added:
Before the first B.
Between the two B's.
After the second B.
Thus, according to your reasoning, for each A that is added, the number of arrangements should increase by a factor of 3.
If 2 A's are added, your approach will proceed as follows:
3*3 = 9.

Let's see whether this line of reasoning is valid.

Options for the next A:
BAB --> ABAB, BAAB, BABA.
Total unique arrangements = 3.

Options for the next A:
ABAB --> AABAB, ABAAB, ABABA
BAAB --> ABAAB, BAAAB, BAABA
BABA --> ABABA, BAABA, BABAA
The arrangements in red are DUPLICATES.
Total unique arrangements = 6.

Your approach doesn't account for the duplicates in red and thus overcounts the number of unique arrangements.
Also, the total yielded by your approach (9) is not a multiple of the actual total (6), so we can't simply divide 9 by 2! or by some other value to yield the actual total.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
Top
Post new topic Post Reply
• Page 1 of 1