uniolympiads English

IMC 2011, Ημέρα 1, Θέμα 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

Πρωτότυπο από το επίσημο 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)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;