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 ⊆
{ 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
2014Sthe 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 . Weclaim that F = F . First, by definition of S , all elements T ∈ F are supersets of S , so F ⊆ F . On
S Sthe 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