uniolympiads Ελληνικά

IMC 2011, Day 1, Problem 4

Let A1,A2,…,AnA_1, A_2, \dots, A_n be finite, nonempty sets. Define the function

f(t)=∑k=1n∑1≤i1<i2<⋯<ik≤n(−1)k−1t∣Ai1∪Ai2∪⋯∪Aik∣.f(t) = \sum_{k=1}^{n} \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} (-1)^{k-1} t^{|A_{i_1} \cup A_{i_2} \cup \dots \cup A_{i_k}|}.

Prove that ff is nondecreasing on [0,1][0, 1]. (∣A∣|A| denotes the number of elements in AA.)

Levon Nurbekyan and Vardan Voskanyan, Yerevan

Original from the official PDFLet 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)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Levon Nurbekyan and Vardan Voskanyan, Yerevan)

Solution 1. Let Ω=⋃i=1nAi\Omega=\bigcup\limits_{i=1}^n A_i. Consider a random subset XX of Ω\Omega which chosen in the following way: for each x∈Ωx\in\Omega, choose the element xx for the set XX with probability tt, independently from the other elements.

Then for any set C⊂ΩC\subset\Omega, we have

P(C⊂X)=t∣C∣.P(C\subset X)=t^{|C|}.
By the inclusion-exclusion principle,
P((A1⊂X) or (A2⊂X) or  …  or (An⊂X))==∑k=1n ∑1≤i1<i2<…<ik≤n(−1)k−1P(Ai1∪Ai2∪…∪Aik⊂X)==∑k=1n ∑1≤i1<i2<…<ik≤n(−1)k−1t∣Ai1∪Ai2∪…∪Aik∣.\begin{aligned} &P\big((A_1\subset X)\text{ or }(A_2\subset X)\text{ or }\ \ldots\ \text{ or }(A_n\subset X)\big)=\\ &=\sum_{k=1}^n\ \sum_{1\le i_1<i_2<\ldots<i_k\le n}(-1)^{k-1}P\big(A_{i_1}\cup A_{i_2}\cup\ldots\cup A_{i_k}\subset X\big)=\\ &=\sum_{k=1}^n\ \sum_{1\le i_1<i_2<\ldots<i_k\le n}(-1)^{k-1}t^{|A_{i_1}\cup A_{i_2}\cup\ldots\cup A_{i_k}|}. \end{aligned}
The probability P((A1⊂X) or  …  or (An⊂X))P\big((A_1\subset X)\text{ or }\ \ldots\ \text{ or }(A_n\subset X)\big) is a nondecreasing function of the probability tt.

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?