2017 AMC 10A Problem 19

P16-20~5 minPrint

Arrangements with Restrictions Split into exhaustive cases and handle each Exploit symmetry to reduce work or pair up objects

Alice refuses to sit next to either Bob or Carla. Derek refuses to sit next to Eric. How many ways are there for the five of them to sit in a row of 5 chairs under these conditions?

Show solution without answering

Key insight

Alice can sit only next to Derek or Eric, so place Alice first. Derek and Eric can end up side by side only when Alice sits at an end.

Solution

Alice has the strictest rule: her neighbors must come from Derek and Eric. So place Alice first and split by her chair. Number the chairs $1$ to $5$ from left to right.

Alice in chair $3$ (the middle). Her neighbors are chairs $2$ and $4$ , so Derek and Eric sit there, in either order: $2$ ways. They are not next to each other, so their rule is fine. Bob and Carla take chairs $1$ and $5$ : $2$ ways. Total $2 \times 2 = 4$ .
Alice in chair $2$ . Her neighbors are chairs $1$ and $3$ , so Derek and Eric go there: $2$ ways. Alice sits between them, so they are not neighbors. Bob and Carla take chairs $4$ and $5$ : $2$ ways. Total $4$ .
Alice in chair $4$ . This is chair $2$ seen in a mirror, so again $4$ .
Alice in chair $1$ . She has only one neighbor, chair $2$ , which must be Derek or Eric: $2$ ways. Say Derek sits there. Now Eric must not sit in chair $3$ (next to Derek), so Eric takes chair $4$ or $5$ : $2$ ways. Bob and Carla fill the other two chairs: $2$ ways. Total $2 \times 2 \times 2 = 8$ .
Alice in chair $5$ . The mirror image of chair $1$ , so again $8$ .
Add: $4 + 4 + 4 + 8 + 8 = 28$ .

The answer is $\boxed{\textbf{(C)}\ 28}$ .

Why this works

In seating problems, place the pickiest person first; that forces her neighbors and shrinks the count quickly. Mirror symmetry (chair $2$ matches chair $4$ , chair $1$ matches chair $5$ ) cuts the work nearly in half. Keep checking the second rule in every case: here it matters only when Alice's single neighbor leaves room for Derek and Eric to sit together.

Concise solution

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

Alice is the most restricted person: whoever sits beside her must be Derek or Eric. Split by Alice's chair, numbering the chairs $1$ to $5$ .

Alice in chair $3$ (middle). Chairs $2$ and $4$ hold Derek and Eric in some order ( $2$ ways). They are not adjacent to each other, so no conflict. Bob and Carla take chairs $1$ and $5$ ( $2$ ways). Total $2 \cdot 2 = 4$ .

Alice in chair $2$ . Chairs $1$ and $3$ hold Derek and Eric ( $2$ ways); they are separated by Alice. Bob and Carla fill chairs $4$ and $5$ ( $2$ ways). Total $4$ . By left-right symmetry, Alice in chair $4$ also gives $4$ .

Alice in chair $1$ . Chair $2$ is Derek or Eric ( $2$ ways). Say Derek; then Eric cannot sit in chair $3$ . Chairs $3, 4, 5$ hold Bob, Carla and Eric with Eric in chair $4$ or $5$ ( $2$ ways) and Bob, Carla in the remaining two chairs ( $2$ ways). Total $2 \cdot 2 \cdot 2 = 8$ . By symmetry, Alice in chair $5$ also gives $8$ .

Adding: $4 + 4 + 4 + 8 + 8 = 28$ .

The answer is $\boxed{\textbf{(C)}\ 28}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)
Prealgebra, Chapter 14: Counting (§14.3)