Русская Википедия:Тождество максимумов и минимумов
Тождество максимумов и минимумов — математическое соотношение между максимальным элементом конечного множества чисел и минимальными элементами всех его непустых подмножеств.
Формулировка
Пусть <math>x_1, \ldots , x_n</math> — произвольные действительные числа. Тогда тождество утверждает:
\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)
</math>Аналогичное соотношение имеет место, если поменять местами минимумы и максимумы:
\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)
</math>Доказательство
Докажем, например, первое из приведённых соотношений.
Заметим, что если заменить <math>x \mapsto x + a</math>, где <math>a</math> — произвольное число, то обе части доказываемого соотношения также изменятся на <math>a</math>.
Действительно, левая часть:
\max (x_1 + a, \ldots, x_n + a) = \max (x_1, \ldots, x_n) + a
</math>Правая часть:
<math> \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} </math>
Второе слагаемое в точности равно <math>a</math>, в силу известного свойства биномиальных коэффициентов:
\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
</math>Заменим теперь все <math>x_i</math> на <math>x'_i = x_i + a</math>, где <math>a = - \min(x_1, \ldots, x_n)</math>. В силу вышеизложенных соображений соотношение для набора <math>x'_i</math> будет выполнено тогда и только тогда, когда выполнено соотношение для набора <math>x_i</math>. Но при этом все <math>x'_i \geq 0</math>, и одно или несколько чисел из набора <math>x'_i</math> равны <math>0</math>.
Если все <math>x'_i = 0</math>, то соотношение, очевидно, выполнено.
Рассмотрим случай, когда не все <math>x'_i = 0</math>. Пусть для определённости <math>x'_1, \ldots , x'_m > 0</math>, а <math>x'_{m+1}= \ldots = x'_n = 0</math>. Тогда, как легко видеть, все нулевые <math>x'_i</math> можно исключить из равенства, которое таким образом превращается в
\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)
</math>Таким образом, мы свели соотношение для <math>n</math> чисел к аналогичному соотношению для меньшего количества <math>m < n</math> чисел. Отсюда в силу принципа математической индукции следует, что исходное соотношение верно для любого натурального <math>n</math>.
См. также
