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 chairs under these conditions?
Problem 82
Pick one
Official solutions — 2
Solution 1
Let Alice be A, Bob be B, Carla be C, Derek be D, and Eric be E.
We can split this problem up into two cases:
A sits on an edge seat.
Since B and C can't sit next to A, that must mean either D or E sits next to A. After we pick either D or E, then either B or C must sit next to D/E. Then, we can arrange the two remaining people in two ways. Since there are two different edge seats that A can sit in, there are a total of .
A does not sit in an edge seat.
Still, the only two people that can sit next to A are either D or E, and there are two ways to permute them, and this also handles the restriction that D can't sit next to E. Then, there are two ways to arrange B and C, the remaining people. However, there are three initial seats that A can sit in, so there are seatings in this case.
Adding up all the seatings, we have .
Solution 2
Alice may sit in the center chair, in an end chair, or in a next-to-end chair. Suppose she sits in the center chair. The 2nd and 4th chairs (next to her) must be occupied by Derek and Eric, in either order, leaving the end chairs for Bob and Carla in either order; this yields ways to seat the group.
Next, suppose Alice sits in one of the end chairs. Then the chair beside her will be occupied by either Derek or Eric. The center chair must be occupied by Bob or Carla, leaving the last two people to fill the last two chairs in either order. ways to seat Alice times ways to fill the next chair times ways to fill the center chair times ways to fill the last two chairs yields ways to fill the chairs.
Finally, suppose Alice sits in the second or fourth chair. Then the chairs next to her must be occupied by Derek and Eric in either order, and the other two chairs must be occupied by Bob and Carla in either order. This yields ways to fill the chairs.
In total, there are ways to fill the chairs, so the answer is .