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

HMMT November 2014 — Guts Round — Problem 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 .

解析

[ 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 each subset. For each k ∈ { 1 , 2 , ..., 999 } , there are 1000 choices for the first subset in the chain that contains k . This count includes the possibility that k doesn’t appear in any of the subsets. If S is the first i subset containing k , for some i ∈ { 1 , 2 , ..., 999 } , then k is also in S , for all i < j ≤ 999. As a result, j picking the first subset that contains k uniquely determines the appearance of k in all the subsets. It 999 follows that there are 1000 such subset chains.