Problem:
While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.
Solution:
We count seatings of people where no originally adjacent pair remains adjacent.
The number of total permutations is .
Subtract seatings with one adjacent pair: .
Add seatings with two adjacent pairs: overlapping (4 cases): ; disjoint (6 cases): .
Subtract seatings with three adjacent pairs: consecutive (3 cases): ; two consecutive, one disjoint (6 cases): ; all disjoint (1 case): .
Add seatings with four adjacent pairs: all consecutive (2 cases): ; two consecutive, two disjoint (3 cases): .
Subtract seating with all five pairs adjacent (1 case): .
Our final count is:
The problems on this page are the property of the MAA's American Mathematics Competitions