AMC 12 Mock Exam 2 Problem 24

Without restriction, the number of ways to split $2m$ people into pairs is $(2m-1)(2m-3)\cdots1$, which is $105$ for $m=4$, $15$ for $m=3$, $3$ for $m=2$, and $1$ for $m\le1$.

There are $8$ adjacent pairs (seat $i$ with seat $i+1$, cyclically). For a set $S$ of $k$ adjacent pairs that are pairwise disjoint, the number of pairings containing all of $S$ is the number of ways to pair the remaining $8-2k$ people. Let $m_k$ be the number of such sets $S$:

• $m_1=8$.
• $m_2=\binom82-8=20$ (all pairs of adjacent pairs, minus the $8$ that share a person).
• $m_3=16$: three disjoint adjacent pairs cover six seats and leave two seats uncovered. The six covered seats form two runs between the uncovered seats, each of even length, so the runs have lengths $0$ and $6$ (the uncovered seats are neighbors: $8$ choices) or $2$ and $4$ (the uncovered seats are three apart: $8$ choices). Each choice is covered by adjacent pairs in exactly one way, so $m_3=16$.
• $m_4=2$ (alternate edges of the $8$-cycle).

By inclusion–exclusion, the number of pairings with no adjacent pair is $$105-8\cdot15+20\cdot3-16\cdot1+2\cdot1=105-120+60-16+2=\boxed{31}.$$