Maths Olympiad Prep

Library / /54 of 84

, 2014

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:
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,S2FS_{1}, S_{2} \in \mathcal{F}, S1S2FS_{1} \cap S_{2} \in \mathcal{F}.

b. If SFS \in \mathcal{F}, T{1,,2014}T \subseteq \{1, \ldots, 2014\}, and STS \subseteq T, then TFT \in \mathcal{F}.

Solution

Solution:
Answer: 220142^{2014}

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.