tough one - combinations

[voodoo_child]

In how many ways can the letters in "abcdabcd" be arranged without letting two letters which are alike come together?

a)2520
b)864
c)324
d)648
e)468

OA B

Any thoughts?

[pskharche]

haha - very easy - 2520

Is it right? let me know so I wil post the solution as well

[sl750]

Arrange the letters without any restriction. This can be done in 8!/(2!)^4 ways, as we have four-two repeating letters

Assume the letters are together, the opposite of what the question states. This allows us to club the identical letters as one unit.
Number of ways to arrange 4 letters is 4! ways

This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters

Therefore, number of ways of arranging the letters without two identical letters being adjacent to each other is 8!/(2!)^4 - (8!/4! - 4!) = 864 . The 4! has to be subtracted from 8!/4! to avoid duplicate counting

[rijul007]

This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters

i didnt get this part of the solution..
after clubbing all alike letters together, where did the 4 empty slots come from????

[pskharche]

I think GMAT Destroyer is correct !

I just limited my thinking till 8!/2!*4

[sl750]

This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters

i didnt get this part of the solution..
after clubbing all alike letters together, where did the 4 empty slots come from????

As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots

[user123321]

This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters

i didnt get this part of the solution..
after clubbing all alike letters together, where did the 4 empty slots come from????

As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots

could you explain say if the letters are ABCABC what the solution might be?

I partly was not able to understand the 8!/4! in your solution.

Thanks
user123321

[sl750]

This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters

i didnt get this part of the solution..
after clubbing all alike letters together, where did the 4 empty slots come from????

As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots

could you explain say if the letters are ABCABC what the solution might be?

I partly was not able to understand the 8!/4! in your solution.

Thanks
user123321

For ABCABC
The two A's are joined as one
The two B's are joined as one
The two C's are joined as one
ABC_ _ _
Fill the blanks with X's
ABCXXX

This can be arranged in 6!/3! ways. The 3! represents the X's

[rijul007]

This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters

i didnt get this part of the solution..
after clubbing all alike letters together, where did the 4 empty slots come from????

As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots

could you explain say if the letters are ABCABC what the solution might be?

I partly was not able to understand the 8!/4! in your solution.

Thanks
user123321

For ABCABC
The two A's are joined as one
The two B's are joined as one
The two C's are joined as one
ABC_ _ _
Fill the blanks with X's
ABCXXX

This can be arranged in 6!/3! ways. The 3! represents the X's

I didnt why you did this...

[user123321]

This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters

i didnt get this part of the solution..
after clubbing all alike letters together, where did the 4 empty slots come from????

As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots

could you explain say if the letters are ABCABC what the solution might be?

I partly was not able to understand the 8!/4! in your solution.

Thanks
user123321

For ABCABC
The two A's are joined as one
The two B's are joined as one
The two C's are joined as one
ABC_ _ _
Fill the blanks with X's
ABCXXX

This can be arranged in 6!/3! ways. The 3! represents the X's

There is still problem in your explanation.
If it is so,

for abcabc, based on your explanation, it will be
6!/2^3 - (6!/3! - 3!) = 90 - 120 + 6 = -ve which is wrong

Maybe i am wrong in understanding the concept

user123321

[pskharche]

Gotcha !!

I think i figured out the flaw - please correct me if I am wrong.

You say that -
************************************************************
I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots
************************************************************

But you already did this clubbing in 8!/4!.

You avoided counting aabbccdd kind of cases when you divided 8! by 4! (the first term in your solution).

Does that help guys?

[user123321]

Gotcha !!

I think i figured out the flaw - please correct me if I am wrong.

You say that -
************************************************************
I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots
************************************************************

But you already did this clubbing in 8!/4!.

You avoided counting aabbccdd kind of cases when you divided 8! by 4! (the first term in your solution).

Does that help guys?

if you club and form four sets, then you will miss combinations as
AAbcdbcd
AABBcdcd
......
which are still valid ones to be accounted for.

I will try the hard way after office :3
I am outta brains for today

user123321

[GmatMathPro]

