# 052 — Birthday Paradox Style Problems

> এই level-এর শেষ problem — আর শেষটা একটা চমক দিয়ে। প্রশ্ন: একটা ঘরে কতজন থাকলে দুজনের জন্মদিন মেলার সম্ভাবনা 50% ছাড়াবে? সবাই ভাবে "অনেক, হয়তো 180+"। আসল উত্তর — মাত্র **23 জন**! এই অবিশ্বাস্য ফলটাই birthday paradox। আর এটা শুধু মজার ধাঁধা নয়: hashing-এ collision কেন এত তাড়াতাড়ি ঘটে, তার পুরো ব্যাখ্যা এখানে। গণিতটা সহজ — জোড়ার হিসাব।

<div class="problem-source" markdown="1">

<p class="source-label" id="source">Problem link ও উৎস</p>

- **Original source:** Classic probability (birthday paradox)
- **Platform:** Classic probability — <https://discrete.openmathbooks.org/>
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Medium
- **Pattern:** collision probability (birthday paradox)
- **Basic idea inherited from:** 051 — Pigeonhole Principle (নিশ্চিত মিল → সম্ভাব্য মিল)

</div>

## প্রশ্ন ও উদাহরণ {#problem}

### সহজ করে প্রশ্ন {#1-problem-in-simple-words}

একটা ঘরে `n` জন মানুষ। প্রত্যেকের জন্মদিন বছরের 365 দিনের যেকোনো একটা (সমান সম্ভাবনায়)। জানতে চাই — অন্তত **দুজনের জন্মদিন এক** হওয়ার সম্ভাবনা কত?

চমকটা: এই সম্ভাবনা আশ্চর্য দ্রুত বাড়ে। মাত্র **23 জনেই** তা 50% ছাড়িয়ে যায়; 50 জনে প্রায় 97%; 70 জনে 99.9%।

সাধারণ রূপ (birthday-style / collision): `m` টা সম্ভাব্য মান (bucket) থেকে `n` বার এলোমেলো বাছলে, অন্তত দুটো বাছাই **এক** হওয়ার (collision) সম্ভাবনা কত? — এটাই hashing collision-এর গল্প।

### Input ও output {#6-example-input-and-output}

```text
prob_at_least_one_match(n, days=365)  ->  ~সম্ভাবনা
-------------------------------------------------
   n=1   ->  0.000     (একজনে মিল অসম্ভব)
   n=5   ->  0.027
   n=10  ->  0.117
   n=23  ->  0.507     <- 50% ছাড়াল
   n=50  ->  0.970
   n=366 ->  1.000     (pigeonhole: নিশ্চিত মিল)

min_people_for_prob(0.5, 365)  ->  23     (50% পেতে কমপক্ষে কতজন)
min_people_for_prob(0.99, 365) ->  57
```

Edge case: **n=1 → 0** (একজনে কোনো জোড়া নেই, মিল অসম্ভব); **n > days → সম্ভাবনা 1** (pigeonhole, নিশ্চিত মিল — `P(সব আলাদা) = 0`)।

### চেনা উদাহরণে বোঝা {#4-real-life-analogy}

ভাবো তুমি একটা hash table বানাচ্ছ — `m` টা bucket, আর জিনিসগুলো এলোমেলোভাবে bucket-এ পড়ছে (hash function)। তুমি ভাবছ "m তো বড়, collision হতে অনেক জিনিস লাগবে।"

কিন্তু না! birthday-গণিত বলছে — মোটামুটি `√m`-এর কাছাকাছি জিনিস ঢুকলেই collision-এর ভালো সম্ভাবনা। যেমন 365 bucket-এ √365 ≈ 19, আর বাস্তবে 23-এই 50%। অর্থাৎ 1 কোটি bucket থাকলেও মাত্র কয়েক হাজার জিনিসেই collision আশা করা যায়।

এই অন্তর্দৃষ্টি system design-এ গুরুত্বপূর্ণ: hash, UUID, বা cryptographic digest-এ "collision হবে না" ধরে নেওয়া বিপজ্জনক — birthday bound বলে দেয় কত তাড়াতাড়ি ঝুঁকি আসে।

## ভিত্তির ধারণা {#idea}

### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}

