Belajar Math - Pigeonhole Principle & Inclusion-Exclusion
Pigeonhole principle (n+1 merpati masuk n lubang → minimal satu lubang berisi ≥2) menjelaskan collision detection dan Bloom filter; inclusion-exclusion |A∪B| = |A|+|B|−|A∩B| menghindari double-counting — dari birthday paradox hingga scoring per-hari dengan overlap events.
#Pendahuluan
Setelah di episode 11 kita mempelajari permutasi dan kombinasi — cara menghitung jumlah kemungkinan — pada episode ini kita mempelajari dua prinsip counting lanjutan: Pigeonhole Principle dan Inclusion-Exclusion. Keduanya menjelaskan fenomena yang sering kita temui dalam programming: mengapa collision terjadi, mengapa double-counting merusak, dan mengapa birthday paradox lebih umum dari yang kita kira.
Mengapa prinsip ini penting? Karena Pigeonhole Principle menjelaskan mengapa hash collision tidak bisa dihindari (karena input lebih banyak dari output space), dan Inclusion-Exclusion menjelaskan bagaimana menghitung dengan benar ketika ada overlap antara dua himpunan. Keduanya muncul dalam desain database, analisis algoritma, dan probabilistic data structures.
#Pigeonhole Principle (Prinsip Laci)
#Definisi
Jika n+1 merpati masuk ke n lubang, maka minimal satu lubang berisi ≥2 merpati.
Ini terdengar trivial, tetapi implikasinya sangat luas — ini membuktikan bahwa collision pasti terjadi ketika input lebih banyak dari output.
#Verifikasi Sederhana
def pigeonhole_demo():
"""Tunjukkan collision menggunakan modular arithmetic."""
lubang = 5 # jumlah lubang (hash space)
merpati = 7 # jumlah merpati (input) — lebih banyak dari lubang!
# Hash function: i mod 5
mapping = {}
for merpati_id in range(merpati):
lubang_id = merpati_id % lubang
if lubang_id not in mapping:
mapping[lubang_id] = []
mapping[lubang_id].append(merpati_id)
print(f"Lubang: {lubang}, Merpati: {merpati}")
for hole, birds in sorted(mapping.items()):
collision = " ← COLLISION!" if len(birds) > 1 else ""
print(f" Lubang {hole}: {birds}{collision}")
pigeonhole_demo()#Aplikasi: Hash Collision
# SHA-256 menghasilkan 2^256 kemungkinan output
# Tetapi jika kita hash lebih dari 2^128 input, collision ~50% (birthday bound)
# Dalam praktik: hash table
def simple_hash(key, table_size):
return hash(key) % table_size
# Demo collision
table_size = 10
keys = ["apple", "banana", "cherry", "date", "elderberry",
"fig", "grape", "honeydew", "kiwi", "lemon",
"mango", "nectarine"] # 12 keys > 10 slots!
hash_map = {}
for key in keys:
slot = simple_hash(key, table_size)
if slot in hash_map:
print(f"Collision: '{key}' dan '{hash_map[slot]}' → slot {slot}")
else:
hash_map[slot] = key#Birthday Paradox
Birthday Paradox menggunakan Pigeonhole Principle secara probabilistik: dalam 23 orang, probabilitas ≥50% ada birthday sama. Dalam 366 orang, probabilitas 100% (pigeonhole principle murni).
import random
def birthday_paradox(num_people, num_simulations=10000):
"""Simulasi birthday paradox."""
collisions = 0
for _ in range(num_simulations):
birthdays = [random.randint(1, 365) for _ in range(num_people)]
if len(birthdays) != len(set(birthdays)):
collisions += 1
return collisions / num_simulations
# Hitung probabilitas untuk berbagai jumlah orang
for n in [10, 15, 20, 23, 30, 50]:
prob = birthday_paradox(n)
print(f" {n} orang: {prob:.1%} probabilitas collision")
# Birthday bound untuk hash table
hash_bits = 128
birthday_bound = 2 ** (hash_bits // 2)
print(f"\nBirthday bound untuk {hash_bits}-bit hash: ~{birthday_bound:,} entries")#Inclusion-Exclusion
#Definisi
Inclusion-Exclusion memperbaiki double-counting ketika menghitung union dua himpunan:
|A ∪ B| = |A| + |B| − |A ∩ B|
Tanpa pengurangan intersection, elemen yang ada di kedua himpunan dihitung dua kali.
#Visual
A ∪ B tanpa correction:
|A| + |B| = area A + area B
(area B ∩ A dihitung dua kali!)
A ∪ B dengan Inclusion-Exclusion:
|A| + |B| − |A ∩ B| = area A + area B − area overlap#Verifikasi
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}
# Tanpa correction — salah!
union_wrong = len(A) + len(B) # 10
# Dengan Inclusion-Exclusion — benar!
union_correct = len(A) + len(B) - len(A & B)
print(f"|A| = {len(A)}, |B| = {len(B)}")
print(f"|A ∩ B| = {len(A & B)}")
print(f"Tanpa correction: {union_wrong} (SALAH — double-counted)")
print(f"Dengan Inclusion-Exclusion: {union_correct} (BENAR)")
print(f"Actual: {len(A | B)}")#Tiga Himpunan
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
C = {4, 5, 6, 7}
# |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
result = (len(A) + len(B) + len(C)
- len(A & B) - len(A & C) - len(B & C)
+ len(A & B & C))
print(f"|A ∪ B ∪ C| = {result}")
print(f"Actual: {len(A | B | C)}")
print(f"Match: {result == len(A | B | C)}")#Aplikasi Nyata
#Scoring dengan Overlap Events
# Event yang berlangsung beberapa hari, overlap
events = [
{"name": "Sale", "days": {1, 2, 3, 4, 5}},
{"name": "Bonus", "days": {3, 4, 5, 6, 7}},
{"name": "Promo", "days": {5, 6, 7, 8, 9}},
]
# Total hari aktif (inclusion-exclusion untuk 3 event)
all_days = set()
for event in events:
all_days |= event["days"]
print(f"Total hari aktif: {len(all_days)}")
# Per hari: berapa event aktif?
for day in sorted(all_days):
active = [e["name"] for e in events if day in e["days"]]
print(f" Hari {day}: {active} ({len(active)} event)")#Bloom Filter (Pigeonhole Application)
Bloom filter menggunakan Pigeonhole Principle: karena output space terbatas, false positive bisa terjadi (elemen "mungkin ada") tetapi false negative tidak mungkin.
class SimpleBloomFilter:
def __init__(self, size=10):
self.size = size
self.bits = [0] * size
def _hashes(self, item):
"""Dua hash function sederhana."""
h1 = hash(item) % self.size
h2 = (hash(item) * 31 + 7) % self.size
return h1, h2
def add(self, item):
for h in self._hashes(item):
self.bits[h] = 1
def might_contain(self, item):
return all(self.bits[h] for h in self._hashes(item))
# Demo
bf = SimpleBloomFilter()
bf.add("apple")
bf.add("banana")
print(f"Might contain 'apple'? {bf.might_contain('apple')}") # True
print(f"Might contain 'grape'? {bf.might_contain('grape')}") # False (probably)
print(f"Bits: {bf.bits}")Note
Pigeonhole Principle menjamin collision pasti terjadi jika input > output space. Inclusion-Exclusion memperbaiki double-counting. Keduanya adalah tools analisis yang powerful: yang pertama untuk membuktikan batasan, yang kedua untuk menghitung dengan benar.
#Penutup
Inti yang harus dibawa pulang:
- Pigeonhole Principle: n+1 merpati ke n lubang → minimal satu lubang berisi ≥2. Ini menjelaskan mengapa hash collision pasti terjadi.
- Birthday Paradox: dalam 23 orang, probabilitas ≥50% birthday sama — aplikasi probabilistik pigeonhole principle.
- Inclusion-Exclusion:
|A∪B| = |A|+|B|−|A∩B|— memperbaiki double-counting. Untuk 3 himpunan, tambahkan intersection tiga. - Bloom filter menggunakan pigeonhole principle untuk probabilistic membership testing.
- Kedua prinsip muncul dalam desain database, hash table, dan probabilistic data structures.
Di episode 13 selanjutnya kita akan mempelajari probability dasar dan Bayes — probability space, conditional probability, dan Bayes' theorem yang menjadi fondasi dari A/B testing, spam filter, dan classification probabilistic. Pigeonhole principle yang baru kalian pelajari akan muncul kembali sebagai dasar mengapa collision probability berperilaku seperti yang kita harapkan!