Привет, Andy77!
A>допустим, у нас есть М карт. Какова вероятность того, что при K попытках выбрать случайную карту мы получим хоть один дубликат? Тривиально, 1 — ((M)! / (M^K * (M-K)!))
A>сколько разных карт должно быть в колоде, чтобы при k попытках вероятность появления дубликата была p1?
Пусть K > 2.
q = 1 — p1
q >= (1-1/M)(1-2/M)...(1-(K-1)/M)
Можно решать перебором по M.
Можно еще так. Если M > k, формула Стирлинга для факториала n! = (n/e)^n * sqrt(2pi*n) несколько упрощает задачу (относительная погрешность формулы, начиная с 3 не превышает 3%, начиная с 5 — 2%, начиная с 8 — 1%). Это приближение тем более годится, что у нас требуется найти целое M, поэтому в итоге в большинстве случаев мы получим правильный ответ (после итогового округления).
q >= (M / (M-k))^(M-k+1/2) * e^(-k)
1/k * lnq + 1 >= (M/k - 1 + 1/(2k)) * ln((M/k) / (M/k - 1))
x = M/k - 1
1/k * lnq + 1 >= (x + 1/(2k)) * ln(1 + 1/x)
x перебираем по значениям n/k, n — натуральное.
Последнее неравенство можно решать иначе, воспользовавшись тем, что справа в нем стоит монотонная функция по x. Существует достаточно способов в данном случае.
Свёл вот одну проблему к простенькой задачке по ТВ, а саму ТВ и забыл... (на примере с картами) —
допустим, у нас есть М карт. Какова вероятность того, что при K попытках выбрать случайную карту мы получим хоть один дубликат? Тривиально, 1 — ((M)! / (M^K * (M-K)!))
Теперь нужно конструктивно решить обратную задачу —
сколько разных карт должно быть в колоде, чтобы при k попытках вероятность появления дубликата была p1?
чувствую, что плохо описал задачу... аналоги —
Найти кол-во детей в таком классе, что-бы вероятность совпадения месяца рождения (k=12) у них была p1
Найти кол-во N элементов множества, при котором вероятность получения хотя бы одного повтора при k попытках выбрать случайный элемент будет равна p1, точнее (min(n) : p(k, n) > p1)
Apapa.gif)