এটা **051 (Pigeonhole Principle)**-এর সম্ভাবনা-রূপ। Pigeonhole বলে: 366 জন হলে দুজনের জন্মদিন মিল **নিশ্চিত** (366 পায়রা, 365 খোপ)। Birthday paradox জিজ্ঞেস করে আরও সূক্ষ্ম প্রশ্ন: নিশ্চিত নয়, কিন্তু **সম্ভাব্য** মিল কত তাড়াতাড়ি আসে?

মূল সেতু: pigeonhole-এর "খোপ" এখানে 365 দিন, আর "পায়রা" মানুষ — কিন্তু এবার গ্যারান্টির বদলে **সম্ভাবনা**। আর গোনার হাতিয়ারটা 045-এর `C(n, 2)` (জোড়া) — collision-এর সুযোগ জোড়ায় জোড়ায়। তাই pigeonhole-এর existence-চিন্তা + pair-counting মিলে এই probability।

### ভেতরের অঙ্ক {#2-what-is-the-math-idea}

মূল চালাকি — **উল্টোটা গোনা সহজ:** "সবার আলাদা" হওয়ার সম্ভাবনা বের করে 1 থেকে বিয়োগ করো।

n জন সবার জন্মদিন আলাদা হওয়ার সম্ভাবনা:

```text
P(সব আলাদা) = (365/365) × (364/365) × (363/365) × ... × ((365−n+1)/365)

P(অন্তত এক মিল) = 1 − P(সব আলাদা)
```

কেন দ্রুত বাড়ে? কারণ মিলের সুযোগ আসে **জোড়ায় জোড়ায়** — n জনে `C(n, 2) = n(n−1)/2` জোড়া, প্রতিটাই collision-এর একটা সুযোগ। 23 জনে জোড়া `C(23,2) = 253` — তাই সম্ভাবনা এত বেশি।

## ধাপে ধাপে সমাধান {#walkthrough}

### প্রথম সরল উপায় {#7-brute-force-thinking}

সবচেয়ে সরাসরি — **Monte Carlo simulation:** বহুবার এলোমেলো জন্মদিন বিলি করে গুনি কতবার মিল হলো:

```python
import random

def birthday_sim(n, days=365, trials=200000):
    hits = 0
    for _ in range(trials):
        bdays = [random.randrange(days) for _ in range(n)]
        if len(set(bdays)) < n:         # set ছোট মানে অন্তত দুটো এক
            hits += 1
    return hits / trials
```

প্রতিটা trial-এ n জনের এলোমেলো জন্মদিন বানাই; `set`-এর আকার n-এর কম হলে কোথাও মিল আছে। অনেক trial-এর গড়ই আনুমানিক সম্ভাবনা — formula যাচাইয়ের ভালো উপায় (যদিও আনুমানিক)।

### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}

simulation শুধু **আনুমানিক**, আর নির্ভুল হতে বহু trial লাগে:

```text
সঠিক 3 দশমিক ঘর পেতে: লক্ষ লক্ষ trial দরকার
প্রতি trial-এ n জনের জন্মদিন + set বানানো -> O(n)
মোট O(trials × n) -> ধীর, আর তবু ±error থেকে যায়

সঠিক formula: 1 − ∏(days−i)/days -> O(n), নির্ভুল!
```

আর "কতজন হলে 50%" খুঁজতে প্রতিটা n-এ আলাদা simulation চালানো আরও ব্যয়বহুল। formula এক pass-এ নির্ভুল উত্তর দেয়।

### আরও ভালোভাবে ভাবা {#9-better-thinking}

মূল insight: simulate নয় — **"সব আলাদা"-র সম্ভাবনা সরাসরি গুণ করে 1 থেকে বিয়োগ:**

```python
def prob_at_least_one_match(n, days=365):
    if n > days:
        return 1.0                      # pigeonhole: নিশ্চিত
    p_all_distinct = 1.0
    for i in range(n):
        p_all_distinct *= (days - i) / days   # i-তম জন আগের সবার থেকে আলাদা
    return 1 - p_all_distinct
```

"কতজন হলে অন্তত target সম্ভাবনা" — n বাড়াতে বাড়াতে প্রথম যেখানে পেরোয়:

