Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
For a more advanced approach, see Mike Spivey's answer here: math.stackexchange.com/questions/89548/… –  Byron Schmuland Nov 6 '13 at 13:25
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.