052 — Birthday Paradox Style Problems

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

Source

• 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 (নিশ্চিত মিল → সম্ভাব্য মিল)

1. Problem in simple words

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

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

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

2. What is the math idea?

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

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

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 — তাই সম্ভাবনা এত বেশি।

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।

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 বলে দেয় কত তাড়াতাড়ি ঝুঁকি আসে।

5. Visual explanation

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

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

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

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

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 হারে -> তাই চমক

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

6. Example input and output

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)।

7. Brute force thinking

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

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 লাগে:

সঠিক 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 থেকে বিয়োগ:

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 বাড়াতে বাড়াতে প্রথম যেখানে পেরোয়:

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"।

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 — অর্ধেক পেরোয় ✓।

12. Python solution

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

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

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

    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 − করে "অন্তত এক মিল"।

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!।

14. Output walkthrough

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

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!।

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) ব্যবহার করো, == নয়।

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 (047-এর 2ⁿ subsets সেখানে bit-এর ভাষায় নতুন রূপ নেবে)।

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

---

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