Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
For a more advanced approach, see Mike Spivey's answer here:… – Byron Schmuland Nov 6 '13 at 13:25
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|cite|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

Your Answer


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.