From Wikipedia, the free encyclopedia
Relates the maximum element of a set of numbers and the minima of its non-empty subsets
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 non-empty subsets of S .
Let S = {x 1 , x 2 , ..., x n 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.
