04.09.2025 07:00
violent_muse 0 777 Источник

Привет! К первому сентября я публиковала вот такую задачку. Самое время обсудить решения.

Для начала вспомним основное условие.

Василий поступил в университет и впервые встретил свою группу. Всего в группе 20 человек (включая Васю). Он решает впечатлить всех своими знаниями теорвера и посчитать несколько интересных вещей.

1. Какова вероятность, что хотя бы у одного одногруппника день и месяц рождения совпадут с Васиными?

Для упрощения возьмем невисокосный год, числа от этого не сильно поменяются. Тогда вероятность, что у какого-то человека день рождения не совпадает с ним, равна 364/365. Для 19 человек вероятность не совпасть с ним.

\left(\dfrac{364}{365}\right)^{19}\approx 0.9492.

Значит, вероятность хотя бы одного совпадения с ним будет 1 - 0.9492 \approx 0.051 или 5.1 \%.

Тут стоит отметить, что это задача не на классический парадокс дней рождения, там бы спрашивалось про совпадение дней рождений хотя бы у какой-то пары и вероятность была бы порядка 41%. А нас интересовало совпадение именно с Васей, поэтому нет ни подвоха, ни парадокса, ну и вероятность ожидаемо низкая.

2. В первый же день все пишут тест, в нем 10 задач, решение надо сдать в виде текста. Проверяет этот тест специально обученный AI, причем вероятность, что он засчитает неверный ответ как верный, равна 2%, а вероятность, что верный ответ не засчитается — 0,5%. Статистика за предыдущие годы говорит, что в среднем вероятность решить каждую из задач теста равна 70%. В итоге Вася получил 10 из 10, ура! Но какова вероятность, что он действительно решил все задачи верно?

Если Вася получил за конкретную задачу плюсик, то это либо потому, что она правда решена верно, либо это ложноположительный результат. Вероятности этих двух случаев (на картинке они розовые) надо сложить, при этом учитываем вероятность вообще пойти по этой ветке, получим 0.7\cdot 0.995+0.3\cdot0.02=0.6965+0.006=0.7025.

Тогда вероятность того, что задача действительно решена правильно, равна \dfrac{0.6965}{0.7025}\approx0.9915, что как будто не так плохо. Здесь мы делили «хорошие» исходы на все возможные.

А теперь нам надо возвести это в десятую степень, так как задачек в тесте было 10, и мы считаем, что решение каждой — независимое событие (так как не указано иное).

Получим 0.9915^{10}\approx0.9182, то есть меньше 92%, что уже чуть менее приятно.

Можно также расписать через условную вероятность, идея там та же, но мне больше нравится через дерево, так как можно быстро объяснить решение на уровне школьной программы.

3. С первого же дня Васе не понравился Петя, он тоже написал тест на 10 из 10 и вообще какой-то неприятный. Из всей группы набирают две волейбольные команды, каждая по 6 человек. Вася уже отобран в одну из них. Какова вероятность, что он не окажется в одной команде с Петей?

Не оказаться в одной команде с Петей можно в двух случаях: когда Петю отобрали во вторую команду или когда Петя не оказался ни в одной из них. Можно посчитать эти два случая отдельно, а можно вычесть из 1 вероятность того, что они все-таки оказались в одной команде.

Сколько всего есть способов собрать команду для Васи? Надо выбрать 5 человек из 19, порядок тут не важен, так что считаем через сочетания:

C_{19}^5=\dfrac{19!}{14!\cdot5!}=11\ 628.

А сколько есть способов дособрать команду, если там уже есть Вася и Петя? Надо выбрать 4 человека из 18:

C_{18}^4=\dfrac{18!}{14!\cdot4!}=3060.

Значит, P(Петя\ с\ Васей \ в\ одной\ команде) = \dfrac{C_{18}^4}{C_{19}^5}=\dfrac{3060}{11\ 628}=\dfrac{5}{19}\approx 0.263.

Тут, кстати, можно было считать прямо в факториалах, очень красиво все сокращается. И отсюда P(Петя\ не\ оказался\ в\ команде\ Васи) \approx 1-0.263=0.737.

