Prinsip Inklusi-Eksklusi (PIE) adalah salah satu teknik berhitung (kombinatorika) yang sangat fundamental dalam olimpiade matematika. Konsep ini digunakan untuk menghitung jumlah total elemen dari gabungan beberapa himpunan yang saling beririsan, dengan cara mengoreksi perhitungan ganda (overcounting).
Berikut adalah penjelasan rincinya, yang disusun agar mudah dipahami secara konseptual maupun untuk diajarkan kembali dalam persiapan kompetisi.
1. Konsep Dasar dan Logika PIE
Ide utama dari PIE adalah:
Inklusi (Masukkan): Tambahkan jumlah elemen dari setiap himpunan secara individual.
Eksklusi (Keluarkan): Saat kita menambahkan elemen dari himpunan-himpunan tersebut, elemen yang berada di irisannya terhitung lebih dari satu kali. Oleh karena itu, kita harus menguranginya.
Koreksi Lanjutan: Jika ada tiga himpunan atau lebih, mengurangkan irisan dua himpunan mungkin akan membuat bagian irisan tiga himpunan tidak terhitung sama sekali, sehingga kita harus menambahkannya kembali. Pola tambah-kurang ini terus berlanjut.
2. Rumus PIE
Untuk 2 Himpunan ($A$ dan $B$):
$$|A \cup B| = |A| + |B| - |A \cap B|$$
Penjelasan: Kita menghitung semua di $A$ dan semua di $B$. Karena irisan $A \cap B$ dihitung dua kali (sekali di $A$, sekali di $B$), kita menguranginya satu kali.
Untuk 3 Himpunan ($A$, $B$, dan $C$):
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
Bentuk Umum (Untuk $n$ Himpunan):
Jika terdapat himpunan $A_1, A_2, \dots, A_n$, maka jumlah elemen gabungannya adalah:
$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$$
3. Tipe Soal PIE yang Sering Muncul di Olimpiade
Dalam konteks soal olimpiade, PIE jarang muncul dalam bentuk "himpunan" murni, melainkan disembunyikan dalam kondisi-kondisi tertentu, seperti:
Keterbagian: Menghitung banyaknya bilangan dalam suatu rentang yang habis dibagi (atau tidak habis dibagi) oleh sekumpulan bilangan prima.
Derangement (Kekacauan): Mencari banyaknya permutasi di mana tidak ada elemen yang menempati posisi aslinya.
Distribusi Objek (Fungsi Surjektif): Menghitung banyaknya cara mendistribusikan objek berbeda ke dalam kotak berbeda sedemikian rupa sehingga tidak ada kotak yang kosong.
Persamaan Diophantine Linear: Mencari banyaknya solusi bulat dari persamaan $x_1 + x_2 + x_3 = n$ dengan batasan atas tertentu untuk masing-masing variabel.
4. Contoh Soal dan Pembahasan (Fokus Keterbagian)
Soal:
Berapa banyak bilangan bulat dari 1 hingga 1000 yang tidak habis dibagi 2, 3, atau 5?
Pembahasan:
Misalkan $S$ adalah himpunan semua bilangan bulat dari 1 hingga 1000. Maka $|S| = 1000$.
Misalkan:
$A$ = himpunan bilangan yang habis dibagi 2
$B$ = himpunan bilangan yang habis dibagi 3
$C$ = himpunan bilangan yang habis dibagi 5
Kita akan mencari nilai dari bilangan yang habis dibagi 2, 3, atau 5 terlebih dahulu, yaitu $|A \cup B \cup C|$.
Langkah 1: Hitung masing-masing himpunan (Inklusi)
$|A| = \lfloor 1000 / 2 \rfloor = 500$
$|B| = \lfloor 1000 / 3 \rfloor = 333$
$|C| = \lfloor 1000 / 5 \rfloor = 200$
Langkah 2: Hitung irisan dua himpunan (Eksklusi)
Gunakan KPK dari pembagi untuk mencari irisan.
$|A \cap B|$ (habis dibagi 2 dan 3, berarti habis dibagi 6): $\lfloor 1000 / 6 \rfloor = 166$
$|A \cap C|$ (habis dibagi 2 dan 5, berarti habis dibagi 10): $\lfloor 1000 / 10 \rfloor = 100$
$|B \cap C|$ (habis dibagi 3 dan 5, berarti habis dibagi 15): $\lfloor 1000 / 15 \rfloor = 66$
Langkah 3: Hitung irisan tiga himpunan (Inklusi kembali)
$|A \cap B \cap C|$ (habis dibagi 2, 3, dan 5, berarti habis dibagi 30): $\lfloor 1000 / 30 \rfloor = 33$
Langkah 4: Terapkan rumus PIE
$$|A \cup B \cup C| = (500 + 333 + 200) - (166 + 100 + 66) + 33$$
$$|A \cup B \cup C| = 1033 - 332 + 33 = 734$$
Ada 734 bilangan yang habis dibagi 2, 3, atau 5. Karena yang ditanyakan adalah yang tidak habis dibagi, kita kurangi dari total:
$$\text{Jawaban} = 1000 - 734 = 266$$
LATIHAN SOAL
Soal 1 (Himpunan Dasar)
Dari $100$ siswa di sebuah sekolah, $50$ siswa menyukai materi Aljabar, $40$ siswa menyukai Geometri, dan $30$ siswa menyukai Kombinatorika. Diketahui ada $15$ siswa yang menyukai Aljabar dan Geometri, $10$ siswa menyukai Aljabar dan Kombinatorika, $8$ siswa menyukai Geometri dan Kombinatorika, serta $5$ siswa menyukai ketiga materi tersebut. Berapa banyak siswa yang tidak menyukai ketiga bidang matematika tersebut?
Soal 2 (Keterbagian 2 Variabel)
Tentukan banyaknya bilangan bulat dari $1$ hingga $500$ yang tidak habis dibagi $3$ dan juga tidak habis dibagi $7$.
Soal 3 (Keterbagian Bersyarat)
Dari bilangan bulat $1$ hingga $300$, berapa banyak bilangan yang habis dibagi $2$ atau $3$, tetapi tidak habis dibagi $5$?
Soal 4 (Kombinasi Angka/PIN)
Sebuah kata sandi (PIN) terdiri dari $4$ angka (menggunakan angka $0$ hingga $9$). Berapa banyak kemungkinan PIN yang dapat dibuat jika PIN tersebut harus memuat setidaknya satu buah angka $7$ dan setidaknya satu buah angka $8$?
Soal 5 (Derangement Dasar)
Ada $4$ orang siswa yang menaruh tas mereka di loker. Jika saat pulang tiba-tiba mati lampu dan mereka mengambil tas secara acak di dalam gelap, berapa banyak cara yang mungkin terjadi agar tidak ada satupun siswa yang mengambil tas miliknya sendiri?
Soal 6 (Persamaan Diophantine dengan Batasan Atas)
Tentukan banyaknya solusi bilangan bulat non-negatif dari persamaan $x + y + z = 15$, dengan syarat pembatas: $x \le 5$, $y \le 6$, dan $z \le 7$.
Soal 7 (Permutasi dengan Larangan)
Berapa banyak susunan kata (tidak harus bermakna) dengan panjang $5$ huruf yang dapat dibentuk dari huruf-huruf A, B, C, D, E (setiap huruf dipakai tepat satu kali) jika susunan huruf tersebut tidak boleh memuat substring "AB" dan tidak boleh memuat substring "CD"?
Soal 8 (Keterbagian dalam Rentang)
Berapa banyak bilangan bulat di antara $1000$ dan $2026$ yang habis dibagi $4$ atau $6$, tetapi tidak habis dibagi $9$?
Soal 9 (Relatif Prima - Fungsi Euler)
Dua buah bilangan dikatakan relatif prima jika Faktor Persekutuan Terbesar (FPB) dari kedua bilangan tersebut adalah $1$. Berapa banyak bilangan asli yang kurang dari atau sama dengan $210$ yang relatif prima dengan $210$? (Petunjuk: Faktorisasi prima dari $210$ adalah $2 \times 3 \times 5 \times 7$).
Soal 10 (Derangement Modifikasi)
Lima pasangan suami istri menghadiri suatu acara perpisahan kelas. Saat sesi permainan berdansa, pembawa acara memasangkan $5$ laki-laki dan $5$ perempuan secara acak. Berapa banyak cara memasangkan mereka sedemikian rupa sehingga tepat ada satu orang laki-laki yang berdansa dengan istrinya sendiri?