Question

Mientras veían un espectáculo, Ayako, Billy, Carlos, Dahlia, Ehuang y Frank se sentaron en ese orden en una fila de seis sillas. Durante el descanso, fueron a la cocina por un refrigerio. Cuando regresaron, se sentaron en esas seis sillas de tal manera que si dos de ellos se sentaban uno al lado del otro antes del descanso, entonces no se sentaban uno al lado del otro después del descanso. Halle el número de posibles órdenes de asientos que pudieron haber elegido después del descanso.

While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.

Respuesta

Solución:

Numere a los amigos del $1$ al $6$ en el orden original de asientos; contamos los ordenamientos de $1, \ldots, 6$ en los que no hay dos enteros consecutivos adyacentes. Apliquemos inclusión-exclusión sobre cuáles de los cinco pares $\{i, i+1\}$ se ven forzados a sentarse juntos. Si un conjunto elegido de $k$ pares forma $r$ rachas maximales de enteros consecutivos, pegar cada racha en un bloque (que se puede ordenar de forma ascendente o descendente) da $2^r (6 - k)!$ disposiciones que contienen todas las adyacencias elegidas.

Contando según $k:$ para $k = 0,$ $720.$ Para $k = 1,$ cinco conjuntos, cada uno $2 \cdot 120,$ en total $1200.$ Para $k = 2,$ cuatro conjuntos forman una racha $(2 \cdot 24)$ y seis forman dos rachas $(4 \cdot 24),$ en total $768.$ Para $k = 3,$ tres conjuntos forman una racha $(2 \cdot 6),$ seis forman dos rachas $(4 \cdot 6),$ uno forma tres rachas $(8 \cdot 6),$ en total $228.$ Para $k = 4,$ dos conjuntos forman una racha $(2 \cdot 2)$ y tres forman dos rachas $(4 \cdot 2),$ en total $32.$ Para $k = 5,$ un conjunto, en total $2.$

El conteo es $720 - 1200 + 768$ $- 228 + 32 - 2 = 90.$

Number the friends $1$ through $6$ in original seating order; we count orderings of $1, \ldots, 6$ in which no two consecutive integers are adjacent. Apply inclusion-exclusion over which of the five pairs $\{i, i+1\}$ are forced to sit together. If a chosen set of $k$ pairs forms $r$ maximal runs of consecutive integers, gluing each run into a block (orderable ascending or descending) gives $2^r (6 - k)!$ seatings containing all chosen adjacencies.

Tallying by $k:$ for $k = 0,$ $720.$ For $k = 1,$ five sets, each $2 \cdot 120,$ total $1200.$ For $k = 2,$ four sets form one run $(2 \cdot 24)$ and six form two runs $(4 \cdot 24),$ total $768.$ For $k = 3,$ three sets form one run $(2 \cdot 6),$ six form two runs $(4 \cdot 6),$ one forms three runs $(8 \cdot 6),$ total $228.$ For $k = 4,$ two sets form one run $(2 \cdot 2)$ and three form two runs $(4 \cdot 2),$ total $32.$ For $k = 5,$ one set, total $2.$

The count is $720 - 1200 + 768$ $- 228 + 32 - 2 = 90.$

2020 AIME II Problema 9

Solución:

El Problema 9 en otros años