4. Университет требует назначить старосту группы, но никто не хочет брать на себя эту роль. Ребята решили, что это будет сменная должность — на каждый из 10 учебных месяцев этого года будет свой староста, при этом один человек может быть старостой не больше двух раз за год. Вася написал код, который выдает каждому человеку в группе число от 0 до 2 (сколько раз ты будешь старостой). Кто в какой месяц, неважно, это они решат между собой потом. Код честный и корректный, даже Петя зааппрувил. Какова вероятность, что Вася не будет старостой ни разу за год?

Для начала — кратко про две идеи, через которые можно решать.

При этой жеребьевке каждому из студентов группы достанется число 0, 1 или 2. Если мы хотим, чтобы Вася не был старостой ни разу, то все единички и двоечки должны достаться другим людям. То есть нас интересует отношение:

\dfrac{\text{число допустимых распределений без Васи}}{\text{число вообще всех допустимых распределений }}.

И есть два способа посчитать эти распределения — классический комбинаторный и через генератриссу. Разберем оба.

1) Комбинаторно

Так как жеребьевка сразу раздает все людям числа x_i∈ \{0,1,2\}, допустимыми распределениями будут такие, что x_1 + x_2 + ... + x_n = 10, при этом двоечек будет не больше 5 штук. Нам нужно будет узнать количество подходящих векторов вида (x_1{,}\ x_2 {,}\ ... {,}\ x_n).

Общее количество людей обозначим за n, у нас будет разным для числителя и знаменателя, поэтому пока пишем в общем виде.

Количество месяцев, которые распределяем, обозначим за k, а людей, получивших двойку, — за t. Тогда единичек должно быть k-2t штук, остальные нули.

Дальше следим за руками, нам нужно несколько вещей.

  • выбрать тех, кто получил двойку, — есть C_n^t способов это сделать;

  • из оставшихся n−t человек выбрать k−2t человек, которые получили единичку, для этого есть C_{n-t}^{k-2t} способов;

  • остальные n−t−(k-2t)=n-k-3t человек получат нолики.

Заметим, что t∈ [0; [k/2]], здесь [k/2] — это целая часть от числа k/2. Мы будем как бы мысленно сначала распределять двойки (которых t штук), а потом для каждого такого значения t распределять оставшиеся k-2t единичек.

Итого количество подходящих нам векторов считается по формуле:

\displaystyle\sum_{t=0}^{[k/2]} C_{n}^{t}\cdot C_{n-t}^{k-2t} \tag 1

Выглядит довольно страшно, но по сути тут просто формула произведения и суммирование для разных вариантов t.

Можно убедиться на маленьких значениях, что формула работает верно

Пусть n=3 и k=2. Тогда:

  • при t=0 никто не получает двоечку, и мы выбираем 2 человек, которые получат по единичке, есть всего 3 варианта: (1,1,0), (1,0,1), (0,1,1);

  • при t=1 один человек получает двоечку и остальные нули, то есть выбрать надо только одного с двойкой, тут тоже 3 варианта: (2,0,0), (0,2,0), (0,0,2).

Итого 6 вариантов.

А по формуле у нас было бы:

\displaystyle\sum_{t=0}^{[2/2]} C_{3}^{t}\cdot C_{3-t}^{2-2t}=\displaystyle\sum_{t=0}^{1} C_{3}^{t}\cdot C_{3-t}^{2-2t}=C_{3}^{0}\cdot C_{3}^{2}+C_{3}^{1}\cdot C_{2}^{0}= 1 \cdot 3 + 3\cdot1=6.

Сошлось!

Теперь давайте поймем, как эта формула применяется к искомой вероятности, равной

