04.09.2025 07:00
violent_muse 19 3500 Источник

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

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

Василий поступил в университет и впервые встретил свою группу. Всего в группе 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 человек. Вася уже отобран в одну из них. Какова вероятность, что он не окажется в одной команде с Петей?

Есть два способа: покороче и подлиннее.
Сначала короткий: в Васиной команде осталось 5 мест, на них претендуют 19 человек (в том числе Петя).

Значит, вероятность того, что Петя попадёт в эту же команду, равна \dfrac{5}{19}\approx 0.263.
И тогдаP(Петя\ не\ оказался\ в\ команде\ Васи) \approx 1-0.263=0.737.

А тут длинный вариант.


Не оказаться в одной команде с Петей можно в двух случаях: когда Петю отобрали во вторую команду или когда Петя не оказался ни в одной из них. Можно посчитать эти два случая отдельно, а можно вычесть из 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 остальным людям. Мы как бы представляем, что Вася уже получил заветный нолик и жеребьевка происходит только среди остальных. Подставляем эти значения в формулу с суммой и записываем это все в числитель.

  • Число вообще всех допустимых распределений, судьба Васи может быть какая угодно. Тогда k=10 распределены по n=20 людям.

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

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

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

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

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

\dfrac {5\ 222\ 264}{8 \ 533\  660}=\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. Ну красота же!

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

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


  1. axion-1
    04.09.2025 12:29
    #28795968

    По третьей задаче, нужны ли здесь вообще сочетания? Отбираем случайным образом 5 человек из 19, вероятность того что среди них окажется Петя будет равна 5/19


    1. violent_muse Автор
      04.09.2025 12:29
      #28796082

      Вообще да, вы правы, можно обойтись просто таким рассуждением ))
      Добавлю это в пост, спасибо!


  1. WASD1
    04.09.2025 12:29
    #28797408

    Ох.. сначала хотел написать про частности формулировок, потом появилась эта сентенция.

    У вас некоторые задачи (в частности 2 и 3) - плохо сформулированы.
    Совет - не примите его за назидание - найдите в ВК группу Константина Кнопа (это автор задач и член жури школьного математического движения) "математические задачи и головоломки" и посмотрите как там формулируются задачи на вероятности, и какие замечания профессионалы выдвигают, когда мы с вами, обыватели, неаккуратно их формулируем.
    Вам будет полезно, поверьте.


    ==============================
    1. Главного героя должны звать не Вася, а Петя (это соответствует русскоязычной традиции именования героев задач на вероятности - подобно традиции "Алиса" и "Боб" в англоязычных источниках).

    2. В задаче 2 идея и решения основаны на предположении: события "студент решил задачу №_X" и "студент решил задачу №_Y" независимы.
    В реальном мире это не так.
    Соответственно надо или аккуратно переформулировать задачу.
    Или решить задачу для зависимых событий и посмотреть - уйдёт ли условная вероятность "решил задачу №_X при условии решил задачу №_Y" из конечной формулы или нет - с ходу видится, что решение не тривиальное.


    3. В задаче 3 сентенция "Вася уже отобран в команду" - лишняя и сбивающая с толку. Намеренное сбивание решающего с толку - допустимо и поощряется в головоломках, но является плохой практикой для задач (если только не стоит какая-то цель столкнуть ученика с парадоксом, мнимым или реальным, - здесь этой цели нет).


    1. Germanjon
      04.09.2025 12:29
      #28798296

      В задаче 3 сентенция "Вася уже отобран в команду" - лишняя и сбивающая с толку.

      Возможно я чего-то недопонял, но факт отбора в команду Васи - важен. Ибо есть вероятность 8/20, что он не попадёт ни в одну из команд и тогда ответ будет совсем другим


      1. WASD1
        04.09.2025 12:29
        #28799558

        Ой чёрт, согласен.
        My fault.


    1. violent_muse Автор
      04.09.2025 12:29
      #28801308

      Как вы легко и непринуждённо меня отнесли к обывателям, однако.

      1) Про имена — вы это серьёзно? Никому нельзя использовать другие имена? Про традицию в курсе, но лично меня уже слегка мутит от одних и тех же (особенно в англоязычном мире), это же уже просто невозможно.
      2) Да, можно было бы это дописать, но обычно если про это нет данных, то события считаем независимыми.
      3) Про это вам уже ответили


      1. WASD1
        04.09.2025 12:29
        #28802294

        Как вы легко и непринуждённо меня отнесли к обывателям, однако.

        Если вы сами решили заострить внимание - давайте просто подсчитаем число неаккуратностей и ошибок.

        1. Нарушение устоявшихся соглашений с именами (такие имена даются для того, чтобы читатель не путался. Петя - П - первый. Вася - В - второй)

        2.Задача 2 - модель задачи явно не соответствует реальному миру (и ваше оправдание уровня "3.5 землекопа потому, что в задачах на деление поразумеваются рациональные числа").

        3. Задача 3 - Громоздкое условие на ровном месте ни чего не добавляющее задаче. Вместо "Всю группу разделили на 2 равные команды" " Из всей группы набирают две волейбольные команды, каждая по 6 человек. Вася уже отобран в одну из них".

        4. Задача 4 - решение неверное(если судить как профессионала), или "неаккуратность в решении", если судить как обывателя.
        Вероятностное пространство задано в условии одним образом. Вероятностное пространство в обоих решениях используется другим образом.


  1. WASD1
    04.09.2025 12:29
    #28797502


    1. violent_muse Автор
      04.09.2025 12:29
      #28801364

      Да, вы правы, можно просто собрать знаменатель вместе, но мне хотелось рассмотреть случаи отдельно.
      Но добавлю про это.


  1. WASD1
    04.09.2025 12:29
    #28797544

    Генеративное решение решает другую (возможно эквивалентную) задачу.
    Численный ответ тот же. Но без доказательства, что мы решаем ту же задачу такое применение - близко к ошибке.

    Решение-1 -- Вася написал алгоритм, который выдаёт каждому студенту число 0 или 1 или 2. (сумма всех 20 чисел == 10).
    Решение-2 -- Вася написал алгоритм, который дважды выдаёт каждому студенту число 0 или 1 (сумма всех 40 чисел == 10).

    И отдельно требуется доказать, что Решение-2 - применима (т.е. оба сформулированных условия эквивалентны).


    1. violent_muse Автор
      04.09.2025 12:29
      #28801320

      Почему во втором решении алгоритм выдаёт число дважды?


      1. WASD1
        04.09.2025 12:29
        #28802370

        (x^2 + x +1)*(x^2 * x + 1) = ..... x^2 + x×x + x^2

        Какое условие должно быть наложено на пространство вероятностей, чтобы вы имели право складывать x^2 (одного человека) и x×x (двух разных людей)?


  1. homm
    04.09.2025 12:29
    #28797572

    Вася написал код, который выдает каждому человеку в группе число от 0 до 2 (сколько раз ты будешь старостой).

    Так по какому принципу код выдает эти числа?


    1. violent_muse Автор
      04.09.2025 12:29
      #28801284

      Случайно и одномоментно, но таким образом, чтобы сумма всех выданных чисел была равна 10


      1. homm
        04.09.2025 12:29
        #28804310

        А с чего вы взяли, что при таком подходе у всех допустимых распределений будет одинаковая вероятность появления? Вот вам сходу два алгоритма, которые «Случайно и одномоментно» выдают каждому участнику группы числа от 0 до 2:

        from random import randint
