Skip to main content
OlympiadHQ

Browse · MathNet

Print

2 Bulgarian Winter Tournament

Bulgaria counting and probability

Problem

Let and be a nonempty family of nonempty subsets of with the following property – if and , then . Prove that the function is strictly increasing in the interval .
Solution
Let . Notice that . We construct the sets and as follows: For each element we put in with probability (independently of each other), and for each element we put in with probability . Then . It is easy to see that , and , but since has the property from the condition we have that .

Techniques

Expected values