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

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

Пусть ${\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}$ .

См. также

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