HMMT 二月 2003 · 团队赛 · 第 8 题
HMMT February 2003 — Team Round — Problem 8
题目详情
- (a) [15] Given a set A with n ≥ 1 elements, find the number of consistent 2- configurations of A of order 1 with exactly 1 cell. (b) [25] Given a set A with 10 elements, find the number of consistent 2-configurations of A of order 2 with exactly 1 cell. (c) [25] Given a set A with 10 elements, find the number of consistent 2-configurations of order 2 with exactly 2 cells.
解析
- (a) Given a set A with n ≥ 1 elements, find the number of consistent 2-configurations of A of order 1 with exactly 1 cell. Solution: There must be some pair { a, b } in the 2-configuration, since each element a ∈ A must belong to one pair. Since neither a nor b can now belong to any other pair, this must be the entire cell. Thus, there is 1 such 2-configuration when n = 2, and there are none when n 6 = 2. (b) Given a set A with 10 elements, find the number of consistent 2-configurations of A of order 2 with exactly 1 cell. Solution: Consider such a configuration; let { a , a } be an element of it. Then a be- 1 2 2 longs to exactly one other pair; call it { a , a } . Likewise, a belongs to exactly one other 2 3 3 pair { a , a } , and so forth; since we have finitely many elements, we must eventually 3 4 reach some pair { a , a } that revisits a previously used element ( m > k ). But this is m k only possible if k = 1, since each other a with k < m is already used in two pairs. Now, k { a , . . . , a } constitutes a complete cell, because none of these elements can be used 1 m in any more pairs, so m = 10. Thus, every consistent 2-configuration of order 2 with exactly 1 cell gives rise to a permutation a , . . . , a of the elements of A , and conversely, 1 10 each such permutation gives us a 2-configuration {{ a , a } , . . . , { a , a } , { a , a }} . In 1 2 9 10 10 1 fact, each configuration corresponds to exactly 20 permutations, depending which of the 5 10 elements of the 2-configuration we choose as { a , a } and which of these two elements 1 2 of A we in turn choose to designate as a (as opposed to a ). Therefore, the number of 1 2 such 2-configurations is 10! / 20 = 9! / 2 = 181440. (More generally, the same argument shows that, when A has n ≥ 3 elements, there are ( n − 1)! / 2 such 2-configurations.) (c) Given a set A with 10 elements, find the number of consistent 2-configurations of order 2 with exactly 2 cells. Solution: Notice that if we look only at the pairs contained within any fixed cell, each element of that cell still lies in 2 such pairs, since all the pairs it belongs to are contained within that cell. Thus we have an induced consistent 2-configuration of order 2 of each cell. Now, each cell must have at least 3 elements for the configuration to be 2-consistent. So we can have either two 5-element cells, a 4-element cell and a 6-element cell, or a 3-element cell and a 7-element cell. If there are two 5-element cells, we can choose ( ) 10 the members of the first cell in ways, and then (by the reasoning in the previous 5 problem) we have 4! / 2 ways to build a consistent 2-configuration of order 2 of each cell. However, choosing 5 elements for the first cell is equivalent to choosing the other 5 elements for the first cell, since the two cells are indistinguishable; thus, we have ( ) 10 2 overcounted by a factor of 2. So we have · (4! / 2) / 2 = 252 · 144 / 2 = 18144 ways to 5 form our configuration if we require it to have two cells of 5 elements each. ( ) 10 If we have one 4-element cell and one 6-element cell, then there are ways 4 to determine which 4 elements go in the smaller cell, and then 3! / 2 ways and 5! / 2 ways, respectively, to construct the 2-configurations of the two cells, for a total of ( ) 10 · (3! / 2) · (5! / 2) = 210 · 3 · 60 = 37800 configurations (no overcounting here), and 4 ( ) 10 by similar reasoning, we have · (2! / 2) · (6! / 2) = 120 · 1 · 360 = 43200 configurations 3 with one 3-element cell and one 7-element cell. Thus, altogether, we have a total of 18144 + 37800 + 43200 = 99144 consistent 2-configurations of order 2 with exactly 2 cells.