## IMC 2011 Day 1 Problem 4

Let be finite, nonempty sets. Define the function

Prove that is nondecreasing on .

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

Consider subsets of a great finite space . Suppose that for a set and for every element we have that . Then for every subset we have . Consider the events . Then by the inclusion – exclusion principle, we have

.

If we increase the probability then increases also. Therefore is increasing.

Advertisements

Categories: Olympiad, Probability
IMC, Probability

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

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

For n = 1 case we would have , which is a decreasing function on .

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.

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