CountTheOpposite InclusionExclusion Bundling AIME Difficult
2011


Problem - 266
Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Find the probability that each delegate sits next to at least one delegate from another country.

Firstly, while the people even from the same country are distinguishable, but we can treat them indistinguishable here because all the duplicate factors are equal which will be canceled when computing probability. Let's call these three countries as $A$, $B$, and $C$, respectively and use these letter to present people from their respective countries. Then this problem can be modeled as placing three $A$s, three $B$s, and three $C$s around the table such that every letter is next to at least one different letter.

It is easy to see that the opposite of a qualified arrangement is at least one group of three same letters are next to each other.

Let's pick up one $A$ as the anchor and fix its location. Call this special $A$ as $\mathbb{A}$. Then, the number of all the possible arrangements is $$C_8^2\times C_6^3 \times C_3^3 = 560$$

Now, let's count the number of cases where at least one group of three same letters are next to each other.

Firstly, the three $A$s are next to each other. There are two cases:

  • $\mathbb{A}$ is in the middle. There are $C_6^3=20$ ways.
  • $\mathbb{A}$ is not in the middle. There are $2\times C_6^3=40$ ways

Hence, there are totally $20+40=60$ ways for $A$s to be together.

Secondly, for three $B$s or three $C$s to be together. Each case has $C_6^1\times C_5^2 = 60$. (First select the left most seat for the three $B$s, and then select $2$ from the remaining to place $A$s.)

Thirdly, for both three $A$s and three $B$s (same for three $A$s and three $C$). There are again two cases depending on whether $\mathbb{A}$ is in the middle or not. There are totally $C_4^1 + 2\times C_4^1 = 12$ cases.

If three $B$s and three $C$s are both together, using bundling technique will give $C_4^1 \times C_3^1 = 12$ ways.

Finally, if all three $A$s, three $B$s and three $C$s are together, depending whether $\mathbb{A}$ is in the middle of the three $A$s or not, we have totally $C_2^1 + 2\times C_2^1 = 6$ cases.

It follows that the number of ways for at least one of the groups are together equals: $$(60+2\times 60)-(2\times 12 + 12) + 6 =150$$

Therefore, the final answer is $$\frac{560-150}{560}=\boxed{\frac{41}{56}}$$


report an error