AMC 10 Step by Step

2008 AMC 10B Problem 21

P21-25~6 minPrint

Ten chairs are evenly spaced around a round table and numbered clockwise from 11 through 1010 . 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?

Log in to save your progress.
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.

  1. Men and women alternate, so the men sit either in all the odd chairs or in all the even chairs: 22 choices.
  2. The 55 men can be placed in their 55 chairs in 5×4×3×2×1=1205 \times 4 \times 3 \times 2 \times 1 = 120 ways.

Seating the wives. Suppose the men are in chairs 1,3,5,7,91, 3, 5, 7, 9 (the even case works the same way). Call the wife of the man in chair kk "wife kk".

  1. Wife kk cannot sit in the two chairs next to chair kk, or in the chair straight across, which is 55 chairs away. Of the five even chairs, that rules out three, leaving two:
WifeChairs ruled outChairs allowed
wife 1110,2,610, 2, 64,84, 8
wife 332,4,82, 4, 86,106, 10
wife 554,6,104, 6, 102,82, 8
wife 776,8,26, 8, 24,104, 10
wife 998,10,48, 10, 42,62, 6
  1. Try wife 11 in chair 44. Chair 44 is taken, so wife 77 must take 1010. Then wife 33 must take 66, wife 99 must take 22, and wife 55 must take 88. Every step is forced: one seating.
  2. Try wife 11 in chair 88. Then wife 55 takes 22, wife 99 takes 66, wife 33 takes 1010, and wife 77 takes 44. Again forced: one seating.
  3. So the wives can be seated in exactly 22 ways, however the men sat.

Total. 2×120×2=4802 \times 120 \times 2 = 480.

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

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 2×2×2×2×22 \times 2 \times 2 \times 2 \times 2. 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: 22 choices. The five men can then be seated in 5!=1205! = 120 ways.

Now fix the men in chairs 1,3,5,7,91, 3, 5, 7, 9 (the even case is identical). The wife of the man in chair kk may not sit in chairs k−1k-1, k+1k+1 or k+5k+5 (across), all of which are even, so she has 5−3=25 - 3 = 2 legal chairs:
W1:{4,8},W3:{6,10},W5:{2,8},W7:{4,10},W9:{2,6}.W_1: \{4, 8\},\quad W_3: \{6, 10\},\quad W_5: \{2, 8\},\quad W_7: \{4, 10\},\quad W_9: \{2, 6\}.
If W1W_1 takes chair 44, then W7W_7 must take 1010, so W3W_3 takes 66, so W9W_9 takes 22, so W5W_5 takes 88. If W1W_1 takes chair 88, then W5W_5 takes 22, W9W_9 takes 66, W3W_3 takes 1010, W7W_7 takes 44. Every step is forced, so there are exactly 22 ways to seat the wives.

Total: 2⋅120⋅2=4802 \cdot 120 \cdot 2 = 480.

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

Review in the AoPS books

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.