Browse · MathNet
PrintChina Girls' Mathematical Olympiad
China counting and probability
Problem
Let be an integer greater than two, and let be pairwise distinct nonempty subsets of . Determine the maximum value of . (Here, we set . For a set , let denote the number of elements in .)
Solution
The answer is .
We consider each summand . If is the empty set, then . If is nonempty, because , at least one of and has more than one element, that is, . Because is a subset of each of and , and It follows that This upper bound can be achieved with sets
We consider each summand . If is the empty set, then . If is nonempty, because , at least one of and has more than one element, that is, . Because is a subset of each of and , and It follows that This upper bound can be achieved with sets
Final answer
n
Techniques
Coloring schemes, extremal arguments