```python
def min_people_for_prob(target, days=365):
    n = 1
    while prob_at_least_one_match(n, days) < target:
        n += 1
    return n
```

সম্ভাবনা n-এর সাথে monotonic বাড়ে, তাই প্রথম-পেরোনো n-ই উত্তর।

### ভাবনার পরিবর্তন {#10-thinking-tweak}

আসল "আহা" মুহূর্ত: **collision-এর সম্ভাবনা সরাসরি গোনার বদলে উল্টোটা ("সব আলাদা") গোনো — সেটা সহজ গুণফল; আর মনে রাখো তুলনা হয় জোড়ায় (C(n,2)), ব্যক্তিতে নয়।**

দুই tweak গেঁথে নাও:
- **Complement trick:** "অন্তত একটা মিল" গোনা কঠিন (অনেক case); "একটাও মিল নেই" সহজ (একটাই case, পরপর আলাদা)। `1 − P(সব আলাদা)` — এই উল্টো-গোনা probability-র সবচেয়ে কাজের কৌশল।
- **√m intuition:** collision আশা করা যায় মোটামুটি `√(সম্ভাব্য মান)` জিনিসেই — কারণ জোড়া `~n²/2`, আর `n ≈ √m`-এ জোড়া `~m/2` (খোপের অর্ধেক)। hashing/security-তে এটাই "birthday bound"।

### ছবিতে বোঝা {#5-visual-explanation}

প্রথমে দেখো সম্ভাবনা কত দ্রুত বাড়ে:

```text
n জন -> অন্তত এক মিলের সম্ভাবনা (~):

 5  জন: ████                  ~2.7%
10  জন: ████████████          ~11.7%
23  জন: ██████████████████████████ ~50.7%   <- অর্ধেক পেরোল!
30  জন: ████████████████████████████████ ~70.6%
50  জন: ███████████████████████████████████████ ~97.0%
70  জন: ████████████████████████████████████████ ~99.9%
```

এবার দেখো কেন এত দ্রুত — জোড়ার হিসাব:

```text
n জনে collision-এর সুযোগ = জোড়ার সংখ্যা = C(n, 2)

n=5  -> C(5,2)  = 10 জোড়া
n=23 -> C(23,2) = 253 জোড়া     <- 253 টা সুযোগ! তাই 50%
n=30 -> C(30,2) = 435 জোড়া

মানুষ-সংখ্যা রৈখিক বাড়ে, কিন্তু জোড়া-সংখ্যা ~n²/2 হারে -> তাই চমক
```

লক্ষ করো — তুলনা ব্যক্তিতে নয়, **জোড়ায়**; জোড়া বর্গাকার হারে বাড়ে বলেই সম্ভাবনা লাফিয়ে ওঠে।

### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}

চলো `prob_at_least_one_match(3, days=365)` চালাই (`p_all_distinct` জমে):

| i | এই ধাপের গুণক (days−i)/days | p_all_distinct (পরে) |
| --- | --- | --- |
| শুরু | — | 1.0 |
| 0 | 365/365 = 1.0 | 1.0 |
| 1 | 364/365 ≈ 0.99726 | ≈ 0.99726 |
| 2 | 363/365 ≈ 0.99452 | ≈ 0.99180 |

`P(সব আলাদা) ≈ 0.99180` → `P(অন্তত মিল) ≈ 1 − 0.99180 = 0.0082` (≈ 0.82%)।

ব্যাখ্যা: 3 জনে জোড়া C(3,2)=3, তাই সম্ভাবনা ছোট। একই loop 23 পর্যন্ত চালালে `P` ≈ 0.507 — অর্ধেক পেরোয় ✓।

## কোড ও ব্যাখ্যা {#code}

### Python {#12-python-solution}

