HMMT 二月 2012 · 冲刺赛 · 第 32 题
HMMT February 2012 — Guts Round — Problem 32
题目详情
- [ 19 ] Let S be a set of size 3. How many collections T of subsets of S have the property that for any two subsets U ∈ T and V ∈ T , both U ∩ V and U ∪ V are in T ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TH 15 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 11 FEBRUARY 2012 — GUTS ROUND √
解析
- [ 19 ] Let S be a set of size 3. How many collections T of subsets of S have the property that for any two subsets U ∈ T and V ∈ T , both U ∩ V and U ∪ V are in T ? ⋃ Answer: 74 Let us consider the collections T grouped based on the size of the set X = U , U ∈ T which we can see also must be in T as long as T contains at least one set. This leads us to count the number of collections on a set of size at most 3 satisfying the desired property with the additional property that the entire set must be in the collection. Let C denote that number of such collections n ( ) ( ) ( ) ( ) 3 3 3 3 on a set of size n . Our answer will then be 1 + C + C + C + C , with the additional 1 0 1 2 3 0 1 2 3 coming from the empty collection. ⋂ Now for such a collection T on a set of n elements, consider the set I = U . Suppose this set has U ∈ T size k . Then removing all these elements from consideration gives us another such collection on a set of size n − k , but now containing the empty set. We can see that for each particular choice of I , this gives a bijection to the collections on the set S to the collections on the set S − I . This leads us to consider the further restricted collections that must contain both the entire set and the empty set. It turns out that such restricted collections are a well-studied class of objects called topological spaces . Let T be the number of topological spaces on n elements. Our argument before shows that C = n n ( ) ∑ n n T . It is relatively straightforward to see that T = 1 , T = 1, and T = 4. For a set of size k 0 1 2 k =0 k 3, there are the following spaces. The number of symmetric versions is shown in parentheses. • ∅ , { a, b, c } (1) • ∅ , { a, b } , { a, b, c } (3) • ∅ , { a } , { a, b, c } (3) • ∅ , { a } , { a, b } , { a, b, c } (6) • ∅ , { a } , { b, c } , { a, b, c } (3) Guts • ∅ , { a } , { a, b } , { a, c } , { a, b, c } (3) • ∅ , { a } , { b } , { a, b } . { a, b, c } (3) • ∅ , { a } , { b } , { a, b } , { a, c } , { a, b, c } (6) • ∅ , { a } , { b } , { c } , { a, b } , { a, c } , { b, c } , { a, b, c } (1) ( ) ( ) ( ) 0 1 1 which gives T = 29. Tracing back our reductions, we have that C = T = 1 , C = T + T = 3 0 0 1 0 1 0 0 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 2 2 3 3 3 3 2 , C = T + T + T = 7 , C = T + T + T + T = 45, and then our answer is 2 0 1 2 3 0 1 2 3 0 1 2 0 1 2 3 ( ) ( ) ( ) ( ) 3 3 3 3 1 + C + C + C + C = 1 + 1 + 6 + 21 + 45 = 74. 0 1 2 3 0 1 2 3 √