Maximum-minimums identity

In mathematics, the maximum-minimums identity is a relation between the maximum element of a set S of n numbers and the minima of the 2ⁿ − 1 non-empty subsets of S.

Let S = {x₁, x₂, ..., x_n}. The identity states that

\begin{matrix} max {x_{1}, x_{2}, \dots, x_{n}} & = \sum_{i = 1}^{n} x_{i} - \sum_{i < j} min {x_{i}, x_{j}} + \sum_{i < j < k} min {x_{i}, x_{j}, x_{k}} - \dots \\ \dots + {(- 1)}^{n + 1} min {x_{1}, x_{2}, \dots, x_{n}}, \end{matrix}

or conversely

\begin{matrix} min {x_{1}, x_{2}, \dots, x_{n}} & = \sum_{i = 1}^{n} x_{i} - \sum_{i < j} max {x_{i}, x_{j}} + \sum_{i < j < k} max {x_{i}, x_{j}, x_{k}} - \dots \\ \dots + {(- 1)}^{n + 1} max {x_{1}, x_{2}, \dots, x_{n}} . \end{matrix}

For a probabilistic proof, see the reference.

References

Ross, Sheldon M. (2020). A First Course in Probability (Tenth, global ed.). Harlow, United Kingdom: Pearson. pp. 331–333. ISBN 978-1-292-26920-7.

Maximum-minimums identity

See also

References