Browse · MathNet
Print48th Austrian Mathematical Olympiad
Austria counting and probability
Problem
Let . Find the maximal with the property that there exist distinct subsets of such that for no two subsets their union equals .
Solution
Answer: .
Proof: There are subsets of which do not contain . The union of any two such subsets does not contain and is thus a proper subset of . Thus .
To show the other direction, we group the subsets of into pairs in such a way that every subset forms a pair with its complement. If then the subsets would contain such a pair. Its union would be , contradiction.
Thus .
Proof: There are subsets of which do not contain . The union of any two such subsets does not contain and is thus a proper subset of . Thus .
To show the other direction, we group the subsets of into pairs in such a way that every subset forms a pair with its complement. If then the subsets would contain such a pair. Its union would be , contradiction.
Thus .
Final answer
2^2016
Techniques
Pigeonhole principleColoring schemes, extremal arguments