2011 AIME II Problem 12

Below is the professionally curated solution for Problem 12 of the 2011 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2011 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:circular arrangementscomplementary countinginclusion-exclusion

Difficulty rating: 3060

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 mn,\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+n.m + n.

Solution:

Only the pattern of countries in the nine chairs matters, and all 9!3!3!3!=1680\frac{9!}{3!\,3!\,3!} = 1680 patterns are equally likely. The condition fails for some delegate exactly when both of his neighbors are compatriots, which happens exactly when some country's three delegates occupy three consecutive chairs. Let AiA_i be the set of patterns in which country ii's delegates are consecutive.

There are 99 triples of consecutive chairs, so Ai=9(63)=180,|A_i| = 9\binom{6}{3} = 180, choosing which 33 of the remaining 66 chairs go to one of the other countries. For two countries, after placing the first block (99 ways) the remaining six chairs form an arc containing 44 triples of consecutive chairs, so AiAj=94=36.|A_i \cap A_j| = 9 \cdot 4 = 36. For all three, the circle must split into three consecutive triples (33 ways) assigned to the countries in 3!3! orders: A1A2A3=18.|A_1 \cap A_2 \cap A_3| = 18. By inclusion-exclusion, A1A2A3=3180336+18=450.|A_1 \cup A_2 \cup A_3| = 3 \cdot 180 - 3 \cdot 36 + 18 = 450.

The probability is 14501680=11556=4156,1 - \frac{450}{1680} = 1 - \frac{15}{56} = \frac{41}{56}, so m+n=41+56=97.m + n = 41 + 56 = 97.

← Problem 11Full ExamProblem 13

Problem 12 in Other Years