IMC 2011, Day 1, Problem 4
Let be finite, nonempty sets. Define the function
Prove that is nondecreasing on . ( denotes the number of elements in .)
Levon Nurbekyan and Vardan Voskanyan, Yerevan
Original from the official PDF
![Let A 1 , A 2 , . . . , A n be finite, nonempty sets. Define the function f (t) = n X X (−1) k−1 t |A i 1 ∪A i 2 ∪...∪A ik | . k=1 1≤i 1 <i 2 <...<i k ≤n Prove that f is nondecreasing on [0, 1]. (|A| denotes the number of elements in A.) (Levon Nurbekyan and Vardan Voskanyan, Yerevan)](/archive/imc/imc-2011-d1-p4.png)
This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(Levon Nurbekyan and Vardan Voskanyan, Yerevan)
Solution 1. Let . Consider a random subset of which chosen in the following way: for each , choose the element for the set with probability , independently from the other elements.
Then for any set , we have
Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.