HMMT 二月 2003 · 团队赛 · 第 8 题

英文解析

8. (a) Given a set A with n ≥ 1 elements, find the number of consistent 2-configurationsof A of order 1 with exactly 1 cell.
   Solution: There must be some pair { a, b } in the 2-configuration, since each elementa ∈ 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, andthere 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 ism konly possible if k = 1, since each other a with k < m is already used in two pairs. Now,
   { a , . . . , a } constitutes a complete cell, because none of these elements can be usedk
   1 min any more pairs, so m = 10. Thus, every consistent 2-configuration of order 2 withexactly 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
   10 elements of the 2-configuration we choose as { a , a } and which of these two elements 5
   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 argumentshows 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 oforder 2 with exactly 2 cells.
   Solution: Notice that if we look only at the pairs contained within any fixed cell, eachelement of that cell still lies in 2 such pairs, since all the pairs it belongs to are containedwithin that cell. Thus we have an induced consistent 2-configuration of order 2 of eachcell.
   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
   ( )
   the members of the first cell in ways, and then (by the reasoning in the previous 10
   problem) we have 4! / 2 ways to build a consistent 2-configuration of order 2 of each 5
   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
   ( )
   overcounted by a factor of 2. So we have · (4! / 2) / 2 = 252 · 144 / 2 = 18144 ways to 210
   form our configuration if we require it to have two cells of 5 elements each.5
   ( )
   If we have one 4-element cell and one 6-element cell, then there are ways 10
   to determine which 4 elements go in the smaller cell, and then 3! / 2 ways and 5! / 24
   ways, respectively, to construct the 2-configurations of the two cells, for a total of
   ( )
   · (3! / 2) · (5! / 2) = 210 · 3 · 60 = 37800 configurations (no overcounting here), and 10
   ( )4
   by similar reasoning, we have · (2! / 2) · (6! / 2) = 120 · 1 · 360 = 43200 configurations 10
   with one 3-element cell and one 7-element cell. Thus, altogether, we have a total of 3
   18144 + 37800 + 43200 = 99144 consistent 2-configurations of order 2 with exactly 2
   cells.