Question

Cuatro embajadores y un asesor para cada uno de ellos deben sentarse en una mesa redonda con $12$ sillas numeradas en orden de $1$ a $12.$ Cada embajador debe sentarse en una silla de número par. Cada asesor debe sentarse en una silla adyacente a su embajador. Hay $N$ maneras de sentar a las $8$ personas en la mesa bajo estas condiciones. Halle el residuo cuando $N$ se divide entre $1000.$

Four ambassadors and one advisor for each of them are to be seated at a round table with $12$ chairs numbered in order $1$ to $12.$ Each ambassador must sit in an even-numbered chair. Each advisor must sit in a chair adjacent to his or her ambassador. There are $N$ ways for the $8$ people to be seated at the table under these conditions. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Las seis sillas pares forman un ciclo (la silla $12$ es adyacente a la silla $1$ ), y cada silla impar está entre dos sillas pares consecutivas. Los embajadores ocupan $4$ de las $6$ sillas pares, y cada asesor debe tomar una de las dos sillas impares que flanquean a su embajador, con todas las elecciones distintas. Para un bloque maximal de $k$ sillas pares ocupadas consecutivas, los $k$ ocupantes eligen entre las $k + 1$ sillas impares que tocan el bloque; registrando cada elección como izquierda o derecha, ocurre un conflicto exactamente cuando alguien elige derecha y su vecino elige izquierda, así que los patrones válidos son las cadenas de $L$ seguidas de $R$ : $k + 1$ de ellos.

Ahora distinga casos según las dos sillas pares vacías entre las seis posiciones. Si son adyacentes ( $6$ maneras), las sillas ocupadas forman un bloque de $4,$ dando $5$ patrones. Si están separadas por una silla ( $6$ maneras), los bloques tienen tamaños $1$ y $3,$ dando $2 \cdot 4 = 8$ patrones. Si son opuestas ( $3$ maneras), los bloques tienen tamaños $2$ y $2,$ dando $3 \cdot 3 = 9$ patrones. El número de configuraciones de asientos es $6 \cdot 5 + 6 \cdot 8 + 3 \cdot 9 = 105.$

Finalmente, los cuatro pares embajador-asesor pueden asignarse a las cuatro sillas pares elegidas de $4! = 24$ maneras, así que $N = 105 \cdot 24 = 2520,$ y el residuo módulo $1000$ es $520.$

The six even chairs form a cycle (chair $12$ is adjacent to chair $1$ ), and each odd chair lies between two consecutive even chairs. The ambassadors occupy $4$ of the $6$ even chairs, and each advisor must take one of the two odd chairs flanking their ambassador, with all choices distinct. For a maximal block of $k$ consecutive occupied even chairs, the $k$ occupants choose among the $k + 1$ odd chairs touching the block; recording each choice as left or right, a conflict occurs exactly when someone picks right and their neighbor picks left, so the valid patterns are the strings of $L$ s followed by $R$ s: $k + 1$ of them.

Now case on the two empty even chairs among the six positions. If they are adjacent ( $6$ ways), the occupied chairs form one block of $4,$ giving $5$ patterns. If they are separated by one chair ( $6$ ways), the blocks have sizes $1$ and $3,$ giving $2 \cdot 4 = 8$ patterns. If they are opposite ( $3$ ways), the blocks have sizes $2$ and $2,$ giving $3 \cdot 3 = 9$ patterns. The number of seat configurations is $6 \cdot 5 + 6 \cdot 8 + 3 \cdot 9 = 105.$

Finally, the four ambassador-advisor pairs can be assigned to the four chosen even chairs in $4! = 24$ ways, so $N = 105 \cdot 24 = 2520,$ and the remainder modulo $1000$ is $520.$

2019 AIME II Problema 5

Solución:

El Problema 5 en otros años