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?
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
Alice's neighbors must be Derek and Eric; place Alice first, and only when she sits at an end can Derek and Eric become adjacent, which costs a few arrangements.
Solution
Alice is the most restricted person: whoever sits beside her must be Derek or Eric. Split by Alice's chair, numbering the chairs to .
Alice in chair (middle). Chairs and hold Derek and Eric in some order ( ways). They are not adjacent to each other, so no conflict. Bob and Carla take chairs and ( ways). Total .
Alice in chair . Chairs and hold Derek and Eric ( ways); they are separated by Alice. Bob and Carla fill chairs and ( ways). Total . By left-right symmetry, Alice in chair also gives .
Alice in chair . Chair is Derek or Eric ( ways). Say Derek; then Eric cannot sit in chair . Chairs hold Bob, Carla and Eric with Eric in chair or ( ways) and Bob, Carla in the remaining two chairs ( ways). Total . By symmetry, Alice in chair also gives .
Adding: .
The answer is .
Why this works
When one person is forbidden from two of the four others, fix that person first: her neighbors are forced to come from a two-person pool, which collapses the count. Symmetry (reversing the row) halves the casework. The Derek-Eric rule only bites when Derek and Eric can end up side by side, which happens only when Alice has a single neighbor.
The trap
Using inclusion-exclusion on three forbidden adjacencies and losing track of the overlaps, or forgetting the Derek-Eric restriction when Alice is at an end.
Common mistakes
- Using inclusion-exclusion on three forbidden adjacencies and losing track of the overlaps, or forgetting the Derek-Eric restriction when Alice is at an end.
- Counting the end cases as each (ignoring Eric's restriction), which gives .
Techniques
Split into exhaustive cases and handle each · Exploit symmetry to reduce work or pair up objects