Problem Solving

In how many ways can 11 # signs and 8* signs be arranged in a row so that no two * signs come together?

11 # signs and 8* signs

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

12C8

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.

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.

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.

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

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?

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.