HMMT 二月 2014 · 冲刺赛 · 第 10 题

HMMT February 2014 — Guts Round — Problem 10

[ 6 ] Find the number of nonempty sets F of subsets of the set { 1 , . . . , 2014 } such that: (a) For any subsets S , S 2 F , S \ S 2 F . 1 2 1 2 (b) If S 2 F , T ✓ { 1 , . . . , 2014 } , and S ✓ T , then T 2 F .

解析

[ 6 ] Find the number of nonempty sets F of subsets of the set { 1 , . . . , 2014 } such that: (a) For any subsets S , S ∈ F , S ∩ S ∈ F . 1 2 1 2 (b) If S ∈ F , T ⊆ { 1 , . . . , 2014 } , and S ⊆ T , then T ∈ F . 2014 Answer: 2 For a subset S of { 1 , . . . , 2014 } , let F be the set of all sets T such that S ⊆ T ⊆ S { 1 , . . . , 2014 } . It can be checked that the sets F satisfy the conditions 1 and 2. We claim that the S F are the only sets of subsets of { 1 , . . . , 2014 } satisfying the conditions 1 and 2. (Thus, the answer is S 2014 the number of subsets S of { 1 , . . . , 2014 } , which is 2 .) Suppose that F satisfies the conditions 1 and 2, and let S be the intersection of all the sets of F . We claim that F = F . First, by definition of S , all elements T ∈ F are supersets of S , so F ⊆ F . On S S the other hand, by iterating condition 1, it follows that S is an element of F , so by condition 2 any set T with S ⊆ T ⊆ { 1 , . . . , 2014 } is an element of F . So F ⊇ F . Thus F = F . S S