\dfrac{\text{число допустимых распределений без Васи}}{\text{число вообще всех допустимых распределений }}.

  • Число допустимых распределений, когда Вася не выбран ни разу, — это когда все k=10 распределены по n=19 остальным людям. Мы как бы представляем, что Вася уже получил заветный нолик и жеребьевка происходит только среди остальных. Подставляем эти значения в формулу с суммой и записываем это все в числитель.

  • Знаменатель будет складываться из трех «фиксированных» случаев для 19 оставшихся людей, в зависимости от того, какое число достанется Васе:

    • если ему достался нолик ⇒ остальные числа дают сумму 10 ⇒ подставляем k=10 и n=19 в формулу (1), как в предыдущем случае;

    • если ему досталась единичка ⇒ остальные числа дают сумму 9 ⇒ подставляем k=9 и n=19 в формулу (1);

    • если ему досталась двойка ⇒ остальные числа дают сумму 8 ⇒ подставляем k=8 и n=19 в формулу (1).

  • Итого получаем вот такого монстра:

\dfrac{\text{число допустимых распределений без Васи}}{\text{число вообще всех допустимых распределений }} =\dfrac {\displaystyle\sum_{t=0}^{5} C_{19}^{t}\cdot C_{19-t}^{10-2t}}{\displaystyle\sum_{t=0}^{5} C_{19}^{t}\cdot C_{19-t}^{10-2t}+\displaystyle\sum_{t=0}^{4} C_{19}^{t}\cdot C_{19-t}^{9-2t}+\displaystyle\sum_{t=0}^{4} C_{19}^{t}\cdot C_{19-t}^{8-2t}}.

А дальше надо всего-навсего это посчитать (нервный смех). Лучше не руками, конечно, хотя кто я такая, чтобы вам запрещать.

Через Вольфрам можно посчитать отдельно каждое слагаемое — например, вот числитель.

В итоге получится:

\dfrac {5\ 222\ 264}{5\ 222\ 264+2\ 355\ 962+955\ 434}=\dfrac {4042}{ 6605}​≈0.612, то есть около 61.2%.

2) Через генератриссу

В комбинаторике есть штука под названием генератрисса, она же производящая функция. Мне очень нравится высказывание о ней, которое говорит, что она похожа на мешок или сумку — вместо того, чтобы тащить много маленьких отдельных объектов, и тогда нам становится сильно удобнее, ведь теперь мы несем только один предмет, эту сумку. Я не буду рассказывать о ней подробно, можно почитать на английской «Википедии», можно почитать еще вот эту статью на Хабре и вот эту.

В нашу производящую функцию мы закодируем/запакуем все, что нам нужно, а потом просто достанем нужные коэффициенты. Для каждого человека сконструируем такой многочлен, где степень переменной будет означать полученное в жеребьевке число:

  • если он вытянул нолик ⇒ слагаемое 1;

  • если вытянул единичку ⇒ слагаемое x;

  • если вытянул двойку ⇒ слагаемое x^2.

Тогда для одного человека все варианты описываются многочленом 1+x+x^2. Для n независимых людей получим многочлен (1+x+x^2)^n.

Если раскрыть эту скобку со степенью и посмотреть коэффициент при z^k, то он будет в точности равен числу способов получить суммарно k «назначений» (т. е. число решений x_1+...+x_n=k). И это прям ровно то же самое, что мы только что считали комбинированно: коэффициент при x^k в (1+x+x^2)^n равен количеству подходящих векторов вида (x_1{,}\ x_2 {,}\ ... {,}\ x_n).

Выше под катом/тогглом был пример с n=3 и k=2, и там формула \displaystyle\sum_{t=0}^{[k/2]} C_{n}^{t}\cdot C_{n-t}^{k-2t} давала значение 6. Проверим через генератриссу: ищем коэффициент при x^2 в многочлене (1+x+x^2)^3.

Если раскрыть эту скобку, получится x^6 + 3 x^5 + 6 x^4 + 7 x^3 + 6 x^2 + 3 x + 1, и коэффициент при x^2 действительно равен 6, сошлось!

А в случае нашей исходной задачи про Васю для нахождения вероятности нам понадобится:

  • в числителе коэффициент при x^{10} в многочлене (1+x+x^2)^{19}

  • в знаменателе коэффициент при x^{10} в многочлене (1+x+x^2)^{20}

Раскрыть можно тоже через Вольфрам — например, получим снова

\dfrac{5\ 222\ 264}{8\ 533\ 660}=\dfrac {4042}{ 6605}​≈0.612. Ну красота же!

На этом у меня все. Спасибо за внимание!

Комментарии (0)