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

HMMT February 2003 — Team Round — Problem 5

[30] Let B ( n ) be the largest number of elements in a 2-separable k -configuration of k a set with 2 n elements (2 ≤ k ≤ n ). Find a closed-form expression (i.e. an expression not involving any sums or products with an variable number of terms) for B ( n ). k

解析

Let B ( n ) be the largest possible number of elements in a 2-separable k -configuration of k a set with 2 n elements (2 ≤ k ≤ n ). Find a closed-form expression (i.e. an expression not involving any sums or products with a variable number of terms) for B ( n ). k ( ) ( ) ( ) a 2 n − a n Solution: First, a lemma: For any a with 0 ≤ a ≤ 2 n , + ≥ 2 . (By k k k ( ) a convention, we set = 0 when a < k .) Proof: We may assume a ≥ n , since otherwise k we can replace a with 2 n − a . Now we prove the result by induction on a . For the base ( ) ( ) n n case, if a = n , then the lemma states that 2 ≥ 2 , which is trivial. If the lemma k k holds for some a > 0, then by the familiar identity, [( ) ( )] [( ) ( )] a + 1 2 n − a − 1 a 2 n − a

− + k k k k [( ) ( )] [( ) ( )] a + 1 a 2 n − a 2 n − a − 1 = − − + k k k k ( ) ( ) a 2 n − a − 1 = − > 0 k − 1 k − 1 ( ) ( ) ( ) ( ) ( ) a +1 2 n − a − 1 a 2 n − a n (since a > 2 n − a − 1), so + > + ≥ 2 , giving the induction k k k k k step. The lemma follows. Now suppose that the elements of A are labeled such that a elements of the set A receive the number 1 and 2 n − a elements receive the number 2. Then the k - configuration can include all k -element subsets of A except those contained among the a elements numbered 1 or the 2 n − a elements numbered 2. Thus, we have at most ( ) ( ) ( ) 2 n a 2 n − a − − elements in the k -configuration, and by the lemma, this is at most k k k ( ) ( ) 2 n n − 2 . k k ( ) ( ) 2 n n On the other hand, we can achieve − 2 via the recipe above — take all the k k k -element subsets of A , except those contained entirely within the first n elements or entirely within the last n elements. Then, labeling the first n elements with the number 1 and the last n elements with the number 2 shows that the configuration is ( ) ( ) 2 n n 2-separable. So, B ( n ) = − 2 . k k k