Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate from another country be $\frac{m}{n}$, where m and n are relatively prime positive integers. Find $m + n$.

I was going through the solution at AoPS, and I didn't understand several things.

We have $$\frac{9!}{(3!)^3} = \frac{9\cdot8\cdot7\cdot6\cdot5\cdot4}{6\cdot6} = 6\cdot8\cdot7\cdot5 = 30\cdot56$$ total ways to seat the candidates.

Because the candidates are seated in a circle, shouldn't it be $$\frac{\frac{9!}{(3!)^3}}{9}$$ to account for the rotations?

Of these, there are $$3 \times 9 \times \frac{6!}{(3!)^2}$$ ways to have the candidates of at least some one country sit together.

My question comes from why they used $$\frac{9\cdot 6!}{3!3!}$$

I believe their reasoning is that there are nine ways to choose the three consecutive chairs that the three delegates from a specific country A sit in, and then $\binom{6}{3}$ ways to seat the other country and then the last country sits in the open spots.

However, I tried to do this a different way, by considering the three delegates from country A as one entity, and then you have the 6 seats + 1 group to arrange around the circle, which can be done in $\frac{7!}{3!3!}$ ways.

However, this does not match with their expression. Why?

  • 1
    $\begingroup$ In the count, they seem to count the $9$-letter words that use $3$ each of the letters A, B, C. That's fine, as long as we count the "bads" using the same convention, and remember that the same country at the two ends is also bad. $\endgroup$ – André Nicolas Aug 9 '14 at 0:48
  • $\begingroup$ @AndréNicolas What about the second part to my question: Why couldn't I treat the 3 delegates from country A as one group and then arrange that group among the 6 others? $\endgroup$ – 1110101001 Aug 9 '14 at 1:04
  • 1
    $\begingroup$ That does not seem to take care of all cases. $\endgroup$ – André Nicolas Aug 9 '14 at 1:10
  • 1
    $\begingroup$ Using the straightline analysis, two at one end and one at the other. If we instead divide by $9$, which is sensible, we have to deal with B and C, and some inclusion/exclusion is needed. $\endgroup$ – André Nicolas Aug 9 '14 at 1:21
  • 1
    $\begingroup$ The count of the favourables depends on how we count the total. But with total as given, the position of the leftmost of Group A matters. $\endgroup$ – André Nicolas Aug 9 '14 at 1:42

They are making two simplifying assumptions in their solution, that the seats are numbered and that people from the same country are identical.

1) They didn't divide by $9$ in finding their total because they were assuming the seats were numbered; otherwise they would have.

2) Your expression of $\frac{7!}{3!3!}$ would work fine if the people were arranged in a straight line. Notice that in this case the 3 people sitting together have 7 choices for their positions: $123, 234, \cdots, 789$.
In a circle, though, they have 9 choices instead: $123, 234, \cdots, 789, 891, 912$.

If we assumed that the 9 people were all distinct and we didn't number the seats, then we would get the same probability of

$\displaystyle 1-\frac{\binom{3}{1}3!6!-\binom{3}{2}4(3!)^{3}+2(3!)^{3}}{8!}=1-\frac{10800}{40320}=1-\frac{15}{56}=\frac{41}{56}$.

  • $\begingroup$ Could you please explain why your middle term is $\binom{3}{2}4(3!)^{3}$ $\endgroup$ – Anirudh Dec 30 '17 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.