2015 AMC 10A Problem 22

All $2^8 = 256$ head/tail patterns are equally likely, so we count the patterns in which no two neighbors around the circle both stand.

First a lemma for people in a row. Let $a_n$ be the number of ways to choose who stands among $n$ people in a line with no two neighbors standing. Look at the last person: if seated, the first $n-1$ people can be anything valid ($a_{n-1}$ ways); if standing, the previous person must sit and the first $n-2$ are free ($a_{n-2}$ ways). So $a_n = a_{n-1} + a_{n-2}$ with $a_1 = 2$, $a_2 = 3$, giving
$$a_3 = 5,\quad a_4 = 8,\quad a_5 = 13,\quad a_6 = 21,\quad a_7 = 34.$$

Now break the circle at person $1$.

• Person $1$ sits. Persons $2$ through $8$ form a row of $7$ with no wrap-around constraint left: $a_7 = 34$ ways.
• Person $1$ stands. Then persons $2$ and $8$ must sit, and persons $3$ through $7$ form a free row of $5$: $a_5 = 13$ ways.

Total $34 + 13 = 47$ patterns, so the probability is
$$\frac{47}{256}.$$

The answer is $\boxed{\textbf{(A)}\ \dfrac{47}{256}}$.

"No two adjacent" in a row is the classic Fibonacci-type recursion: decide the last element and the problem shrinks by one or two. A circle adds a single wrap-around condition, and fixing one position removes it, leaving one or two row problems. The resulting count for a cycle of $n$ is the Lucas number $a_{n-1} + a_{n-3}$, here $34 + 13$.

Casework on how many people stand. With $k = 0$: $1$ way. $k = 1$: $8$. $k = 2$: $\binom82 - 8 = 20$ (remove the $8$ adjacent pairs). $k = 3$: $\binom83 - 8\cdot 4 - 8 = 16$ (remove triples containing exactly one adjacent pair and the $8$ consecutive triples). $k = 4$: only the two alternating patterns. Sum $1 + 8 + 20 + 16 + 2 = 47$.

• Treating the eight seats as a row ($55$ arrangements) and ignoring that the first and last people are also neighbors.
• Starting the recursion with $a_1 = 1$, $a_2 = 2$ instead of $2$ and $3$, which shifts every count by one Fibonacci term.
• In the casework method, miscounting the three-person case (for instance forgetting the $8$ consecutive triples) and landing on $49$ or $51$.