6
$\begingroup$

$$\max(x_1, x_2, x_3) = x_1 + x_2 + x_3 - \min(x_1, x_2) - \min(x_1, x_3) - \min(x_2, x_3) + \min(x_1, x_2, x_3)$$

Is there a more elegant proof to this than just trying out all the possibilities and showing that it works? For example, assuming that the numbers are distinct, this statement is true if $x_1 < x_2 < x_3$ since the equation would yield $x_1 + x_2 + x_3 - x_1 - x_1 - x_2 + x_1 = x_3$, etc.

It also seems to work if the numbers are not distinct, but then there are even more combinations to try. Also, interestingly, it looks like inclusion-exclusion but that might be a red herring. Also not sure how to tag this question...

$\endgroup$
1
  • 1
    $\begingroup$ WLOG, assume $x_1 \geq x_2 \geq x_3$ $\endgroup$
    – PSPACEhard
    May 1, 2015 at 2:22

4 Answers 4

5
$\begingroup$

It is essentially inclusion-exclusion. $x_1+x_2+x_3$ counts each number once. $-\min(x_1, x_2)-\min(x_1,x_3)-\min(x_2,x_3)$ removes the smallest element twice and the second smallest number once. This has now under-counted the smallest number (and removed the second smallest). Then $+\min(x_1, x_2, x_3)$ puts back the under-counted smallest number.

$\endgroup$
2
$\begingroup$

It really is inclusion/exclusion. For each number $x_i$, define $X_i$ to be the interval $[0,x_i]$. Then for any set $I$ of indices, $|\cup_{i\in I} X_i|=\max_{i\in I} x_i$ and $|\cap_{i\in I}X_i|=\min_{i\in I}x_i$. So inclusion/exclusion translates directly to the formula in the problem.

$\endgroup$
0
$\begingroup$

A formula that might be of use to you is the following: $$ \max(a,b) = \frac{a + b + |b-a|}{2} $$

If you don't want to do case by case, you can apply this formula repeatedly, although it is true that the algebra does get voluminous.

$\endgroup$
0
$\begingroup$

For $x_1,\ldots,x_n$ distinct, $$ \max\{x_1,\ldots,x_n\}=\sum\limits_{i=1}^{n}x_i\prod\limits_{j\ne i}(1-{\bf 1}_{x_j>x_i}) $$


For completeness, more generally,

$$ \max\{x_1,\ldots,x_n\}=\sum\limits_{i=1}^{n}x_i{\bf 1}_{x_i\geqslant x_{j\ne i}}-\sum\limits_{i<j}x_i{\bf 1}_{x_i\geqslant x_{k\ne i,j}, x_i=x_j}+\ldots +(-)^{n+1}x_1{\bf 1}_{x_1=\ldots=x_n} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .