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

HMMT February 2016 — Team Round — Problem 6

[ 35 ] A nonempty set S is called well-filled if for every m ∈ S , there are fewer than m elements of S 2 which are less than m . Determine the number of well-filled subsets of { 1 , 2 , . . . , 42 } . 1 2 n n − 1

解析

[ 35 ] A nonempty set S is called well-filled if for every m ∈ S , there are fewer than m elements of S 2 which are less than m . Determine the number of well-filled subsets of { 1 , 2 , . . . , 42 } . Proposed by: Casey Fu ( ) 43 Answer: − 1 21 Let a be the number of well-filled subsets whose maximum element is n (setting a = 1). Then it’s n 0 easy to see that a = 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. k We proceed to compute C . One can think of such a subset as a sequence of numbers 1 ≤ s < · · · < k 1 s ≤ 2 k + 1 such that s ≥ 2 i − 1 for every 1 ≤ i ≤ k + 1. Equivalently, letting s = i + 1 + t it’s k +1 i i i the number of sequences 0 ≤ t ≤ · · · ≤ t ≤ k + 1 such that t ≥ i for every i . This gives the list of 1 k +1 i x -coordinates of steps up in a Catalan path from (0 , 0) to ( k + 1 , k + 1), so ( ) 1 2( k + 1) C = k k + 2 ( k + 1) is equal to the ( k + 1)th Catalan number. From this we can solve the above recursion to derive that ( ) n a = . n b ( 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 ). 0 1 2 n n − 1