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.
  
Use complementary probability and PIE.
+
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>
  
If we consider the delegates from each country to be indistinguishable and number the chairs, we have <cmath>\frac{9!}{(3!)^3}</cmath> total ways to seat the candidates. This comes to: <cmath>\frac{9\cdot8\cdot7\cdot6\cdot5\cdot4}{6\cdot6} = 6\cdot8\cdot7\cdot5 = 30\cdot56.</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>
  
Of these there are <cmath> 3 \times 9 \times \frac{6!}{(3!)^2} </cmath> 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>
+
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).
  
Among these there are <cmath> 3 \times 9 \times 4 </cmath> ways for candidates from two countries to each sit together. This comes to <cmath> 27\cdot 4. </cmath>
+
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>
  
Finally, there are <cmath> 9 \times 2 = 18.</cmath> ways for the candidates from all the countries to sit in three blocks (9 clockwise arrangements, and 9 counter-clockwise arrangements).
+
== See also ==
 +
{{AIME box|year=2011|n=II|num-b=11|num-a=13}}
  
So, by PIE, the total count of unwanted arrangements is <cmath>27\cdot 20 - 27\cdot 4 + 18 = 16\cdot27 + 18 = 18\cdot25. </cmath>
+
[[Category:Intermediate Combinatorics Problems]]
 
 
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{97.}</math>
 

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

See also

2011 AIME II (ProblemsAnswer KeyResources)
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
Invalid username
Login to AoPS