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

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

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

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

Второе слагаемое в точности равно $~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$.

См. также

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