Тождество максимумов и минимумов (Mk';yvmfk bgtvnbrbkf n bnunbrbkf)

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

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

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

$\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})$

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

$\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})$

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

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

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

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

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

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

${\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}}$

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

$\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$

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

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

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

$\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})$

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

См. также

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