Problem:
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:
The number of ways that the nine chairs can be assigned to countries is given by the multinomial coefficient . The requested probability is minus the probability that all three delegates from at least one country sit next to each other so that the middle delegate is surrounded by delegates from the same country. Let , and be the sets of seat assignments where the three delegates from the first, second, and third countries, respectively, sit in three adjacent chairs. The desired probability is then . The Inclusion/Exclusion Principle along with the symmetry of the three sets , and imply that . To choose an element of , choose one of the nine chairs for the rightmost of the delegates from the first country to sit. That determines the occupants of three adjacent chairs. Then choose the countries assigned to the remaining six chairs. This shows that . To choose an element of , choose one of nine chairs for the rightmost of the delegates from the first country to sit. Then choose one of the four possible chairs for the rightmost of the delegates from the second country to sit. This shows that . To choose an element of , choose one of nine chairs for the rightmost of the delegates from the first country to sit. This leaves six adjacent chairs to seat the two delegations from the other two countries which can be accomplished in two ways. This shows that . Thus . The requested probability is then , and the requested sum is .
The problems on this page are the property of the MAA's American Mathematics Competitions