HMMT 十一月 2014 · 冲刺赛 · 第 20 题

英文解析

20. [ 11 ] Determine the number of sequences of sets S , S , . . . , S such that
    1 2 999
    S ⊆ S ⊆ · · · ⊆ S ⊆ { 1 , 2 , . . . , 999 } .
    1 2 999
    Here A ⊆ B means that all elements of A are also elements of B .
    2997 999
    Answer: 10 OR 1000 The idea is to look at each element individually, rather than eachsubset. For each k ∈ { 1 , 2 , ..., 999 } , there are 1000 choices for the first subset in the chain that containsk . This count includes the possibility that k doesn’t appear in any of the subsets. If S is the firstisubset containing k , for some i ∈ { 1 , 2 , ..., 999 } , then k is also in S , for all i < j ≤ 999. As a result,
    picking the first subset that contains k uniquely determines the appearance of k in all the subsets. Itjfollows that there are 1000 such subset chains.999