```python
def prob_at_least_one_match(n, days=365):
    """n জনে অন্তত দুজনের জন্মদিন মেলার সম্ভাবনা।"""
    if n < 0:
        raise ValueError("n non-negative হতে হবে")
    if n > days:
        return 1.0                          # pigeonhole: নিশ্চিত মিল
    p_all_distinct = 1.0
    for i in range(n):
        p_all_distinct *= (days - i) / days
    return 1 - p_all_distinct


def min_people_for_prob(target, days=365):
    """অন্তত target সম্ভাবনা পেতে কমপক্ষে কতজন লাগবে।"""
    n = 1
    while prob_at_least_one_match(n, days) < target:
        n += 1
    return n


def expected_distinct(n, m):
    """m bucket-এ n বার এলোমেলো ফেললে গড়ে কতগুলো আলাদা bucket ভরে।"""
    return m * (1 - (1 - 1 / m) ** n)


# --- ছোট test গুলো (সব pass করা উচিত) ---
import math

# base case
assert prob_at_least_one_match(0) == 0.0        # কেউ নেই -> মিল নেই
assert prob_at_least_one_match(1) == 0.0        # একজন -> জোড়া নেই
assert prob_at_least_one_match(366) == 1.0      # pigeonhole
assert prob_at_least_one_match(400) == 1.0

# জানা মাইলফলক (approx, tolerance সহ)
assert abs(prob_at_least_one_match(23) - 0.5073) < 1e-3
assert abs(prob_at_least_one_match(50) - 0.9704) < 1e-3
assert abs(prob_at_least_one_match(10) - 0.1169) < 1e-3

# সম্ভাবনা n-এর সাথে monotonic বাড়ে (কখনো কমে না)
prev = -1.0
for n in range(0, 100):
    cur = prob_at_least_one_match(n)
    assert cur >= prev - 1e-12
    prev = cur

# বিখ্যাত উত্তর: 50%-এর জন্য 23 জন, 99%-এর জন্য 57
assert min_people_for_prob(0.5) == 23
assert min_people_for_prob(0.99) == 57

# ছোট days দিয়ে formula হাতে-হিসাবের সাথে মেলে
# days=2 (মুদ্রা): 2 জনে মিল = 1/2; "সব আলাদা" = 2/2 * 1/2 = 1/2
assert abs(prob_at_least_one_match(2, days=2) - 0.5) < 1e-12
# days=3, n=2: সব আলাদা = 3/3 * 2/3 = 2/3, মিল = 1/3
assert abs(prob_at_least_one_match(2, days=3) - (1 / 3)) < 1e-12

# C(n,2) jোড়ার গল্প: 23 জনে 253 জোড়া (সম্ভাবনার অন্তর্দৃষ্টি)
assert math.comb(23, 2) == 253

print(round(prob_at_least_one_match(23), 4))    # 0.5073
print(round(prob_at_least_one_match(50), 4))    # 0.9704
print(min_people_for_prob(0.5))                 # 23
print("সব test pass!")
```

### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}

```text
def prob_at_least_one_match(n, days=365):
    if n > days:
        return 1.0
```

pigeonhole — মানুষ দিনের চেয়ে বেশি হলে মিল নিশ্চিত, সরাসরি 1।

```text
    p_all_distinct = 1.0
    for i in range(n):
        p_all_distinct *= (days - i) / days
    return 1 - p_all_distinct
```

হৃদয় — "সব আলাদা"-র সম্ভাবনা জমাই: i-তম জনের জন্মদিন আগের i জনের কারো সাথে না-মেলার সম্ভাবনা `(days−i)/days`; সব গুণ। শেষে `1 −` করে "অন্তত এক মিল"।

```text
def min_people_for_prob(target, days=365):
    n = 1
    while prob_at_least_one_match(n, days) < target:
        n += 1
    return n
```

সম্ভাবনা monotonic বাড়ে, তাই n বাড়াতে বাড়াতে প্রথম যেখানে target পেরোয় — সেটাই কমপক্ষে দরকারি লোকসংখ্যা।

বাকি `assert` লাইনগুলো base case, জানা মাইলফলক (23→0.5073 ইত্যাদি), monotonicity, ছোট-days হাতে-হিসাব আর C(23,2)=253 — সব দিক যাচাই করছে। সব মিললে শেষে `সব test pass!`।

### Output মিলিয়ে দেখা {#14-output-walkthrough}

চালালে যা ছাপবে:

```text
0.5073
0.9704
23
সব test pass!
```

