Difference between revisions of "2011 AIME II Problems/Problem 12"
m (wikify) |
|||
| Line 1: | Line 1: | ||
== 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 <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>. | + | 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 <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are [[relatively prime]] positive integers. Find <math>m + n</math>. |
== Solution == | == 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 <cmath>\frac{9!}{(3!)^3} = \frac{9\cdot8\cdot7\cdot6\cdot5\cdot4}{6\cdot6} = 6\cdot8\cdot7\cdot5 = 30\cdot56</cmath> total ways to seat the candidates. | ||
| − | + | Of these, there are <math>3 \times 9 \times \frac{6!}{(3!)^2} </math> ways to have the candidates of at least some one country sit together. This comes to <cmath>\frac{27\cdot6\cdot5\cdot4}6 = 27\cdot 20.</cmath> | |
| − | + | Among these there are <math> 3 \times 9 \times 4 </math> ways for candidates from two countries to each sit together. This comes to <math> 27\cdot 4. </math> | |
| − | + | Finally, there are <math> 9 \times 2 = 18.</math> 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 <math>27\cdot 20 - 27\cdot 4 + 18 = 16\cdot27 + 18 = 18\cdot25. </math> So the fraction <cmath> \frac mn = \frac{30\cdot 56 - 18\cdot 25}{30\cdot 56} = \frac{56 - 15}{56} = \frac{41}{56}.</cmath> Thus <math>m + n = 56 + 41 = \fbox{097}.</math> | |
| − | + | == See also == | |
| + | {{AIME box|year=2011|n=II|num-b=11|num-a=13}} | ||
| − | + | [[Category:Intermediate Combinatorics Problems]] | |
| − | |||
| − | |||
Revision as of 21:24, 22 August 2011
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 ![\[\frac{9!}{(3!)^3} = \frac{9\cdot8\cdot7\cdot6\cdot5\cdot4}{6\cdot6} = 6\cdot8\cdot7\cdot5 = 30\cdot56\]](http://latex.artofproblemsolving.com/8/7/a/87a8106f953586f11987836e4afba2abdd223b07.png)
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 ![\[\frac{27\cdot6\cdot5\cdot4}6 = 27\cdot 20.\]](http://latex.artofproblemsolving.com/6/9/7/697fa4dead6eaf9bae735e8d3197a84bf79929b1.png)
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 ![\[\frac mn = \frac{30\cdot 56 - 18\cdot 25}{30\cdot 56} = \frac{56 - 15}{56} = \frac{41}{56}.\]](http://latex.artofproblemsolving.com/4/0/6/406a20b8393defde8e35a1ee5ad1bbfe956e4a5c.png)
Thus 
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 | ||
