Home > Olympiad, Probability > IMC 2011 Day 1 Problem 4

IMC 2011 Day 1 Problem 4

Let A_1,A_2,...,A_n be finite, nonempty sets. Define the function

\displaystyle f(t)=\sum_{k=1}^n \sum_{1\leq i_1 < i_2 <...< i_k\leq n} (-1)^{k-1} t^{|A_{i_1}\cup A_{i_2}\cup ... \cup A_{i_k}|}

Prove that f is nondecreasing on [0,1].

Hint: A very cool solution uses the inclusion exclusion principle for probability. Here it is:

Consider A_1,...,A_n subsets of a great finite space X. Suppose that for a set C and for every element x \in X we have that P(x \in C)=t \in [0,1],\ i=1..n. Then for every subset A \subset X we have P(A \subset C)=t^{|A|}. Consider the events E_i : A_i \subset C. Then by the inclusion – exclusion principle, we have

\displaystyle P(E_1\cap E_2\cap...\cap E_n)= \sum_{k=1}^n \sum_{1\leq i_1 < i_2 <...< i_k\leq n} (-1)^{k-1} P(E_{i_1}\cup E_{i_2}\cup ... \cup E_{i_k})=f(t).

If we increase the probability t then P(E_1 \cap E_2\cap...\cap E_n)=f(t) increases also. Therefore f(t) is increasing.

Categories: Olympiad, Probability Tags: ,
  1. Matija Basic
    July 31, 2011 at 11:08 pm

    Hi, how did you have the problems before the competition? 🙂

    • July 31, 2011 at 11:12 pm

      I didn’t have the problems before the competition. I posted them as soon as the competition was over. I made the posts with titles a few days ago and edited them when I got the problems. 🙂

  2. ilonpilaaja
    October 15, 2011 at 3:37 pm

    For n = 1 case we would have f(t) = -t^{A_1}, which is a decreasing function on [0,1].
    Also, for the right-hand side PIE is usually contains intersections of sets rather than unions,
    so I couldn’t see how it can be solved _immediately_ with PIE. The thing is I’m giving a short talk
    at a class about PIE, so could you give me a tiny hint? Thanks, and keep up your good work.

    • October 15, 2011 at 7:24 pm

      I’ll post the solution later this evening. Thanks for the comment.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: