Задача по подсчету вероятности наличия у человека 2х купюр с одинаковыми номерами
В ответ на пост http://pikabu.ru/story/veroyatnosti_1_na_10_mln_5111243
Для ЛЛ: постановка задачи следующая
посчитать вероятность того что у человека будет 2 купюры с одинаковыми номерами (без букв, только число)
Если кто хочет решить сам то самое время это сделать а потом посмотреть совпал ли результат
Осторожно много математики (даже слишком)
Так как мы работаем с теорией вероятности то предполагаем что купюры с любыми номерами встречаються с одинаковой вероятностью и эта вероятность не зависит от других купюр которые мы имеем в наличии
Начнем с простого
Очевидно что если у вас в наличии всего одна или ноль купюр то 2х с одинаковыми номерами быть у вас точно не может
Если же у вас 2 купюры то вероятность того что у них одинаковый номер будет равна вероятности того что у второй купюры номер точно такой же как и у первой
А так как всего номеров есть 10 000 000 (речь идет о рублях\гривнах, для других валют просто замените 10 000 000 на количество различных номеров нужной валюты) то и вероятность 1 на 10 000 000 (что меньше чем 1 на 9 999 999 как писал автор, хотя и не на много)
Если у вас строго больше 10 000 000 купюр (сомневаюсь что у кого либо кто будет это читать есть столько купюр, но все же) то по принципу Дирихле хотя бы у 2х будет одинаковый номер
Принцип Дирихле вики: https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%BD%D1%86...
Если купюр 3 и больше то вероятность уже будет более сложной
Будет считать что у вас N купюр
Для того чтобы решить эту задачу для 3<=N<=10 000 000 посчитаем вероятность того что у всех купюр будут разные номера и отнимем от единицы данную вероятность
Очевидно что для N = 2 Эта вероятность равно 9 999 999 / 10 000 000 ( 9 999 999 - количество свободных номеров)
Если же мы человеку с двумя различными купюрами дадим 3ю то вероятность того что у 3й не будут совпадать номера с первыми двумя будет равна 9 999 998 / 10 000 000 ( потому что занято уже 2 номера )
Если дать 4ю при условии что первые 3 разные то вероятность того что и 4я не совпадет ни с какой будет 9 999 997 / 10 000 000
Ну и так дальше
Пусть f(x) = (10 000 000 - x) / 10 000 000
Очевидно что f(x) равно вероятности того что x+1 я купюра не будет совпадать ни с одной из первых x купюр при условии что первые x имеют различные номера
А вот теперь мы можем непосредственно посчитать чему равна вероятность того что x купюр будут иметь различные номера
Допустим эта вероятность равна функции g(x)
Мы знаем что если у человека уже есть x-1 различная купюра то вероятность того что при добавлении x'ой купюры она ни с какой не совпадет равна f(x-1)
А если первые x-1 различны и x'ая купюра не совпадает ни с какой из первых x-1 купюр то все x купюр различны
Исходя из этого можем вывести рекурентную зависимость
g(x) = g(x-1) * f(x-1)
а g(x-1) в свою очередь равно g(x-2)*f(x-2)
А так как мы знаем что g(1) это вероятность того что среди 1й купюры будут 2 совпадающие (чего быть не может) то g(1) будет равно 0
Тогда легко заметить что g(x) равно произведению вида f(1) * f(2) * ... * f(x-1) (по хорошему это стоит доказывать через индукцию но тогда пост будет в 2 раза больше)
Произведение вида f(1) * f(2) * ... * f(x-1) можно упростить
В каждом f в знаменателе число 10 000 000 а в числителе числа от 10 000 000 - 1 до 10 000 000 - ( x + 1 )
Тогда все это выражение имеет вид ( 9 999 999 * 9 999 998 * ... * ( 10 000 000 - ( x - 1 )))/(10 000 000 ^ (x-1)) где a ^ b это a в степени b
В свою очередь произведение ( 9 999 999 * 9 999 998 * ... * (10 000 000 - ( x - 1 ))) можно представить в виде дроби факториалов 9 999 999! / ( 10 000 000 - x )!
Тогда получим что g(x) = 9 999 999! / (( 10 000 000 - x )! * ( 10 000 000 ^ ( x - 1)))
Получили формулу вероятности того что у человека с N купюрами номера всех купюр разные и равна g(N)
Тогда вероятность того что хотя бы какие то 2 будут совпадать равна 1 - g(N) и соответственно равна 1 - (9 999 999! / (( 10 000 000 - N )! * ( 10 000 000 ^ ( N - 1))))
Для тех кому интересны конкретные числа вот пару значений вероятностей
(Приблизительные, посчитаны по формуле через wolframalpha.com)
N = 1
0
N = 2
0.0000001
N = 3
0.0000003
N = 4
0.0000006
N = 5
0.000001
N = 10
0.0000045
N = 20
0.000019
N = 50
0.000122
N = 100
0.000494
N = 200
0.002
N = 1000
0.048
N = 2000
0.18
N = 5000
0.71
N = 10000
0.99
