Menghitung Banyaknya Himpunan Bagian

Halo pejuang OSN! Ketemu lagi dengan soal Kombinatorika tentang Himpunan Bagian. Kelihatannya gampang ya, tinggal cari subset. Tapi hati-hati, ada kata ATAU di sana yang sering jadi jebakan maut kalau kalian cuma menghitung biasa. Di video ini, kita bakal bedah cara pandang ala anak olimpiade biar soal ini selesai kurang dari satu menit!

Analisis soalnya begini: kita punya himpunan semesta S berisi angka satu sampai tujuh. Kita diminta mencari banyaknya himpunan bagian yang wajib memuat himpunan satu, dua, tiga, empat, lima, ATAU wajib memuat empat, lima, enam. Karena ada kata kunci ATAU, ini adalah tanda mutlak bahwa kita harus menggunakan Prinsip Inklusi Eksklusi agar tidak ada anggota yang terhitung dua kali.

Strategi OSN-nya simpel: Kalau sebuah subset wajib memuat elemen tertentu, anggap elemen itu sudah masuk keranjang. Sisanya ada en elemen bebas yang masing-masing punya dua pilihan: ikut masuk atau tidak. Jadi rumusnya adalah dua pangkat en. Untuk menangani kata ATAU, kita gunakan rumus n A gabung B sama dengan n A ditambah n B dikurangi n A irisan B.

Mari kita eksekusi! Langkah satu, himpunan A wajib memuat satu sampai lima. Dari tujuh anggota semesta, sisa dua angka bebas yaitu enam dan tujuh. Maka, dua pangkat dua sama dengan empat. Langkah dua, himpunan B wajib memuat empat, lima, enam. Sisa empat angka bebas yaitu satu, dua, tiga, dan tujuh. Maka, dua pangkat empat sama dengan enam belas. Langkah tiga, irisannya wajib memuat gabungan keduanya yaitu satu sampai enam. Sisa satu angka bebas yaitu angka tujuh. Maka, dua pangkat satu sama dengan dua. Totalnya adalah empat ditambah enam belas dikurangi dua, hasilnya delapan belas!

Catatan penting untuk cheat sheet kalian: Setiap ketemu soal himpunan bagian dengan syarat ATAU, hitunglah dua pangkat sisa syarat A, ditambah dua pangkat sisa syarat B, lalu wajib dikurangi dua pangkat sisa gabungan syarat A dan B. Kesalahan paling klasik adalah lupa mengurangkan irisan ini, padahal subset seperti satu sampai enam itu terhitung di kelompok A dan juga di kelompok B.

Sekarang giliran kamu! Coba kerjakan dua soal latihan ini. Level satu: himpunan bagian satu sampai lima yang memuat satu dua atau empat. Dan Level dua yang lebih sulit: himpunan bagian satu sampai enam dengan tiga syarat sekaligus. Jangan lupa tuliskan jawabanmu di kolom komentar ya!

Gimana, asik kan mikir ala OSN? Dengan prinsip inklusi eksklusi, soal kombinatorika jadi jauh lebih terukur dan cepat dikerjakan. Jangan lupa bagikan video ini ke teman belajar kalian dan sampai jumpa di pembahasan soal seru lainnya. Tetap semangat pejuang medali!