Maths Olympiad Prep

Library / /562 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Find the number of nonempty sets F\mathcal{F} of subsets of the set {1,,2014}\{1, \ldots, 2014\} such that: (a) For any subsets S1,S2F,S1S2FS_{1}, S_{2} \in \mathcal{F}, S_{1} \cap S_{2} \in \mathcal{F}. (b) If SF,T{1,,2014}S \in \mathcal{F}, T \subseteq\{1, \ldots, 2014\}, and STS \subseteq T, then TFT \in \mathcal{F}.

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

Solution

For a subset SS of {1,,2014}\{1, \ldots, 2014\}, let FS\mathcal{F}_{S} be the set of all sets TT such that ST{1,,2014}S \subseteq T \subseteq \{1, \ldots, 2014\}. It can be checked that the sets FS\mathcal{F}_{S} satisfy the conditions 1 and 2. We claim that the FS\mathcal{F}_{S} are the only sets of subsets of {1,,2014}\{1, \ldots, 2014\} satisfying the conditions 1 and 2. (Thus, the answer is the number of subsets SS of {1,,2014}\{1, \ldots, 2014\}, which is 220142^{2014}.) Suppose that F\mathcal{F} satisfies the conditions 1 and 2, and let SS be the intersection of all the sets of F\mathcal{F}. We claim that F=FS\mathcal{F}=\mathcal{F}_{S}. First, by definition of SS, all elements TFT \in \mathcal{F} are supersets of SS, so FFS\mathcal{F} \subseteq \mathcal{F}_{S}. On the other hand, by iterating condition 1, it follows that SS is an element of F\mathcal{F}, so by condition 2 any set TT with ST{1,,2014}S \subseteq T \subseteq \{1, \ldots, 2014\} is an element of F\mathcal{F}. So FFS\mathcal{F} \supseteq \mathcal{F}_{S}. Thus F=FS\mathcal{F}=\mathcal{F}_{S}.

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.