Maths Olympiad Prep

Library / /670 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Let SS be a set of size 3. How many collections TT of subsets of SS have the property that for any two subsets UTU \in T and VTV \in T, both UVU \cap V and UVU \cup V are in TT ?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let us consider the collections TT grouped based on the size of the set X=UTUX=\bigcup_{U \in T} U, which we can see also must be in TT as long as TT 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 CnC_{n} denote that number of such collections on a set of size nn. Our answer will then be 1+(30)C0+(31)C1+(32)C2+(33)C31+\binom{3}{0} C_{0}+\binom{3}{1} C_{1}+\binom{3}{2} C_{2}+\binom{3}{3} C_{3}, with the additional 1 coming from the empty collection. Now for such a collection TT on a set of nn elements, consider the set I=UTUI=\bigcap_{U \in T} U. Suppose this set has size kk. Then removing all these elements from consideration gives us another such collection on a set of size nkn-k, but now containing the empty set. We can see that for each particular choice of II, this gives a bijection to the collections on the set SS to the collections on the set SIS-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 TnT_{n} be the number of topological spaces on nn elements. Our argument before shows that Cn=C_{n}= k=0n(nk)Tk\sum_{k=0}^{n}\binom{n}{k} T_{k}. It is relatively straightforward to see that T0=1,T1=1T_{0}=1, T_{1}=1, and T2=4T_{2}=4. For a set of size 3 , there are the following spaces. The number of symmetric versions is shown in parentheses. - ,{a,b,c}(1)\emptyset,\{a, b, c\}(1) - ,{a,b},{a,b,c}(3)\emptyset,\{a, b\},\{a, b, c\}(3) - ,{a},{a,b,c}(3)\emptyset,\{a\},\{a, b, c\}(3) - ,{a},{a,b},{a,b,c}\emptyset,\{a\},\{a, b\},\{a, b, c\} (6) - ,{a},{b,c},{a,b,c}\emptyset,\{a\},\{b, c\},\{a, b, c\} - ,{a},{a,b},{a,c},{a,b,c}(3)\emptyset,\{a\},\{a, b\},\{a, c\},\{a, b, c\}(3) - ,{a},{b},{a,b}.{a,b,c}(3)\emptyset,\{a\},\{b\},\{a, b\} .\{a, b, c\}(3) - ,{a},{b},{a,b},{a,c},{a,b,c}(6)\emptyset,\{a\},\{b\},\{a, b\},\{a, c\},\{a, b, c\}(6) - ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}\emptyset,\{a\},\{b\},\{c\},\{a, b\},\{a, c\},\{b, c\},\{a, b, c\} which gives T3=29T_{3}=29. Tracing back our reductions, we have that C0=(00)T0=1,C1=(10)T0+(11)T1=C_{0}=\binom{0}{0} T_{0}=1, C_{1}=\binom{1}{0} T_{0}+\binom{1}{1} T_{1}= 2, C2=(20)T0+(21)T1+(22)T2=7,C3=(30)T0+(31)T1+(32)T2+(33)T3=45C_{2}=\binom{2}{0} T_{0}+\binom{2}{1} T_{1}+\binom{2}{2} T_{2}=7, C_{3}=\binom{3}{0} T_{0}+\binom{3}{1} T_{1}+\binom{3}{2} T_{2}+\binom{3}{3} T_{3}=45, and then our answer is 1+(30)C0+(31)C1+(32)C2+(33)C3=1+1+6+21+45=741+\binom{3}{0} C_{0}+\binom{3}{1} C_{1}+\binom{3}{2} C_{2}+\binom{3}{3} C_{3}=1+1+6+21+45=74.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.