2015 AMC 10A Problem 22

P21-25~6 minPrint

Recursive Counting Arrangements with Restrictions Basic Probability Split into exhaustive cases and handle each Define states/recurrence and iterate

Eight people are sitting around a circular table, each holding a fair coin. All eight people flip their coins and those who flip heads stand while those who flip tails remain seated. What is the probability that no two adjacent people will stand?

Show solution without answering

Key insight

Rows with no two neighbors standing follow 2, 3, 5, 8, 13, 21, 34. Open the circle at one person: 34 ways if they sit, 13 if they stand.

Solution

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:

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$a_n$	$2$	$3$	$5$	$8$	$13$	$21$	$34$

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.

Person 1 sits. Then no one can clash with person $1$ . People $2$ through $8$ form a row of $7$ : $a_7 = 34$ ways.
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.
Total good patterns: $34 + 13 = 47$ .

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

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

Why this works

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.

Alternative approach

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

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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

Review in the AoPS books

Intermediate Counting & Probability, Chapter 10: Recursion (§10.2, §10.3)
Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Intermediate Counting & Probability, Chapter 9: Fibonacci Numbers