# Difference between revisions of "2011 AIME II Problems/Problem 12"

## Problem 12

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

## Solution

Use complementary probability and Principle of Inclusion-Exclusion. If we consider the delegates from each country to be indistinguishable and number the chairs, 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.

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. This comes to $$\frac{27\cdot6\cdot5\cdot4}6 = 27\cdot 20.$$

Among these there are $3 \times 9 \times 4$ ways for candidates from two countries to each sit together. This comes to $27\cdot 4.$

Finally, there are $9 \times 2 = 18.$ ways for the candidates from all the countries to sit in three blocks (9 clockwise arrangements, and 9 counter-clockwise arrangements).

So, by PIE, the total count of unwanted arrangements is $27\cdot 20 - 27\cdot 4 + 18 = 16\cdot27 + 18 = 18\cdot25.$ So the fraction $$\frac mn = \frac{30\cdot 56 - 18\cdot 25}{30\cdot 56} = \frac{56 - 15}{56} = \frac{41}{56}.$$ Thus $m + n = 56 + 41 = \fbox{097}.$

 2011 AIME II (Problems • Answer Key • Resources) Preceded byProblem 11 Followed byProblem 13 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 All AIME Problems and Solutions