Тождество максимумов и минимумов

Тождество максимумов и минимумов — математическое соотношение между максимальным элементом конечного множества чисел и минимальными элементами всех его непустых подмножеств.

Пусть ${\displaystyle x_{1},\ldots ,x_{n}}$ — произвольные действительные числа. Тогда тождество утверждает:

${\displaystyle \max(x_{1},\ldots ,x_{n})=\sum _{i}x_{i}-\sum _{i<j}\min(x_{i},x_{j})+\sum _{i<j<k}\min(x_{i},x_{j},x_{k})+\ldots +(-1)^{n-1}\,\min(x_{1},\ldots ,x_{n})}$

Аналогичное соотношение имеет место, если поменять местами минимумы и максимумы:

${\displaystyle \min(x_{1},\ldots ,x_{n})=\sum _{i}x_{i}-\sum _{i<j}\max(x_{i},x_{j})+\sum _{i<j<k}\max(x_{i},x_{j},x_{k})+\ldots +(-1)^{n-1}\,\max(x_{1},\ldots ,x_{n})}$

Докажем, например, первое из приведённых соотношений.

Заметим, что если заменить ${\displaystyle x\mapsto x+a}$, где ${\displaystyle a}$ — произвольное число, то обе части доказываемого соотношения также изменятся на ${\displaystyle a}$.

Действительно, левая часть:

${\displaystyle \max(x_{1}+a,\ldots ,x_{n}+a)=\max(x_{1},\ldots ,x_{n})+a}$

Правая часть:

${\displaystyle {\begin{aligned}\sum _{k=1}^{n}\sum _{i_{1}<\ldots <i_{k}}(-1)^{k-1}\,&\min(x_{i_{1}}+a,\ldots ,x_{i_{k}}+a)=\\&=\sum _{k=1}^{n}\sum _{i_{1}<\ldots <i_{k}}(-1)^{k-1}\,\min(x_{i_{1}},\ldots ,x_{i_{k}})+a\sum _{k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\!\!\!1\end{aligned}}}$

Второе слагаемое в точности равно ${\displaystyle a}$, в силу известного свойства биномиальных коэффициентов:

${\displaystyle \sum _{k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\!\!\!1=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}=1}$

Заменим теперь все ${\displaystyle x_{i}}$ на ${\displaystyle x'_{i}=x_{i}+a}$, где ${\displaystyle a=-\min(x_{1},\ldots ,x_{n})}$. В силу вышеизложенных соображений соотношение для набора ${\displaystyle x'_{i}}$ будет выполнено тогда и только тогда, когда выполнено соотношение для набора ${\displaystyle x_{i}}$. Но при этом все ${\displaystyle x'_{i}\geq 0}$, и одно или несколько чисел из набора ${\displaystyle x'_{i}}$ равны ${\displaystyle 0}$.

Если все ${\displaystyle x'_{i}=0}$, то соотношение, очевидно, выполнено.

Рассмотрим случай, когда не все ${\displaystyle x'_{i}=0}$. Пусть для определённости ${\displaystyle x'_{1},\ldots ,x'_{m}>0}$, а ${\displaystyle x'_{m+1}=\ldots =x'_{n}=0}$. Тогда, как легко видеть, все нулевые ${\displaystyle x'_{i}}$ можно исключить из равенства, которое таким образом превращается в

${\displaystyle \max(x'_{1},\ldots ,x'_{m})=\sum _{i}x'_{i}-\sum _{i<j}\min(x'_{i},x'_{j})+\sum _{i<j<k}\min(x'_{i},x'_{j},x'_{k})+\ldots +(-1)^{m-1}\,\min(x'_{1},\ldots ,x'_{m})}$

Таким образом, мы свели соотношение для ${\displaystyle n}$ чисел к аналогичному соотношению для меньшего количества ${\displaystyle m<n}$ чисел. Отсюда в силу принципа математической индукции следует, что исходное соотношение верно для любого натурального ${\displaystyle n}$.

• Формула включений-исключений