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$.

First I want to tackle the total number of possibilities for the arrangements, but since that seems a more troublesome idea, I'll actually get to it later.

Let's fix chair one, the top chair, and let $A, B ,C$ be the countries so we have people: $AAA, BBB, CCC$ total 9.

Case 1: $A$, Case 2: $B$, Case 3: $C$.

Consider Case 1 First: $(A$_ _)( _ _ ) ( _ _)

Considering the first bracket space first: We have:

  • 1
    $\begingroup$ Please fix your title. $\endgroup$ – Thomas Andrews Aug 16 '15 at 20:41
  • $\begingroup$ @ThomasAndrews: I changed the title. How is it now? $\endgroup$ – Rory Daulton Aug 16 '15 at 21:55


Let $A$ denote the event that the delegates from Alaska choose seats next to each other.

Let $B$ denote the event that the delegates from Belgium choose seats next to each other.

Let $C$ denote the event that the delegates from Canada choose seats next to each other.

Then to be found is actually $$1-P\left(A\cup B\cup C\right)$$

With inclusion/exclusion and symmetry we find:

$$P\left(A\cup B\cup C\right)=3P\left(A\right)-3P\left(A\cap B\right)+P\left(A\cap B\cap C\right)$$

A tip to find $P\left(A\right)$. If the first delegate of Alaska has taken his place then there are $\binom{8}{2}$ possibilities left for the other two from Alaska. In $3$ of these cases event $A$ will occur.

Also note that $P\left(A\cap B\right)=P\left(B\mid A\right)P\left(A\right)$ and $P\left(A\cap B\cap C\right)=P\left(B\cap C\mid A\right)P\left(A\right)$. To find $P(B|A)$ and $P\left(B\cap C\mid A\right)$ think of the situation in wich the $3$ delegates from Alaska have allready taken their seats and sit next to each other. Then $\binom63$ possibilities are left for the $3$ delegates from Belgium and in $4$ of the cases they come to sit next to each other, so that $A\cap B$ occurs. In $2$ of the cases $3$ chairs next to each other are left for the $3$ Canadians, so that $A\cap B\cap C$ occurs.

  • $\begingroup$ (Are you one of these Alaska secessionists?) $\endgroup$ – user84413 Aug 16 '15 at 21:35
  • $\begingroup$ @user84413 Actually it is the first time that I encounter the term secessionist (I am Dutch). So let me put you at ease: no. $\endgroup$ – drhab Aug 16 '15 at 21:41
  • $\begingroup$ Thanks for your reply, and of course I was just joking. (There really are people in Alaska who want to form their own country, though.) $\endgroup$ – user84413 Aug 16 '15 at 21:43
  • 3
    $\begingroup$ The Alaska comment is based on the fact that Alaska is not actually a country, just a state within the United States of America. You may want to use one of the countries that start with the letter A, such as Afghanistan. That is not necessary, though. And I'm glad you have the same main love that I do! $\endgroup$ – Rory Daulton Aug 16 '15 at 21:58
  • $\begingroup$ @RoryDaulton Ah.. that makes things clear! I won't change it, just to keep the comments relevant. As you will understand your gladness is of course my gladness too. $\endgroup$ – drhab Aug 16 '15 at 22:09

You finished your question at a strange place, so I'll just give some hints now. Clean up your question if you want more detail.

  • There exists someone from country A who is not seated next to someone from another country if and only if the three A delegates are seated in a group, AAA.
  • There are nine places for that block of 3 A delegates to sit. The other six places can be arranged in any way, and all those seating arrangements will not be included in your desired probability.
  • Use those facts to find how many seating arrangements have someone from country A who is not seated next to someone from another country. That will be the same number as for someone from country B and for someone from country C.
  • There is double-counting for all those bad seating arrangements in the last hint. The Inclusion–exclusion principle for three sets can be used to remove that double counting.
  • To do that you will need to find bad seating arrangements due to country A and due to country B, etc. That is the same number for A and C, and for B and C. Then find bad seating arrangements due to all three countries A, B, and C.
  • The number of all seating arrangements is the same as the number of permutations of 9 objects where 3 are identical, another 3 are identical, and the last 3 are identical. This is a multinomial coefficient. You can also use a multinomial coefficient to do the calculation in my second bullet point, though a binomial coefficient also works there.
  • $\begingroup$ Just to let you know: your main love coincides with mine. $\endgroup$ – drhab Aug 16 '15 at 21:54

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.