Lesson 9 — Intermediate

Pigeonhole Principle

Pigeonhole principle duniya ka sabse chhota aur sabse powerful principle hai — ek line ka. "Kam se kam", "guaranteed", "at least" — ye shabd dekhte hi iska signal mil jaata hai. Is lesson mein seekhenge basic aur strong version, aur classic exam problems.

Pigeonhole principle kya hai

Iska proof bhi ek line ka hai: agar har khaane mein 1 hi pigeon gaya, toh n khaano mein n pigeons — par paas mein n + 1 hain. Toh koi na koi khaana 2 lega. Bas contradiction itna hi hai.

Strong (generalized) pigeonhole

Generalized (strong) pigeonhole:
  kn + 1 pigeons, n holes → kam se kam ek hole mein (k + 1)

Formula: q pigeons, n holes → guaranteed max = ⌈q / n⌉

Example 1: 52 students, 12 months
  ⌈52 / 12⌉ = ⌈4.33⌉ = 5
  ⇒ kam se kam 5 students ka ek hi mahine mein birthday

Example 2: 13 students, 12 months
  ⌈13 / 12⌉ = 2 ⇒ do ka ek hi mahine birthday (guaranteed)

Example 3: 100 log, 366 possible birthdays
  ⌈100 / 366⌉ = 1 → koi guarantee nahi!
  (pigeons ≤ holes ho toh collision ki compulsion nahi)

Isi wajah se 100 logon ke beech sabka birthday alag ho sakta hai, par 367 logon ke beech guarantee hai — kyunki 366 possible days hi hain.

Classic exam problems

1) 367 log → do ka birthday ek hi din
   366 days + 1 = 367 ✓

2) 13 log → do ka ek hi mahine birthday
   12 months, ⌈13/12⌉ = 2 ✓

3) Drawer mein 10 black + 10 blue socks (andhe andhe)
   Worst case: 1 black + 1 blue = mismatch
   3rd sock → pakka matching pair
   Answer = 3 (2 colours ho toh bas)

4) Hash table: 1001 keys, 1000 buckets
   ⌈1001/1000⌉ = 2 → collision guaranteed
   (hashing mein yahi hota hai — collision handling chahiye)

PHP ki applications

• Hashing: keys > buckets → collision guaranteed (collision resolution chahiye hi chahiye).
• Birthday paradox: 23 logon mein ~50% chance do ka birthday same (PHP ka probability version).
• Scheduling: 13 lectures 12 din mein fit karo → kisi ek din 2 lectures.
• Tournament: 5 khiladi round-robin — do ke scores equal ho sakte hain.
• Proofs: "koi do cheezein same hain" — sabse chhota proof tarika.

PHP mein exact dhoondh nahi sakte — sirf guaranteed lower bound milta hai. Isliye answer options mein "at least 2" wala option dhundo — exact number wala option trap hai.

Exercise

Common mistakes

• "At least 2" ko exact samajhna: PHP kehta hai kam se kam 2 — 3 bhi ho sakte hain. Exact count mat assume karo, guaranteed minimum hi milta hai.
• Pigeons aur holes ulta: Objects = pigeons, categories = holes. ⌈pigeons/holes⌉ — ulta karoge toh answer galat. Hamesha bade wale ko upar rakho.
• Guarantee aur chance mix: PHP GUARANTEE deta hai (worst case), probability AVERAGE chance deti hai. Dono alag cheezein hain — 100 log nahi, 367 log chahiye guarantee ke liye.

12 thaliyan, 13 students → do ek thali share = guaranteed
Almirah: 10 kaale + 10 neele moza
Worst case: 1 kaala + 1 neela = mismatch
3rd moza → pakka pair ✓
Slogan: ⌈objects / categories⌉ = kam se kam