Notes:

1. In my opinion this is too hard for a real GMAT question.

2. The following explanation is long for the sake of clarity, but the solution doesn't take that long once you see the pattern for how to handle the double-counting.





Here is why:

The overall strategy is to count the number of ways to arrange abcdabcd with no restrictions and then subtract out any ones where adjacent letters match. I think we all agree that the first part is 8!/16 or 2520, so let's focus on counting the cases where adjacent letters match (the part in parentheses above).

First, some sequences will have exactly one pair of adjacent letters such as aabcdbcd some will have two, such as aabbcdcd, some will have 3 daabbccd, and some will have 4, aabbccdd. Let's agree to call a sequence with exactly n adjacent matching pairs Sn. So S1 will mean sequences like aabcdbcd with exactly one adjacent pair matching, up to S4 which will represent cases like aabbccdd where exactly 4 adjacent pairs are matching. The trick is not double counting any of them when you count up how many there are of each.

We can count the ones that have at least one match as follows:
1. Choose one of the four letters a,b,c,d, and merge or "club" the two letters together. If you choose a, it would be like Abbccdd, with capital A representing the grouping of two lowercase a's. We can arrange this 7!/(2!2!2!) ways, with the 2!2!2! there to divide out the repeats. There are 4C1 ways to choose the letter treat as one, so there are 4C1(7!/(2!^3)) ways. This explains the first term within the parentheses. But note that this counts some of the sequences multiple times. For example, when you club the a's, you will count sequences such as aabbcdcd, but you will also count this sequence when you club the b's. Something like daabbccd will get counted three times because it will get counted once each time you club the a's b's and c's. With this logic, the number of time's we're counting the S1,S2,S3,S4 is as follows:

S1=1
S2=2
S3=3
S4=4

but we only want to count each of these once. So we need to subtract.

2. Count how many ways you can have two or more adjacent matching pairs:
By similar logic to above, we can choose the 2 letters in 4C2 ways, and then there will be 6!/2!^2 ways to arrange the letters. so 4C2*6!/2!^2 ways to have at least two adjacent matching pairs. This will count the S3's 3 times each and the S4's 6 times each. To see why, note that each S4 will be counted for any two letters you club together, so each one gets counted 4C2=6 ways total. Likewise, the S3's get counted 3C2=3 ways. Because, for example something like daabbccd gets counted when you club 1. a's and b's, 2. b's and c's, and 3. a's and c's as 1. dABccd 2. daaBCd 3. dAbbCd respectively. So, if we subtract out the ones with at least 2, we now have the following count:

S1=1
S2=1
S3=0
S4=-2

So we're making progress, but now S3's arent counted at all and S4's are being counted negative times. So we need to add some stuff in.

3. Count the number of ways to have at least 3 matches: 4C3*5!/2!. This counts The number of S3's one time and the number of S4's 4 times. Add this number in and we have the following count:

S1=1
S2=1
S3=1
S4=2

Now we're just about done, but we need to subtract the number of ways to have 4 matching pairs which is just 4!, and our count is perfect:

S1=1
S2=1
S3=1
S4=1

So we start with the term from number 1, subtract the term from number 2, add the term from number 3, and subtract the term from number 4 to get the number of unique sequences that have at least one adjacent matching pair. subtract this from 2520 to get 864.

[user123321]

thanks for the explanation. This surely is a 800+ question, if this kind of question is not touched before gmat.

user123321

[voodoo_child]

Notes:
But note that this counts some of the sequences multiple times. For example, when you club the a's, you will count sequences such as aabbcdcd, but you will also count this sequence when you club the b's. Something like daabbccd will get counted three times because it will get counted once each time you club the a's b's and c's. With this logic, the number of time's we're counting the S1,S2,S3,S4 is as follows:

S1=1
S2=2
S3=3
S4=4

Pete, I went through almost 1/4th of your solution. However, I couldnt understand above treatment. Can you explain ?

for S4, if I start with A,
aabbccdd
is different from starting with B,
i.e. bbaaccdd Isnt it?
I dont understand why S4=4....

Thanks in advance!