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.

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