MCP

воскресенье, 6 ноября 2016 г.

Задача на вероятность

Тут недавно возникла в голове задача по теории вероятности, задал её в твиттере, но из-за ограничений его формата меня, видно не очень поняли. Несмотря на то, что я забыл терверы, пришлось их упорно вспоминать, чтобы решить самостоятельно   или хотя бы приблизиться к решению. При этом казалось, что я хожу по очевидной и банальной проблеме, но никак не мог подобрать правильные слова для гугла. В общем, вроде бы решил, но если кто лучше помнит всё это, может прокомментирует с подсказками, куда смотреть и как всё это называется.

Собственно, сама задача. Сформулирую её приближенно к реальности, чтобы было понятнее.

У нас есть условный Киндер-Сюрприз и мы знаем, что в нём есть n различных вариантов игрушек, мы купили k киндеров (k ≥ n). Какая вероятность того, что мы соберём всю коллекцию игрушек? 

Подумайте над решением, задача мне понравилась в итоге... Для тех, кто не хочет думать, решение ниже.





Итак, моё решение. Я руководствовался такими соображениями:
  • Всего вариантов набрать k киндеров из n вариантов nk, т.е. размещения с повторениями, если верить Wiki, а фактически число длиной k из n цифр. Т.е. если у нас есть 10 различных игрушек, мы можем считать их цифрами и выкладывать числа.
  • Нам по факту надо посчитать количество чисел длиной k, которое состоит из различных цифр. Т.е. если есть цифры 0, 1, 2 и число длиной 4, то нам подходят 2110, 2001, 0021, но не подходят 1110, 2212 и прочие.
  • Попробуем посчитать количество чисел, у которых меньше чем n разных цифр. Их будет (n-1)k * n. Т.е. исключаем одну цифру, получаем (n-1)k вариантов. А цифр мы можем исключить n.
  • Вроде всё хорошо... но есть нюанс. В данной формуле мы несколько раз посчитали числа, у которых чисел меньше чем n-1. Т.е. их надо добавить в эту формулу.
  • А когда мы их будем добавлять, мы добавим лишнего, и нам надо будет исключать...
Короче, в итоге моя формула выглядит так:
((nk - (n-1)k * C(n, n-1) + (n-2)k * C(n, n-2) - .... + 1k * C(n, 1)) / nk

Где C(n, k) - число сочетаний.
Т.е. если у нас есть 3 разных киндера, и мы берём 4, то всего у нас есть 81 вариант, нам подходит:
((81 - (2)4 * 3 + (1)4 * 3) / 81 = 36 / 81 = 0.4444

Т.е. вероятность меньше 0.5, для остальных можно посчитать ручками.

Что мне не нравится в этой формуле? Ощущение что она некрасивая и неоптимальная, или я как обычно изобрёл велосипед чего-то известного. В общем, жду комментариев.

2 комментария:

  1. Практика показывает, что события выпадения определённой игрушки не равновероятны, иначе бы собрать всю коллекцию было достаточно просто.

    ОтветитьУдалить
    Ответы
    1. Это да. Но меня именно с такой абстрактной задачей всё интересует. Надо довести всё до идеала, а потом страдать от несовершенства мира :)

      Удалить