HMMT 二月 2016 · 团队赛 · 第 6 题

英文解析

6. [ 35 ] A nonempty set S is called well-filled if for every m ∈ S , there are fewer than m elements of Swhich are less than m . Determine the number of well-filled subsets of { 1 , 2 , . . . , 42 } .2
   Proposed by: Casey Fu
   ( )
   Answer: − 143
   Let a be the number of well-filled subsets whose maximum element is n (setting a = 1). Then it’s 21
   n 0
   easy to see thata = a + a + · · · + a
   2 k +1 2 k 2 k − 1 0
   a = ( a − C ) + a + · · · + a .
   2 k +2 2 k +1 k 2 k 0
   where C is the number of well-filled subsets of size k + 1 with maximal element 2 k + 1.
   We proceed to compute C . One can think of such a subset as a sequence of numbers 1 ≤ s < · · · <kk 1
   s ≤ 2 k + 1 such that s ≥ 2 i − 1 for every 1 ≤ i ≤ k + 1. Equivalently, letting s = i + 1 + t it’sk +1 i i ithe number of sequences 0 ≤ t ≤ · · · ≤ t ≤ k + 1 such that t ≥ i for every i . This gives the list of
   1 k +1 ix -coordinates of steps up in a Catalan path from (0 , 0) to ( k + 1 , k + 1), so
   ( )
   1 2( k + 1)
   C =
   k + 2 ( k + 1)kis equal to the ( k + 1)th Catalan number.
   From this we can solve the above recursion to derive that
   ( )
   a = .nnb ( n − 1) / 2 c
   Consequently, for even n ,
   ( )
   n + 1
   a + · · · + a = a = .
   0 n n +1
   b n/ 2 c
   Putting n = 42 gives the answer, after subtracting off the empty set (counted in a ).
   1 2 n n − 10