0:00
Давайте разберем задачу про случайные подмножества.
Напомню, как обычно, условие, конечно: у нас есть множество,
которое состоит из N (большое) объектов.
Ну объекты можно обозначить как угодно.
Там какие-то буковки: a1, ..., aN (большое).
И вот из этого множества вытаскивается случайное подмножество.
Вернее, говорится так: давайте рассмотрим множество всех
подмножеств этого множества, и вот из этого множества,
множества всех подмножеств, возьмем один случайный элемент.
Вот это будет случайное подмножество нашего множества из N объектов.
Ну давайте я напишу, чтоб легче читалось.
Из множества всех подмножеств
выбираем случайный элемент,
то есть какое-то подмножество.
Спрашивается, с какой вероятностью вот этот случайный элемент, то есть вот
это случайное подмножество исходного множества, будет иметь четную мощность?
С какой вероятностью
случайное множество, выбранное нами,
будет иметь четную мощность,
то есть четное количество элементов?
Ну, опять,
сразу же в этой формулировке усматривается классическое определение вероятности.
То есть мы опять можем очень легко сообразить, какие элементарные исходы
образуют полную группу попарно несовместные и при этом равновероятные?
Конечно же, это просто подмножества вот этого множества.
Каждое из них мы вытаскиваем с одной и той же вероятностью.
Это следует сразу из условий, что мы взяли такой огромных мешок,
в котором лежат все возможные подмножества этого множества.
Каждое, если хотите, написано на каком-нибудь листке бумаге,
и вот мы запускаем руку в этот огромный мешок,
вытаскиваем один листочек бумаги и таким образом получаем случайное подмножество.
Конечно, это классическая схема.
Такимобразом, у нас есть какие-то элементарные
исходы: ω1, …, ω Ну и осталось понять, с каким последним индексом.
То есть для того чтобы описать пространство элементарных исходов,
нам лишь остается осознать, сколько всего у нас есть вот этих элементарных исходов.
Ну я уже занудил, конечно.
Элементарный исход – это какое-то подмножество отсюда.
Ну комбинаторно очевидно, что подмножеств в множестве, имеющем N (большое)
элементов, 2 в степени N, поэтому последний индекс будет 2 в степени N.
Ну я не знаю, для полноты картины я, конечно, могу пояснить,
почему всех возможных подмножеств данного множества 2 в степени N штук, но, по идее,
это, конечно, предполагается известным.
С другой стороны, ну почему не пояснить, действительно.
Смотрите, каждый элемент, независимо от остальных,
может как попасть в наше подмножество, так и не попасть туда.
То есть есть 2 варианта: a1 принадлежит подмножеству, a1 ему не принадлежит.
Точно так же есть 2 варианта: a2 принадлежит, a2 не принадлежит.
И так вплоть до a с индексом N.
Естественно, мы просто перемножаем эти двойки вариантов и получаем 2 в N-ой
степени подмножеств.
Итак, в нашем мешке лежит 2 в степени N подмножеств.
Мы их всех считаем равновероятными,
что следует просто из условия, потому что мы извлекаем случайный элемент.
Если мы никак не поясняем, что значит «случайный», ну значит,
равновероятно случайный.
Вот. Мы это, естественно,
по определению кладем равным 1 поделить на 2 в степени N.
А нас интересует событие, которое состоит в том,
что наше случайное множество имеет четную мощность.
Вот давайте это событие обозначим буквой A.
Это будет множество тех элементарных исходов,
которые имеют четную мощность.
Ну мощность обычно принято обозначать модулем количества элементов в множестве.
Вот мы хотим, чтобы это число было четным, то есть делилось пополам.
Итак, нам благоприятствуют все возможные подмножества N (большое)
элементного множества, которые имеют четную мощность.
Так, друзья, ну вот как можно посчитать вероятность?
Надо, естественно, разделить количество элементарных исходов,
которые входят в множество A, то есть благоприятствуют этому событию,
на общее количество элементарных исходов, каковых – ничто, естественно,
не изменилось – 2 в степени N (большое), как и было.
То есть наша цель – посчитать, сколько есть подмножеств, имеющих четную мощность,
в множестве, которое состоит из N (большое) элементов.
Ну можно на этом пути действовать по-разному.
Можно пойти по сложному пути.
Можно пойти по более простому.
Ясно, что в итоге все равно получится некое комбинаторное тождество.
Ну вот товарищи, которые изучали комбинаторику, – а это, по идее,
очень полезно перед тем, как изучать вероятность, – они, конечно, знают,
как такие тождества можно доказывать.
Ну о чем я говорю?
Конечно, можно перебрать просто все случаи.
Можно посмотреть сначала на подмножества...
А кстати, а что значит сначала?
Вот какие, вообще, бывают подмножества четной мощности?
Я вот подозреваю, что могут быть слушатели,
которые не догадываются о существовании очень простого
подмножества четной мощности, а именно пустого подмножества.
Ведь когда мы говорим, что всего подмножеств 2 в степени N, мы,
естественно, предполагаем, что среди подмножеств встречается и пустое.
То есть этот тот случай, когда мы и a1 не включали в наше подмножество,
и a2 не включали в наше подмножество, и aN не включали.
Никого не включали.
Пустое множество.
Оно, естественно, входит вот в это количество 2 в степени N.
Оно там учтено.
То есть пустое множество оно какую мощность имеет?
Ноль, а ноль – это четное число.
Значит, самая простая ситуация – это, конечно, посчитать пустые множества.
Ну пустых множеств, понятное дело, C из N по 0, и как не крути, это просто 1.
Одно единственное на свете есть пустое множество,
и я просто так записал эту единицу, мне удобнее.
Дальше я могу посмотреть на все возможные двухэлементные подмножества,
тут я думаю уже никакой путаницы с осознанием не происходит.
Вот про пустое множество могли забыть, а про двухэлементное никто не забудет.
Дальше C из N по 4, и так далее.
Ну и какое будет последнее слагаемое, это, конечно,
зависит от четности самого числа N (большое).
Понятно, что если N (большое) четное,
то последнее слагаемое будет C из N по N (большое), но это в случае,
если оно четное, а если оно нечетное, тогда последнее слагаемое будет такое.
Но это какой-то некрасивый ответ.
Как-то вот он не очень удовлетворяет.
Эстетически не радует.
Катарсис не получается, да?
Какой-то странный ответ: в зависимости от четности числа N (большое) то ли
здесь стоит сумма вот досюда, то ли здесь стоит сумма вот досюда,
и еще она делится на 2 в степени N.
Ну можно посчитать по-другому.
Радость состоит в том, что можно написать не такую омерзительную формулу,
которая зависит от случаев, а можно посчитать по-другому.
Вот как.
Значит, смотрите: что значит набрать множество четной мощности,
подмножества множества из N (большое) элементов?
Можно действовать так: совершенно произвольно поступить по отношению
к элементу a1, то есть либо положить его в строящееся множество, либо не положить.
Ну два способа, как отнестись к элементу a1.
Точно так же поступить по отношению к элементу a2: положить или не положить.
Тоже два способа.
Без вариантов.
И так далее.
Ну, естественно, мы так не можем дойти до элемента с номером N (большое),
потому что если мы будем наплевательски относиться к делу, то может получиться как
множество четной мощности, так и множество нечетной мощности.
Поэтому давайте дойдем только до элемента с номером (N – 1).
К нему применим два стандартных способа, – то есть либо положим его в строящееся
множество, либо не положим, – а затем переведем дыхание и посмотрим, что
у нас получилось на выходе в результате вот этих вот альтернатив, так сказать.
На выходе могло получиться множество четной мощности.
Но тогда, очевидно, элемент a с индексом N в него добавлять уже никак нельзя,
потому что получится множество нечетной мощности после добавления a с индексом N.
И наоборот, могло получиться множество нечетной мощности,
то есть это как бы нехорошо.
Но тогда, однозначно, надо к нему просто прибавить элемент a с индектом N
(большое), и уже вместе с ним, опять-таки, получится множество четной мощности.
То есть есть всего 2 в степени (N –
1) способов выбрать первые (N – 1) элементов,
и для каждого из таких способов есть однозначный путь добавления элемента
a с индексом N так, чтобы в итоге получилось множество четной мощности.
Ну понятно, что таким образом четно мощных множеств 2 в степени (N – 1).
И мы получаем в итоге 2 в степени (N – 1) поделить на 2 в степени N,
и это равняется ½, что куда приятнее, нежели какая-то странная сумма,
зависящая от случаев, поделенная на 2 в степени N.
Оказывается, эта странная сумма просто равняется 2 в (N – 1) всегда.
И поэтому вероятность получается равной ½.
Ну, опять-таки, этот результат можно было получить как-то более быстро
путем каких-то определенных ручных махинаций.
Я об этом, наверное, сейчас говорить уже не стану, потому что то,
что я сейчас рассказал, это, опять-таки, абсолютно формализованный подход,
который позволяет с гарантией прийти к правильному ответу.
Не угадать его, там, руководствуясь какими-то, может быть,
очень красивыми олимпиадными соображениями,
а вот кондово тупо решить независимо от того, там, как ты соображаешь.
Вот просто взять и подставить в определение классической вероятности в
знаменатель – общее количество элементарных исходов,
а в числитель – количество тех элементарных исходов,
которые благоприятствуют нашему событию.
Ну я думаю, что все.