Тотожність максимумів і мінімумів

Тотожність максимумів та мінімумів — математичне співвідношення між максимальним елементом скінченної множини чисел та мінімальними елементами всіх його непорожніх підмножин.

Формулювання

Нехай ${\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}\geqslant 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}$.

Див. також

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

Література

• Ross, Sheldon (2002). A First Course in Probability. Englewood Cliffs: Prentice Hall. ISBN 0-13-033851-6.