2011 AIME II Problems/Problem 12
Contents
[hide]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 , where and are relatively prime positive integers. Find .
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 total ways to seat the candidates.
Of these, there are ways to have the candidates of at least some one country sit together. This comes to
Among these there are ways for candidates from two countries to each sit together. This comes to
Finally, there are 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 So the fraction Thus
Setup Solution
We should give a specific setup for the table so to simplify. Call countries A, B, C. Someone from A (let me call him/her the "Master A") sits at the northernmost place for configurations. In my solution I choose to represent people by countries, because all the problem says about distinction among delegates is their country. Now, we can see that the total number of ways to arrange is nCr(8, 2) * nCr(6, 3) = 560 (8 seats choose 2 for the rest of the A country, 6 seats choose 3 for B).
It is not difficult to see that the configurations we don't want are those which put three delegates in a row. Note also that despite my (arbitrary) setting A at the front, cases for A, B, C to be together are symmetric. Now, we use some Principle of Inclusion-Exclusion. For A three in a row: two cases. First. A, Master A, A: nCr(6, 3) for B seats = . There's also for each of the "slant" A sets (i.e. A, A, Master A and Master A, A, A). =. For both A and B: Two cases again! A, Master A, A: we see 4 ways for B to have 3-in-a-row. Same for slant = (AB, BC, or CA) = . For all three: This time, we have 2 for each of the 3 aforementioned A situations = 6. Finally, 180-36+6=150. Those are the ones we don't want. The ones we do want are 410 of 560, so our answer is .
See also
2011 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.