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

英文解析

9. (a) Show that if every cell of a 2-configuration of a finite set A is m -separable, thenthe whole 2-configuration is m -separable.
   Solution: Let C be a 2-configuration of A with cells A , . . . , A , so that there is
   1 nno element of C with one element in A and another in A for i 6 = j . Suppose thati jeach cell is m -separable, so that for each i , 1 ≤ i ≤ n , there is a labeling functionf : A → { 1 , . . . , m } such that no two elements in the same pair of C are assigned thei isame number. Then, by combining, we get a function f on all of A whose restrictionto A is f for each i . By the definition of f , within each A there is no element of Ci i i iboth of whose elements are mapped to the same integer; and as above, we know that there are no elements of C not contained inside any A . Thus, C is m -separable, by theiexistence of f .
   (b) Show that any barren 2-configuration of a finite set A is 2-separable.
   Solution: It is sufficient to show each cell is 2-separable, by part (a). A barren 2 configuration by definition cannot have any cycles (i.e. subsets { a , . . . , a } , n ≥ 2,
   0 nwhere each { a , a } and { a , a } all belong to the 2-configuration). For any twoi i +1 n 0
   distinct elements a, b of A in the same cell of a 2-configuration C , define the distancebetween them to be the smallest n such that there exists a sequence a = a , a , . . . , a =
   0 1 nb with { a , a } , { a , a } , . . . , { a , a } all belonging to the 2-configuration. Notice that 6
   0 1 1 2 n − 1 nthe terms of this sequence are all distinct: if a = a for i < j , then we have the shorteri jsequence a , a , . . . , a , a , . . . , a , contradicting minimality.
   0 1 i j +1 n
   Now let C be a barren 2-configuration of A . Pick any element a of A ; label it andall elements at even distance from it with the integer 1, and label all elements at odddistance from it with the integer 2. We claim no two different elements with the samelabel appear in the same element of C . Otherwise, let b and c be such elements, and
   ′ ′ ′
   let a = a , a , . . . , a = b and a = a , a , . . . , a = c be the corresponding minimal
   0 1 n
   0 1 m
   ′ ′ ′
   sequences. Consider the largest p such that a ∈ { a , . . . , a } ; write a = a . We claimp p
   0 m q
   ′ ′
   the set { a , a , . . . , a , a , . . . , a } is then a cycle. It is straightforward to checkn n − 1 pq +1 mthat all its elements are distinct; the only issue is whether it has at least 3 elements. If
   ′
   not, we would have a = a or a . Assume that a = a ⇒ p = n ⇒ q = m − 1 (byp n p n
   ′mminimality of our sequence ( a )), but this means that m = n + 1, so the distances of band c from a have opposite parities, contradicting the assumption that they have thei
   ′ ′
   same label. The case a = a is similar. Thus, our set really does have at least threeq melements, and it is a cycle. But since A is barren, it contains no cycles, and we have acontradiction.
   Thus, after all, no two elements with the same label appear in the same pair of C ,
   so the cell containing a is 2-separable, and we are done.