Просмотр кода страницы Тождество максимумов и минимумов

'''Тождество максимумов и минимумов''' — математическое соотношение между [[Максимальный элемент|максимальным]] элементом [[Конечное множество|конечного множества]] чисел и [[Минимальный элемент|минимальными]] элементами всех его непустых [[Подмножество|подмножеств]].

== Формулировка ==
Пусть <math>x_1, \ldots , x_n</math> — произвольные [[Вещественное число|действительные числа]]. Тогда [[Тождество (математика)|тождество]] утверждает:

<center><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></center>

Аналогичное соотношение имеет место, если поменять местами минимумы и максимумы:
<center><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></center>

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

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

Действительно, левая часть:
<center><math>
\max (x_1 + a, \ldots, x_n + a) = \max (x_1, \ldots, x_n) + a
</math></center>

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

<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>, в силу известного свойства [[биномиальный коэффициент|биномиальных коэффициентов]]:
<center><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></center>

Заменим теперь все <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> можно исключить из равенства, которое таким образом превращается в
<center><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></center>

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

== См. также ==
* [[Формула включений-исключений]]

[[Категория:Тождества]]
[[Категория:Арифметика]]