Question

Nueve delegados, tres de cada uno de tres países diferentes, eligen al azar sillas en una mesa redonda con capacidad para nueve personas. Sea $\frac{m}{n}$ la probabilidad de que cada delegado se siente junto a al menos un delegado de otro país, donde $m$ y $n$ son enteros positivos coprimos. Halla $m + n.$

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

Respuesta

Solución:

Solo importa el patrón de países en las nueve sillas, y los $\frac{9!}{3!\,3!\,3!} = 1680$ patrones son igualmente probables. La condición falla para algún delegado exactamente cuando sus dos vecinos son compatriotas, lo cual ocurre exactamente cuando los tres delegados de algún país ocupan tres sillas consecutivas. Sea $A_i$ el conjunto de patrones en los que los delegados del país $i$ son consecutivos.

Hay $9$ tríos de sillas consecutivas, así que $|A_i| = 9\binom{6}{3} = 180,$ al elegir cuáles $3$ de las $6$ sillas restantes van a uno de los otros países. Para dos países, después de colocar el primer bloque ( $9$ formas) las seis sillas restantes forman un arco que contiene $4$ tríos de sillas consecutivas, así que $|A_i \cap A_j| = 9 \cdot 4 = 36.$ Para los tres, el círculo debe dividirse en tres tríos consecutivos ( $3$ formas) asignados a los países en $3!$ órdenes: $|A_1 \cap A_2 \cap A_3| = 18.$ Por inclusión-exclusión, $\begin{aligned} |A_1 \cup A_2 \cup A_3| &= 3 \cdot 180 - 3 \cdot 36 \\ &\quad {}+ 18 = 450. \end{aligned}$

La probabilidad es $1 - \frac{450}{1680} = 1 - \frac{15}{56} = \frac{41}{56},$ así que $m + n = 41 + 56 = 97.$

Only the pattern of countries in the nine chairs matters, and all $\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 $A_i$ be the set of patterns in which country $i$ 's delegates are consecutive.

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

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

2011 AIME II Problema 12

Solución:

El Problema 12 en otros años