# Show that inclusion-exclusion principle applies to finding max.

Show, that : $\text{max} \{x_1,x_2,...,x_n\} = x_1+x_2+...+x_n-\text{min}\{x_1,x_2\}-...-\text{min}\{x_{n-1},x_n\}+\text{min}\{x_1,x_2,x_3\}+...\pm \text{min}\{x_1,x_2,...,x_n\}$

In a way I'm supposed to prove, that the inclusion-exclusion principle somehow applies to finding maximum from given numbers.

I tried some basic induction and the base case $n=2$ is indeedy easy. But I'm having trouble generalizing it. I get something like this:

$\text{max} \{x_1,x_2,...,x_n\} = x_1+x_2+...+x_n-\text{min}\{x_1,x_2\}-...-\text{min}\{x_{n-1},x_n\}+\text{min}\{x_1,x_2,x_3\}+...\pm \text{min}\{x_1,x_2,...,x_n\}=x_n+\max\{a_1,...,a_{n-1}\}-\text{min}\{a_1,a_n\}-...-\text{min}\{a_{n-1},a_n\}+...\pm \text{min}\{a_1,a_2,...,a_n\}$

And that's not very helpful...

-
For a more advanced approach, see Mike Spivey's answer here: math.stackexchange.com/questions/89548/… – Byron Schmuland Nov 6 '13 at 13:25

Let $X_i = [a,x_i]$. Then $\min$ is $\cap$ and $\max$ is $\cup$. That is the $\max$ problem is reducible to the usual set union problem. For example $\max\{x_1, x_1\} = x_1 + x_2 - \min\{x_1, x_2\}$ becomes $A(X_1 \cup X_2) = A(X_1) + A(X_2) - A(X_1 \cap X_2)$. If you can prove equivalence, then you're done.

-
I guess you change the left endpoint if the numbers are not non-negative. – Byron Schmuland Nov 6 '13 at 13:26
@ByronSchmuland, that slipped by me. Thanks for pointing it out. – Karolis Juodelė Nov 6 '13 at 13:53