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

英文解析

5. Let B ( n ) be the largest possible number of elements in a 2-separable k -configuration ofka set with 2 n elements (2 ≤ k ≤ n ). Find a closed-form expression (i.e. an expressionnot involving any sums or products with a variable number of terms) for B ( n ).
   ( ) ( ) ( )ka 2 n − a n
   Solution: First, a lemma: For any a with 0 ≤ a ≤ 2 n , + ≥ 2 . (Byk k k
   ( )
   convention, we set = 0 when a < k .) Proof: We may assume a ≥ n , since otherwiseakwe can replace a with 2 n − a . Now we prove the result by induction on a . For the base
   ( ) ( )
   n ncase, if a = n , then the lemma states that 2 ≥ 2 , which is trivial. If the lemmak kholds 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 inductionk k k k kstep. 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 thea 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 mostk 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 thek kk -element subsets of A , except those contained entirely within the first n elementsor 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 kk