HMMT 十一月 2009 · 冲刺赛 · 第 28 题

英文解析

28. [ 17 ] Six men and their wives are sitting at a round table with 12 seats. These men and women arevery jealous — no man will allow his wife to sit next to any man except for himself, and no womanwill allow her husband to sit next to any woman except for herself. In how many distinct ways canthese 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating areconsidered distinct.)
    Answer: 288000 Think of this problem in terms of “blocks” of men and women, that is, groups ofmen and women sitting together. Each block must contain at least two people; otherwise you have aman sitting next to two women (or vice-versa).
    We will define the notation [ a , b , a , b , . . . ] to mean a seating arrangement consisting of, going in
    1 1 2 2
    order, a men, b women, a men, b women, and so on.
    1 1 2 2
    Split the problem into three cases, each based on the number of blocks of men and women:
    Case 1: One block of each, [6 , 6].
    There are 12 ways to choose the seats where the men sit, and 6! ways to arrange those men. The twowomen on either side of the men are uniquely determined by the men they sit next to. There are 4!
    ways to arrange the other four women. This gives 6! · 288 ways.
    Case 2: Two blocks of each.
    The arrangement is [ a, b, c, d ], where a + c = b + d = 6. There are five distinct block schematics:
    [2 , 2 , 4 , 4], [2 , 3 , 4 , 3], [2 , 4 , 4 , 2], [3 , 2 , 3 , 4], and [3 , 3 , 3 , 3]. (The others are rotations of one of the above.)
    For each of these, there are 6! ways to arrange the men. In addition, four women are uniquely determined because they sit next to a man. There are 2 ways to arrange the other two women. Each of the first four possible block schematics gives 12 distinct rotations, while the fifth one gives 6. This gives
    6!(2)(12 + 12 + 12 + 12 + 6) = 6! · 108 ways.
    Case 3: Three blocks of each, [2 , 2 , 2 , 2 , 2 , 2].
    There are 4 ways to choose where the men sit and 6! ways to arrange those men. Each placement ofmen will uniquely determine the placement of each women. This gives 6! · 4 ways.
    Then we have a grand total of 6! · (288 + 108 + 4) = 6! · 400 = 288000 seating arrangements.