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

英文解析

4. (a) Suppose A has n elements, where n ≥ 2, and C is a 2-configuration of A that isnot m -separable for any m < n . What is (in terms of n ) the smallest number ofelements that C can have?
   Solution: We claim that every pair of elements of A must belong to C , so that the
   ( )
   answer is . Indeed, if a, b ∈ A and { a, b } is not in the 2-configuration, then we cannassign the other elements of A the numbers 1 , 2 , . . . , n − 2 and assign a and b both 2
   the number n − 1, so that C is ( n − 1)-separable. On the other hand, if every pair ofelements of A is in the configuration, then A cannot be m -separable for m < n , sincethis would require assigning the same number to at least two elements, and then wewould 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 everyinteger 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, whenm ≥ n/ 2 ⇒ m ≥ d n/ 2 e , this labeling shows that any 3-configuration is m -separable.
   (c) Fix k ≥ 2, and suppose A has k elements. Show that any k -configuration of A2
   ( )
   k − 12
   with fewer than elements is k -separable.
   k − 1
   Solution: The argument is similar to that used in problem 2. Suppose the config-
   uration is not k -separable. Consider all possible orderings of the k elements of A .2
   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 someelement of the k -configuration whose elements are all assigned the same number. Nowconsider any given element E of the k -configuration. For each i , we count the orderingsin which all k elements of E receive the number i : there are k ! possible orderings forthe 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 2
   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
   elements E of the k -configuration. Hence, if there are fewer elements, the k -configuration 3
   is k -separable, as desired.