from collections import Counter

def dist_rand_prob(group, _sum):
    while True:
        probs = [randint(0, 2) for _ in range(group)]
        if sum(probs) == _sum:
            yield probs

def dist_rand_sample(group, _sum):
    while True:
        probs = [0] * group
        while sum(probs) < _sum:
            pos = randint(0, group - 1)
            if probs[pos] < 2:
                probs[pos] += 1
        yield probs

        Если посчитать для обоих алгоритмов распределение количества учеников, которых «пронесет», оно получится кардинально разным:

        it = dist_rand_prob(20, 10)
Counter(next(it).count(0) for _ in range(5000))

Counter({10: 114, 11: 875, 12: 2051, 13: 1585, 14: 367, 15: 8})

it = dist_rand_sample(20, 10)
Counter(next(it).count(0) for _ in range(5000))

Counter({10: 317, 11: 1539, 12: 2075, 13: 967, 14: 99, 15: 3})

        А уж пронесет ли конкретного Васю, явно зависит от этого распределения.


        1. violent_muse Автор
          04.09.2025 12:29
          #28804430

          Поэтому в задаче тактично умалчивается, что это за алгоритм )) Но сказано, что он справедливый, то есть какой надо.

          Видимо, на хабре если упомянул алгоритм, то будь добр предоставить


          1. WASD1
            04.09.2025 12:29
            #28804504

            У вас в условии один алгоритм (справедливый), а в решении уже другой, с гораздо более сильными требованиями

            Не правда, ли, что оба представленных распределения удовлетворяют критерию честности, но в одном (честном) распределении вероятность получить 0 дежурств = 0.5. А во втором (опять же честном) распределении вероятность получить 0 дежурств = 0.75?

            import random

# fair distribution of 2 given 5_times - 0 duties probability == 0.75
def fair_distribution_1():
    return [ (2 if i < 5 else 0) for i in range(20) ]

# fair distribution of 1 given 10_times - 0 duties probability == 0.5
def fair_distribution_2():
	return [ (1 if i < 10 else 0) for i in range(20) ]

names = [ "Vasya", "Petya"] + ["number" + str(i) for i in range(2, 20) ]
# Isn't it true, than in two below fair cases probability to get exactly 0 duties is different?
marks = fair_distribution_1()
#marks = fair_distribution_2()

random.shuffle(marks)
res = zip( names, marks)
print( *res)


            Видимо, на хабре если упомянул алгоритм, то будь добр предоставить

            На хабре понимают, что условие должно быть однозначным . А ваше - нет, т.к. алгоритмов, удовлетворяющих вашему условию, но выдающих разные распределения больше одного.

            На самом деле написать императивный алгоритм - гораздо проще, чем составить однозначное дискриптивное условие.

            Вы уверены, что сарказм, относительно @homm который пытался вам помочь выше - хорошая стратегия?


          1. homm
            04.09.2025 12:29
            #28804570

            Поэтому в задаче тактично умалчивается, что это за алгоритм

            Почему поэтому? Чтобы можно было в случае верного решения для другого алгоритма сказать, что решение неверное?

            то есть какой надо.

            Какой надо кому? Я же уточнил какой алгоритм, вы сказали требования. Я вам привел два разных, удовлетворяющих требованию. Так откуда знать какой надо?


  1. muxa_ru
    04.09.2025 12:29
    #28804806

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

    А если среди оставшихся 19 есть две пары совпадений дней рождения?