Тождество максимумов и минимумов — математическое соотношение между максимальным элементом конечного множества чисел и минимальными элементами всех его непустых подмножеств.
Формулировка Пусть — произвольные действительные числа. Тогда тождество утверждает:
Аналогичное соотношение имеет место, если поменять местами минимумы и максимумы:
Доказательство Докажем, например, первое из приведённых соотношений.
Заметим, что если заменить , где — произвольное число, то обе части доказываемого соотношения также изменятся на .
Действительно, левая часть:
Правая часть:
Второе слагаемое в точности равно , в силу известного свойства биномиальных коэффициентов:
Заменим теперь все на , где . В силу вышеизложенных соображений соотношение для набора будет выполнено тогда и только тогда, когда выполнено соотношение для набора . Но при этом все , и одно или несколько чисел из набора равны .
Если все , то соотношение, очевидно, выполнено.
Рассмотрим случай, когда не все . Пусть для определённости , а . Тогда, как легко видеть, все нулевые можно исключить из равенства, которое таким образом превращается в
Таким образом, мы свели соотношение для чисел к аналогичному соотношению для меньшего количества чисел. Отсюда в силу принципа математической индукции следует, что исходное соотношение верно для любого натурального .
Применение к проблеме коллекционера вкладышей Одна из классических задач статистики о времени, необходимом для того, что бы собрать k разных вкладышей (например, из жвачки) из n возможных. Если вероятность получить какой-то конкретный вкладыш одинакова (в каждой жвачке есть вкладыш и они полностью случайно распределены), то такую задачу можно решить с помощью индукции: собрав i вкладышей вы остаетесь с задачей о собрании k-i вкладышей и так далее. Однако решение можно переформулировать с помощью формулы максимумов и минимумов: максимумом тут является время для собирания k вкладышей, а минимумом – время до появления у вас в руках первого из искомого набора из k вкладышей, которое в данном случае статистически одинаково для любого вкладыша из набора и зависит только от размера набора.
Значение тождества здесь проявляется в том, что в случае, когда есть редкие вкладыши и вероятности получения конкретных вкладышей различаются, первый (простой) способ решения уже не годится, а тождество максимумов и минимумов сохраняет свою силу.
См. также Формула включений-исключений
Литература 7.2.2 The Maximum-Minimums Identity // Ross, Sheldon M. A first course in probability. — 8th ed. — Pearson. — pp. 313—314. — ISBN 978-0-13-603313-4
Категория:Тождества Категория:Арифметика