HMMT 二月 2012 · 冲刺赛 · 第 32 题

英文解析

32. [ 19 ] Let S be a set of size 3. How many collections T of subsets of S have the property that for anytwo 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 ∈ Twhich we can see also must be in T as long as T contains at least one set. This leads us to countthe number of collections on a set of size at most 3 satisfying the desired property with the additionalproperty 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 ∈ Tsize k . Then removing all these elements from consideration gives us another such collection on a setof size n − k , but now containing the empty set. We can see that for each particular choice of I , thisgives a bijection to the collections on the set S to the collections on the set S − I . This leads us toconsider 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
    ( )
    ∑
    T . It is relatively straightforward to see that T = 1 , T = 1, and T = 4. For a set of sizennk 0 1 2
    k =0
    3, there are the following spaces. The number of symmetric versions is shown in parentheses.k
    • ∅ , { 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
    √