Let $S=\{1,2, \ldots, 2017\}$.

Determine the largest natural number $n$ for which there are $n$ different subsets of $S$ such that the union of no two of these subsets equals $S$.

(Gerhard Woeginger)
Answer: $n=2^{2016}$.

Proof:

There are $2^{2016}$ subsets of $S$ that do not contain the element 2017. The union of any two of these subsets also does not contain 2017 and is therefore not equal to $S$. Hence, the desired $n$ is at least $2^{2016}$.

If we pair each subset of $S$ with its complement, we can divide $S$ into $2^{2016}$ pairs. If $n$ were greater than $2^{2016}$, there would have to be at least one such pair among the $n$ subsets. The union of such a pair would be the entire set $S$, which is not possible. Therefore, $n$ cannot be greater than $2^{2016}$.

Thus, the desired value is $n=2^{2016}$.

(Gerhard Woeginger)

![](https://cdn.mathpix.com/cropped/2024_04_17_5da65e47240854f15caeg-14.jpg?height=905&width=1060&top_left_y=107&top_left_x=498)

Figure 3: Problem 5, Solution 3