প্রথম: 23 জনে মিলের সম্ভাবনা ≈ 0.5073 (50% পেরোল!)। দ্বিতীয়: 50 জনে ≈ 0.9704। তৃতীয়: 50% পেতে কমপক্ষে 23 জন। আগের সব `assert` (base case, জানা মান, monotonicity, ছোট-days হাতে-যাচাই, C(23,2)) চুপচাপ pass করেছে। শেষে `সব test pass!`।

## খরচ ও সাধারণ ভুল {#cost}

### সময় {#15-time-complexity}

`prob_at_least_one_match(n)` **O(n)** — একটা loop, n টা গুণ। `min_people_for_prob(target)` **O(n²)** খারাপ ক্ষেত্রে (প্রতিটা n-এ O(n) করে), তবে target ছোট হলে দ্রুত থামে। simulation-এর O(trials·n)-এর তুলনায় formula নির্ভুল ও দ্রুত।

### অতিরিক্ত জায়গা {#16-space-complexity}

**O(1)** — শুধু গুটিকয় variable (চলমান probability)। কোনো list বা বড় structure রাখা হয় না (simulation-এ লাগত)।

### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}

1. **সরাসরি "অন্তত এক মিল" গুনতে চাওয়া** — অনেক case, জটিল; complement (`1 − P(সব আলাদা)`) অনেক সহজ।
2. **ব্যক্তিতে তুলনা ভাবা** — মিলের সুযোগ **জোড়ায়** (C(n,2)); তাই 23-এই 50%, "অর্ধেক 365 = 183" ভুল intuition।
3. **n > days-এ formula চালানো** — তখন `(days−i)` negative হয়ে যায়; আগে pigeonhole দিয়ে 1.0 ফেরত দাও।
4. **"নিশ্চিত" আর "সম্ভাব্য" গুলিয়ে ফেলা** — 366 জনে মিল নিশ্চিত (pigeonhole); 23 জনে শুধু 50% সম্ভাব্য — আলাদা প্রশ্ন।
5. **float-এ ঠিক সমতা আশা করা** — সম্ভাবনা float, তুলনায় tolerance (`< 1e-3`) ব্যবহার করো, `==` নয়।

## শেখা ও পরের অনুশীলন {#practice}

### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}

- **Cryptography — Birthday Attack** — hash collision খুঁজতে ~`√(2ⁿ)` চেষ্টা লাগে (n-bit hash); এই গণিতের সরাসরি প্রয়োগ।
- **Hashing collision analysis** — load factor, expected collisions; `expected_distinct`-এর সম্প্রসারণ।
- **051 — Pigeonhole Principle** (এই repo) — এর "নিশ্চিত" রূপ; দুটো একসাথে দেখলে existence vs probability পরিষ্কার হয়।

### কৌশলটি মনে রাখুন {#19-pattern-learned}

**Birthday paradox / collision probability (complement + pair counting)** — `P(মিল) = 1 − ∏(days−i)/days`; collision আশা করা যায় ~`√m` জিনিসেই, কারণ জোড়া C(n,2)~n²/2। মূল signal: **"কতগুলো এলোমেলো বাছাইয়ে দুটো এক হবে / hash collision কত তাড়াতাড়ি" দেখলেই birthday — complement গোনো, জোড়ায় ভাবো।**

### নিজেকে যাচাই করুন {#20-final-summary}

ভবিষ্যতের আমাকে এক লাইনে: *"birthday: P(মিল)=1−∏(days−i)/days; 365 দিনে মাত্র 23 জনেই 50%! তুলনা জোড়ায় (C(n,2)), তাই ~√m জিনিসেই collision — hashing-এর birthday bound। complement গোনার কৌশল মনে রেখো।"*

এই level শেষ! পরের ধাপ → [Level 4: Bit Manipulation](../../04-bit-manipulation/README.md) (047-এর 2ⁿ subsets সেখানে bit-এর ভাষায় নতুন রূপ নেবে)।

ফিরে দেখা: আগের ধাপ → [051 — Pigeonhole Principle Problems](051-pigeonhole-principle.md) · এই level-এর map → [../README.md](../README.md) · concept ঝালাই → [../concept-notes.md](../concept-notes.md) · template → [../../../templates/math-problem-note-template.md](../../../templates/math-problem-note-template.md)।

---

> **মনে রাখার নিয়ম (legal):** সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।