HMMT 十一月 2016 · 冲刺赛 · 第 11 题

英文解析

11. [ 8 ] How many subsets S of the set { 1 , 2 , . . . , 10 } satisfy the property that, for all i ∈ [1 , 9], either i ori + 1 (or both) is in S ?
    Proposed by: Eshaan Nichani
    Answer: 144
    We do casework on the number of i ’s not in S . Notice that these i ’s that are not in S cannot beconsecutive, otherwise there exists an index i such that both i and i + 1 are both not in S . Hence ifthere are k i ’s not in S , we want to arrange k black balls and 10 − k white balls such that no two blackballs are consecutive. Take out k − 1 white balls to insert back between black balls later, then we want
    ( )
    11 − kto arrange k black balls and 11 − 2 k white balls arbitrarily, which can be done in ways. Hence
    ( ) ( ) ( ) ( ) ( ) ( )k
    11 10 9 8 7 6
    we want to find the sum + + + + + , which is equal to 144 ways.
    0 1 2 3 4 5