Свёл вот одну проблему к простенькой задачке по ТВ, а саму ТВ и забыл... (на примере с картами) —

допустим, у нас есть М карт. Какова вероятность того, что при K попытках выбрать случайную карту мы получим хоть один дубликат? Тривиально, 1 — ((M)! / (M^K * (M-K)!))

Теперь нужно конструктивно решить обратную задачу —

сколько разных карт должно быть в колоде, чтобы при k попытках вероятность появления дубликата была p1?

чувствую, что плохо описал задачу... аналоги —

Найти кол-во детей в таком классе, что-бы вероятность совпадения месяца рождения (k=12) у них была p1

Найти кол-во N элементов множества, при котором вероятность получения хотя бы одного повтора при k попытках выбрать случайный элемент будет равна p1, точнее (min(n) : p(k, n) > p1)

e=1/k
p0=k (k-1)...(k-n+1)/k^n=
1 (1-e) (1-2e)...(1-(n-1)e) \approx
1-e(1+2+...n-1)=1-en/2=1-n/(2k)

?

Привет, 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. Существует достаточно способов в данном случае.