Competition problem — Combinatorics

Combinatorics Difficulty 5.2 AIME, harder Prove it Austria

Let $S = \{1, 2, \dots, 2017\}$ .
Find the maximal $n$ with the property that there exist $n$ distinct subsets of $S$ such that for no two subsets their union equals $S$ .

Solution

Answer: $n = 2^{2016}$ .

Proof:
There are $2^{2016}$ subsets of $S$ which do not contain $2017$ . The union of any two such subsets does not contain $2017$ and is thus a proper subset of $S$ . Thus $n \ge 2^{2016}$ .

To show the other direction, we group the subsets of $S$ into $2^{2016}$ pairs in such a way that every subset forms a pair with its complement. If $n > 2^{2016}$ then the $n$ subsets would contain such a pair. Its union would be $S$ , contradiction.

Thus $n = 2^{2016}$ .

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.