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

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

Формулировка

Пусть $x_1,\dots ,x_n$ — произвольные действительные числа. Тогда тождество утверждает:

$\max (x_1,\dots ,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)+\dots +(-1{)}^{n-1}\min (x_1,\dots ,x_n)$

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

$\min (x_1,\dots ,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)+\dots +(-1{)}^{n-1}\max (x_1,\dots ,x_n)$

Доказательство

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

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

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

$\max (x_1+a,\dots ,x_n+a)=\max (x_1,\dots ,x_n)+a$

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

$\begin{array}{cc}\sum _{k=1}^n\sum _{i_1<\dots <i_k}(-1{)}^{k-1}& \min (x_{i_1}+a,\dots ,x_{i_k}+a)=\\ & =\sum _{k=1}^n\sum _{i_1<\dots <i_k}(-1{)}^{k-1}\min (x_{i_1},\dots ,x_{i_k})+a\sum _{k=1}^n(-1{)}^{k-1}\sum _{i_1<\dots <i_k}1\end{array}$

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

$\sum _{k=1}^n(-1{)}^{k-1}\sum _{i_1<\dots <i_k}1=\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})=1$

Заменим теперь все $x_i$ на $x{\text{'}}_i=x_i+a$, где $a=-\min (x_1,\dots ,x_n)$. В силу вышеизложенных соображений соотношение для набора $x{\text{'}}_i$ будет выполнено тогда и только тогда, когда выполнено соотношение для набора $x_i$. Но при этом все $x{\text{'}}_i\ge 0$, и одно или несколько чисел из набора $x{\text{'}}_i$ равны $0$.

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

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

$\max (x{\text{'}}_1,\dots ,x{\text{'}}_m)=\sum _{i}x{\text{'}}_i-\sum _{i<j}\min (x{\text{'}}_i,x{\text{'}}_j)+\sum _{i<j<k}\min (x{\text{'}}_i,x{\text{'}}_j,x{\text{'}}_k)+\dots +(-1{)}^{m-1}\min (x{\text{'}}_1,\dots ,x{\text{'}}_m)$

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

См. также

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