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

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

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

Нехай $x_1,\dots ,x_n$ — довільні дійсні числа. Тоді тотожність стверджує:

$\max (x_1,\dots ,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)+\dots +(-1{)}^{n-1}\min (x_1,\dots ,x_n)$

Аналогічне співвідношення має місце, якщо поміняти місцями мінімуми та максимуми:

$\min (x_1,\dots ,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)+\dots +(-1{)}^{n-1}\max (x_1,\dots ,x_n)$

Доказ

Доведемо, наприклад, перше з наведених співвідношень.

Зауважимо, що якщо замінити $x\mapsto x+a$, де $a$ — довільне число, то обидві частини доказуваного співвідношення також зміняться на $a$.

Дійсно, ліва частина:

$\max (x_1+a,\dots ,x_n+a)=\max (x_1,\dots ,x_n)+a$

Права частина:

$\begin{array}{cc}\sum _{k=1}^n\sum _{i_1<\dots <i_k}(-1{)}^{k-1}& \min (x_{i_1}+a,\dots ,x_{i_k}+a)=\\ & =\sum _{k=1}^n\sum _{i_1<\dots <i_k}(-1{)}^{k-1}\min (x_{i_1},\dots ,x_{i_k})+a\sum _{k=1}^n(-1{)}^{k-1}\sum _{i_1<\dots <i_k}1\end{array}$

Другий доданок в точності дорівнює $a$, в силу відомого властивості біноміальних коефіцієнтів:

$\sum _{k=1}^n(-1{)}^{k-1}\sum _{i_1<\dots <i_k}1=\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})=1$

Замінимо тепер всі $x_i$ на $x{\text{'}}_i=x_i+a$, де $a=-\min (x_1,\dots ,x_n)$. В силу вищевикладених міркувань співвідношення для набору $x{\text{'}}_i$ буде виконано тоді і лише тоді коли виконано співвідношення для набору $x_i$. Але при цьому всі $x{\text{'}}_i⩾0$, і одне або декілька чисел з набору $x{\text{'}}_i$ рівні $0$.

Якщо всі $x{\text{'}}_i=0$, то співвідношення, очевидно, вірне.

Розглянемо випадок, коли не всі $x{\text{'}}_i=0$. Нехай для визначеності $x{\text{'}}_1,\dots ,x{\text{'}}_m>0$, а $x{\text{'}}_{m+1}=\dots =x{\text{'}}_n=0$. Тоді, як легко бачити, всі нульові $x{\text{'}}_i$ можна виключити з рівності, яка, тим самим, перетворюється в

$\max (x{\text{'}}_1,\dots ,x{\text{'}}_m)=\sum _{i}x{\text{'}}_i-\sum _{i<j}\min (x{\text{'}}_i,x{\text{'}}_j)+\sum _{i<j<k}\min (x{\text{'}}_i,x{\text{'}}_j,x{\text{'}}_k)+\dots +(-1{)}^{m-1}\min (x{\text{'}}_1,\dots ,x{\text{'}}_m)$

Таким чином, співвідношення для $n$ чисел зводиться до аналогічного співвідношенню для меншої кількості $m<n$ чисел. Звідки, в силу принципу математичної індукції випливає, що вихідне співвідношення вірно для будь-якого натурального $n$.

Див. також

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

Література

• Шаблон:Cite book