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 2n − 1 non-empty subsets of S. Let S = {x1, x2, ..., xn}. The identity states that
max { x 1 , x 2 , … , x n } = ∑ i = 1 n x i − ∑ i < j min { x i , x j } + ∑ i < j < k min { x i , x j , x k } − ⋯ ⋯ + ( − 1 ) n + 1 min { x 1 , x 2 , … , x n } , {\displaystyle {\begin{aligned}\max\{x_{1},x_{2},\ldots ,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}\}-\cdots \\&\qquad \cdots +\left(-1\right)^{n+1}\min\{x_{1},x_{2},\ldots ,x_{n}\},\end{aligned}}}
or conversely
min { x 1 , x 2 , … , x n } = ∑ i = 1 n x i − ∑ i < j max { x i , x j } + ∑ i < j < k max { x i , x j , x k } − ⋯ ⋯ + ( − 1 ) n + 1 max { x 1 , x 2 , … , x n } . {\displaystyle {\begin{aligned}\min\{x_{1},x_{2},\ldots ,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}\}-\cdots \\&\qquad \cdots +\left(-1\right)^{n+1}\max\{x_{1},x_{2},\ldots ,x_{n}\}.\end{aligned}}}
For a probabilistic proof, see the reference.
See also Inclusion–exclusion principle Maxima and minima § In relation to sets
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.