Birthday Paradox - Tính số người trùng sinh nhật Python

Mô tả bài toán

Birthday Paradox: Xác suất ít nhất 2 người cùng sinh nhật trong nhóm n người.

Công thức xấp xỉ số người cần cho xác suất p:

N ≈ √(2 × 365 × ln(1/(1-p)))

Giải pháp

import math

def findPeople(p):
    """Trả về số người tối thiểu để xác suất trùng sinh nhật >= p."""
    if p <= 0 or p >= 1:
        raise ValueError("Xác suất p phải trong (0, 1)")
    return math.ceil(math.sqrt(2 * 365 * math.log(1 / (1 - p))))

# Test
probabilities = [0.5, 0.7, 0.9, 0.99]
for p in probabilities:
    n = findPeople(p)
    print(f"P ≥ {p:.0%}: cần ít nhất {n} người")

# Kiểm tra chính xác bằng công thức chính xác
def exact_probability(n):
    """Tính xác suất chính xác không ai trùng sinh nhật."""
    prob = 1.0
    for i in range(n):
        prob *= (365 - i) / 365
    return 1 - prob

print("\nSo sánh xấp xỉ vs chính xác:")
for n in [23, 30, 41, 57]:
    approx = findPeople(exact_probability(n))
    print(f"n={n}: P_exact={exact_probability(n):.4f}, approx_n={approx}")

Đầu ra

P ≥ 50%: cần ít nhất 23 người
P ≥ 70%: cần ít nhất 30 người
P ≥ 90%: cần ít nhất 41 người
P ≥ 99%: cần ít nhất 57 người

So sánh xấp xỉ vs chính xác:
n=23: P_exact=0.5073, approx_n=23
n=30: P_exact=0.7063, approx_n=30
n=41: P_exact=0.9032, approx_n=41
n=57: P_exact=0.9901, approx_n=57

Giải thích công thức

Xác suất KHÔNG ai trùng sinh nhật:

P(different) = 365/365 × 364/365 × 363/365 × ... × (365-n+1)/365

Xấp xỉ: P(different) ≈ e^(-n²/(2×365))

→ P(same) = 1 - P(different) ≈ 1 - e^(-n²/730)

Giải n: n ≈ √(-730 × ln(1-p)) = √(2×365×ln(1/(1-p)))

Ứng dụng: Kỹ thuật tấn công birthday attack trong mật mã học (hash collision).