Question

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.

Answer

Solution:

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 Problem 9

Solution:

Problem 9 in Other Years