HMMT 十一月 2009 · 冲刺赛 · 第 28 题
HMMT November 2009 — Guts Round — Problem 28
题目详情
- [ 17 ] Six men and their wives are sitting at a round table with 12 seats. These men and women are very jealous — no man will allow his wife to sit next to any man except for himself, and no woman will allow her husband to sit next to any woman except for herself. In how many distinct ways can these 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating are considered distinct.)
解析
- [ 17 ] Six men and their wives are sitting at a round table with 12 seats. These men and women are very jealous — no man will allow his wife to sit next to any man except for himself, and no woman will allow her husband to sit next to any woman except for herself. In how many distinct ways can these 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating are considered distinct.) Answer: 288000 Think of this problem in terms of “blocks” of men and women, that is, groups of men and women sitting together. Each block must contain at least two people; otherwise you have a man 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 two women 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 deter- mined 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 of men 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.