---
# math

原題:
- 現在有兩組人，如果我要讓 "某一組人中的某個人和另一組中的某個人有相同的生日" 的機率 >= 0.5，請問這兩組人至少要有多少人才夠？

----------------
Lemma 1:
- 假設有現在有 n 個人，則共有 x 種不同的生日的機率是 $\dfrac{C_x^{365}*H_{n-x}^{x}}{365^n}$

Proof of Lemma 1:
題目等價於，從 365 天中選出 x 天，然後把 n 個人分到這 x 天，且每天至少有一個人

--------------

令 $\lambda(n, x) = \dfrac{C_x^{365}*H_{n-x}^{x}}{365^n}$

回到原題，假設有 A B 兩組人，各有 a 和 b 個人，擇在固定 a 的情況下，要滿足原題，b 需要滿足的條件為
$$\sum_{i=1}^a \lambda(a, i)*(1-(\dfrac{365-i}{365})^b) >= 0.5$$
因為$\sum_{i=1}^a \lambda(a, i) = 1$, 化簡後得到
$$\sum_{i=1}^a \lambda(a, i)*(\dfrac{365-i}{365})^b <= 0.5$$

#!/usr/bin/env python3

from math import comb, log
import gmpy2
from gmpy2 import mpfr, sqrt
import matplotlib.pyplot as plt

gmpy2.get_context().precision = 100

N = 1024

def lambda_numerator(n, x):
    numerator = mpfr(comb(N, x)) * mpfr(comb(n - 1, n - x))
    return numerator

def lambda_denomenator(n):
    total = 0
    poss = []
    for i in range(1, n+1):
        ret = lambda_numerator(n, i)
        total += ret
        poss.append(ret)
    return mpfr(total), poss


def probability(a, b):
    total = mpfr(0.0)
    denomenator, poss = lambda_denomenator(a)
    bot = pow(1 / mpfr(N), b)
    for i in range(1, a + 1):
        l = poss[i-1] / denomenator
        r = pow(mpfr(N - i), b) * bot
        total += l * r
    return total

def birthday(n):
    return 1/2 + sqrt(1/4 + 2 * log(2) * n)

def main():
    print(N)
    threshold = mpfr(0.5)
    minimum = 2 << 32
    minimum_ans = []
    ans = []
    xs = []
    y1 = []
    y2 = []
    for a in range(10, 70):
        if a >= minimum:
            break
        left = a - 9
        right = a + 50
        prob = 0
        while left < right:
            mid = left + (right - left) // 2
            prob = probability(a, mid)
            if prob > threshold:
                left = mid + 1
            else:
                right = mid
        if a + mid > minimum:
            continue
        if prob > 0.5:
            continue
        # print(f"[{a+left}]\t{a}\t{left}\t{prob}")
        if a + left < minimum:
            minimum = a + left
            minimum_ans = [a, left]
        xs.append(a)
        y1.append(left)
        y2.append(a+left)

    print(minimum)
    print(minimum_ans)
    return minimum


if __name__ == "__main__":
    ns = []
    ms = []
    us = []
    for N in range(100, 2048):
        ns.append(N)
        ms.append(main())
        us.append(birthday(N))
    plt.plot(ns, ms)
    plt.plot(ns, us)
    plt.show()
    main()

Let $S = \{x \oplus y | x \in A, y \in B\}$, then $|S| = ab$. The original problem is equivalent to: Find $min(a + b)$ s.t. $Pr[0 \in S] >= .5$. Since $x_i \in A$ and $y_i \in B$ are i.i.d. random variables, so do $s_i \in S$. Thus,

$Pr[0 \in S] >= .5$
$\implies 1 - (1 - 1/N)^{ab} >= .5$
$\implies ab >= \dfrac{ln(2)}{ln(N) - ln(N-1)}$
$\implies ab >= N\cdot ln(2)$
$\implies min(a+b) = 2\sqrt{N\cdot ln(2)}$, when $a = b = \sqrt{N\cdot ln(2)}$

P.S. $min(a+b) = \sqrt{2} \cdot \sqrt{N\cdot 2ln(2)} = \sqrt{2} \cdot origBirthdayAns$