# 2011 AIME Problem 12, probability round table

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 have been searching around math stackexchange and I saw this difficult question, so I decided to try to work it out myself.

Question: I am numbering the chairs from (top to last) as $1, 2, 3, 4, 5, 6, 7, 8, 9$.

Now I am stuck, how many ways are there TOTAL to arrange the people?

We want $P = 1 - P(\overbrace{\text{at least one block is the same or all three.}}^{x}) = 1 - P(x).$

The denominator is: $\binom{9}{3, 3, 3}$.This is the number of ways to make three groups of three objects in each.

Next: How many ways are there to make one block identical eg. $AAA$?

But for each $AAA$ there are three cases. Fix $a$ on chair 1 then there are possibilities: $AAa, aAA, AaA$. Thus for the $A$ there are: $3\binom{6}{3, 3}$ ways to arrange at least one block. Same for $B, C$ hence, $9\binom{6}{3, 3}$ total.

But in this we counted the $AAABBBCCC$ arrangements several times. For each $AAA$ there are two possible $AAABBBCCC$ sequences. So subtract $2(9) = 18$.

Hence:

$P = 1 - \frac{9\binom{6}{3, 3} - 18}{\binom{9}{3, 3, 3}} = \frac{253}{280}$

WRONG answer. I am confused, what I did wrong?

• math.stackexchange.com/questions/891601/… – Wojciech Karwacki Aug 19 '15 at 8:52
• Can you please explain how $27$ people fit into $9$ seats? – barak manos Aug 19 '15 at 9:07
• @barakmanos, wait when did I put 27 people? – Amad27 Aug 19 '15 at 9:12
• "Nine delegates, three each": $9\cdot3=27$. – barak manos Aug 19 '15 at 9:18
• @barakmanos, I still don't understand – Amad27 Aug 19 '15 at 9:23

In your setup we have $\binom9{3,3,3}=1680$ possibilities in total.

Let $n(A)$ denote the number of possibilities such that you have a block $AAA$. Likewise we use notations $n(B)$ and $n(C)$. Then $n(A)=n(B)=n(C)=9\binom6{3,3}=180$.

Let $n(A\cap B)$ denote the number of possibilities s.t. there is a block $AAA$ and a block $BBB$. Then $n(A\cap B)=n(A\cap C)=n(B\cap C)=9\times4=36$

Let $n(A\cap B\cap C)$ denote the number of possibilities s.t. there is a block $AAA$, a block $BBB$ and a block $CCC$. Then $n(A\cap B\cap C)=9\times2=18$

Finally let $n(A\cup B\cup C)$ denote the number of possibilitis such that there is block $AAA$ or a block $BBB$ or a block $CCC$.

With inclusion/exclusion we find:

$$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(A\cap C)-n(B\cap C)+n(A\cap B\cap C)=3\times180-3\times36+18=450$$

So there is probability of $\frac{450}{1680}=\frac{15}{56}$ that there is at least one block and a probability of $\frac{41}{56}$ that there is no block.

The numbers $41$ and $56$ are coprime, so the final answer is $41+56=97$.

Hints for another setup can be found here.

• (+1) I am a little confused regarding the multinomial coefficient in these cases. With: $$\binom{9}{3,3, 3}$$ This means the numbers of ways to arrange three groups of three objects each. Does this for example consider: $(AAA)(BCB)(CBC)$ for example? – Amad27 Aug 20 '15 at 7:59
• I am no sure to understand your the question posed in the comment. The coefficient is the number of $9$-letter words that contain $3$ A's, $3$ B's and $3$ C's. The word in your comment is (if you remove the brackets) indeed one of these words. I don't see the relevance of the brackets. – drhab Aug 20 '15 at 8:14
• My question was as you see what N.Hales said here: math.stackexchange.com/questions/1403100/… , he said we subtract the four (written in his answer). But in reality, Don't we also need to subtract configurations such as: $AAABCBCBC$ from the $3 \cdot 9 \cdot \binom{6}{3, 3}$. Moreover What does $\binom{6}{3, 3}$ even represent? We begin with $AAA$, then the $3, 3$ means how many possible two blocks of three elements each right? If yes, then $AAABCBCBC$ is also included in that correct? – Amad27 Aug 20 '15 at 10:08
• After adding up $n(A),n(B)$ and $n(C)$ we need to subtract configurations that are counted more than once. E.g. configuration $AAACBBBCC$ is one of them. This because there is a block $AAA$ in it (so counted under $n(A)$) and there is a block $BBB$ in it (so counted under $n(B)$). Configuration $AAABCBCBC$ not one of them. $\binom6{3,3}$ equals the number of $6$-letter words containing $3$ B's and $3$ C's. It comes in when $3$ of the original $9$ spots are allready possessed by an $AAA$ block. – drhab Aug 20 '15 at 10:33
• okay it is starting to make more sense now, but how is $AAACBBBCC$ a configuration counted more than once? So: $n_1(a) = AAACBBBCC$ and $n_1(b) = AAACBBBCC$ too? Then is: $BBBCAAACC$ overcounted twice as well? – Amad27 Aug 20 '15 at 11:56

You got the total probability right. Now regarding the numerator. (I would like to note that in your solution, you regarded the delegates from each country to be indistinguishable). We need to find the number of ways that each delegate sits next to at least one delegate from another country

The number of ways to make one block identical is actually not what you have. Suppose you have AAA as one block. Then the other six delegates can be arranged in $\binom{6}{3, 3}$ ways. However, you do not arrange the 3 delegates inside the AAA block. Instead, you can put the AAA block in any of the 9 chairs. So we have $9\times \binom{6}{3, 3}$ ways to have an AAA block. So the number of ways to have an identical block is $3 \times 9\times \binom{6}{3, 3}=27\times 20.$

We now need the number of ways for candidates from two countries to each sit together. We can do this in $3\times9\times4=27\times4$ ways. (I believe this is the part you didn't calculate)

Finally we need the number of ways that the candidates from all countries sit together. This can be done in $9\times2=18$ ways, one clockwise and the other anticlockwise.

So the total number of unwanted arrangements is $27\times20-27\times4+18.$

This should lead you to the right answer (I don't know the answer because the AOPS site seems to be down, but I got $m+n$ to be $97.$)

• (+1). A little confused though, how did you get $3 \times 9 \times 4$ ways for the candidates from two countries to sit together? I see that there are for example, $9$ ways to arrange the $AAA$ Then the possibilities are: $BCBCBC, CBCBCB, BBBCCC, CCCBBB$. So these are the four? – Amad27 Aug 19 '15 at 17:17
• The answer is correct. – drhab Aug 19 '15 at 20:45