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

HMMT November 2016 — Guts Round — Problem 11

[ 8 ] How many subsets S of the set { 1 , 2 , . . . , 10 } satisfy the property that, for all i ∈ [1 , 9], either i or i + 1 (or both) is in S ?

解析

[ 8 ] How many subsets S of the set { 1 , 2 , . . . , 10 } satisfy the property that, for all i ∈ [1 , 9], either i or i + 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 be consecutive, otherwise there exists an index i such that both i and i + 1 are both not in S . Hence if there are k i ’s not in S , we want to arrange k black balls and 10 − k white balls such that no two black balls are consecutive. Take out k − 1 white balls to insert back between black balls later, then we want ( ) 11 − k to 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