2015 AMC 10A Problem 22

Each of the $8$ coins lands $2$ ways, so there are $2^8 = 256$ equally likely stand/sit patterns. We count the good ones: no two neighbors both standing.

Step 1: people in a straight row. Let $a_n$ be the number of good patterns for $n$ people in a row.

1. Small rows by hand. With $1$ person: sit or stand, so $a_1 = 2$. With $2$ people: SS, SU, US are fine but UU is not (S = sit, U = up), so $a_2 = 3$.
2. For a longer row, look at the last person.
- If the last person sits, the others can be any good pattern of $n - 1$ people: $a_{n-1}$ ways.
- If the last person stands, the one before must sit, and the first $n - 2$ people can be any good pattern: $a_{n-2}$ ways.

So each count is the sum of the two before it: $a_n = a_{n-1} + a_{n-2}$.
3. Build the list:

Step 2: the circle. A circle is harder only because person $8$ and person $1$ are neighbors. Decide about person $1$ first and the circle opens into a row.

1. Person 1 sits. Then no one can clash with person $1$. People $2$ through $8$ form a row of $7$: $a_7 = 34$ ways.
2. Person 1 stands. Then both neighbors, persons $2$ and $8$, must sit. People $3$ through $7$ form a row of $5$ with no other limits: $a_5 = 13$ ways.
3. Total good patterns: $34 + 13 = 47$.

The probability is $\frac{47}{256}$.

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

For "no two neighbors" in a row, deciding the last spot shrinks the problem by one or two people, which gives the add-the-last-two pattern (the Fibonacci numbers). A circle has just one extra neighbor pair, where it closes up. Choosing the first person's state removes that extra pair and leaves ordinary rows.

Count by how many people stand.

• $0$ standing: $1$ way.
• $1$ standing: $8$ ways.
• $2$ standing: there are $\frac{8 \times 7}{2} = 28$ pairs, and $8$ of them are neighbors, so $20$.
• $3$ standing: there are $56$ groups of three. Remove the $8$ groups of three in a row. Remove also the groups with exactly one neighbor pair: $8$ neighbor pairs, each with $4$ seats for the third person that touch neither of them, so $32$. That leaves $56 - 8 - 32 = 16$.
• $4$ standing: only every other seat, which can be done $2$ ways.
• $5$ or more: impossible around $8$ seats.

Total: $1 + 8 + 20 + 16 + 2 = 47$.

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}}$.