2008 AMC 10B Problem 21
Ten chairs are evenly spaced around a round table and numbered clockwise from through . Five married couples are to sit in the chairs with men and women alternating, and no one is to sit either next to or across from his/her spouse. How many seating arrangements are possible?
Show solution without answering
Key insight
Seat the men first. Each wife then has exactly two allowed chairs, and one wife's choice forces all the others, so the wives can sit in just 2 ways.
Solution
The chairs are numbered, so turning the whole table gives a different arrangement. Seat the men first, then see where the wives are allowed to go.
Seating the men.
- Men and women alternate, so the men sit either in all the odd chairs or in all the even chairs: choices.
- The men can be placed in their chairs in ways.
Seating the wives. Suppose the men are in chairs (the even case works the same way). Call the wife of the man in chair "wife ".
- Wife cannot sit in the two chairs next to chair , or in the chair straight across, which is chairs away. Of the five even chairs, that rules out three, leaving two:
| Wife | Chairs ruled out | Chairs allowed |
|---|---|---|
| wife | ||
| wife | ||
| wife | ||
| wife | ||
| wife |
- Try wife in chair . Chair is taken, so wife must take . Then wife must take , wife must take , and wife must take . Every step is forced: one seating.
- Try wife in chair . Then wife takes , wife takes , wife takes , and wife takes . Again forced: one seating.
- So the wives can be seated in exactly ways, however the men sat.
Total. .
The answer is .
Why this works
Seat one group first, then list where each person in the other group may go. Here every wife has two chairs and every chair is wanted by two wives, so the choices link together in one loop. Once the first wife picks, everyone else is forced, which gives only two ways, not . The men's order does not matter, because the allowed chairs depend only on chair numbers.
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Because the chairs are numbered, rotations count as different arrangements.
Men and women alternate, so the men occupy either all the odd chairs or all the even chairs: choices. The five men can then be seated in ways.
Now fix the men in chairs (the even case is identical). The wife of the man in chair may not sit in chairs , or (across), all of which are even, so she has legal chairs:
If takes chair , then must take , so takes , so takes , so takes . If takes chair , then takes , takes , takes , takes . Every step is forced, so there are exactly ways to seat the wives.
Total: .
The answer is .
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)
- Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
- Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.