HMMT 二月 2003 · 团队赛 · 第 4 题
HMMT February 2003 — Team Round — Problem 4
题目详情
- (a) [15] Suppose A has n elements, where n ≥ 2, and C is a 2-configuration of A that is not m -separable for any m < n . What is (in terms of n ) the smallest number of elements that C can have? (b) [15] Show that every 3-configuration of an n -element set A is m -separable for every integer m ≥ n/ 2. 2 (c) [25] Fix k ≥ 2, and suppose A has k elements. Show that any k -configuration ( ) 2 k − 1 of A with fewer than elements is k -separable. k − 1
解析
- (a) Suppose A has n elements, where n ≥ 2, and C is a 2-configuration of A that is not m -separable for any m < n . What is (in terms of n ) the smallest number of elements that C can have? Solution: We claim that every pair of elements of A must belong to C , so that the ( ) n answer is . Indeed, if a, b ∈ A and { a, b } is not in the 2-configuration, then we can 2 assign the other elements of A the numbers 1 , 2 , . . . , n − 2 and assign a and b both the number n − 1, so that C is ( n − 1)-separable. On the other hand, if every pair of elements of A is in the configuration, then A cannot be m -separable for m < n , since this would require assigning the same number to at least two elements, and then we would have a pair whose elements have the same number. (b) Show that every 3-configuration of an n -element set A is m -separable for every integer m ≥ n/ 2. Solution: We can successively label the elements of A with the numbers 1 , 1 , 2 , 2 , 3 , 3 , . . . , d n/ 2 e . Then surely no 3-element subset can have all its elements labeled with the same number, since no label is assigned to more than two elements. Thus, when m ≥ n/ 2 ⇒ m ≥ d n/ 2 e , this labeling shows that any 3-configuration is m -separable. 2 (c) Fix k ≥ 2, and suppose A has k elements. Show that any k -configuration of A ( ) 2 k − 1 with fewer than elements is k -separable. k − 1 Solution: The argument is similar to that used in problem 2. Suppose the config- 2 uration is not k -separable. Consider all possible orderings of the k elements of A . For each ordering, assign the first k elements the number 1, the next k elements the number 2, and so forth. By assumption, for each such assignment, there exists some element of the k -configuration whose elements are all assigned the same number. Now consider any given element E of the k -configuration. For each i , we count the orderings in which all k elements of E receive the number i : there are k ! possible orderings for 2 the elements of E , and there are ( k − k )! possible orderings for the remaining elements 2 of A . Altogether, this gives k · k ! · ( k − k )! orderings in which the elements of E all 2 receive the same label. So if, in each of the ( k )! orderings of the elements of A , there is some E all of whose members receive the same label, then there must be at least ( ) 2 2 2 ( k )! ( k − 1)! k − 1 = = 2 2 k · k ! · ( k − k )! ( k − 1)!( k − k )! k − 1 3 elements E of the k -configuration. Hence, if there are fewer elements, the k -configuration is k -separable, as desired.