HMMT 二月 2003 · 团队赛 · 第 9 题
HMMT February 2003 — Team Round — Problem 9
题目详情
- (a) [15] Show that if every cell of a 2-configuration of a finite set A is m -separable, then the whole 2-configuration is m -separable. (b) [30] Show that any barren 2-configuration of a finite set A is 2-separable.
解析
- (a) Show that if every cell of a 2-configuration of a finite set A is m -separable, then the whole 2-configuration is m -separable. Solution: Let C be a 2-configuration of A with cells A , . . . , A , so that there is 1 n no element of C with one element in A and another in A for i 6 = j . Suppose that i j each cell is m -separable, so that for each i , 1 ≤ i ≤ n , there is a labeling function f : A → { 1 , . . . , m } such that no two elements in the same pair of C are assigned the i i same number. Then, by combining, we get a function f on all of A whose restriction to A is f for each i . By the definition of f , within each A there is no element of C i i i i both 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 the i existence 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 n where each { a , a } and { a , a } all belong to the 2-configuration). For any two i i +1 n 0 distinct elements a, b of A in the same cell of a 2-configuration C , define the distance between them to be the smallest n such that there exists a sequence a = a , a , . . . , a = 0 1 n 6 b with { a , a } , { a , a } , . . . , { a , a } all belonging to the 2-configuration. Notice that 0 1 1 2 n − 1 n the terms of this sequence are all distinct: if a = a for i < j , then we have the shorter i j sequence 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 and all elements at even distance from it with the integer 1, and label all elements at odd distance from it with the integer 2. We claim no two different elements with the same label 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 claim p p 0 m q ′ ′ the set { a , a , . . . , a , a , . . . , a } is then a cycle. It is straightforward to check n n − 1 p q +1 m that 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 (by p n p n m ′ minimality of our sequence ( a )), but this means that m = n + 1, so the distances of b i and c from a have opposite parities, contradicting the assumption that they have the ′ ′ same label. The case a = a is similar. Thus, our set really does have at least three q m elements, and it is a cycle. But since A is barren, it contains no cycles, and we have a contradiction. 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.