Pencacahan Ganda Archives

Prinsip inklusi-eksklusi (inclusion-exclusion principle) merupakan perluasan konsep dari diagram Venn yang melibatkan operasi irisan dan gabungan dalam himpunan. Konsep tersebut diperluas sampai-sampai diaplikasikan secara variatif pada kombinatorika.

Perhatikan ilustrasi masalah berikut.

Ilustrasi Masalah

Terdapat sejumlah siswa di dalam suatu kelas. Sebanyak

23

siswa menyukai matematika, sedangkan

18

siswa menyukai fisika. Berapa siswa di dalam kelas tersebut yang menyukai matematika atau fisika?

Permasalahan di atas tidak dapat diselesaikan secara langsung karena kurangnya informasi yang diberikan. Banyak siswa yang menyukai matematika atau fisika dapat diketahui jika banyak siswa yang menyukai keduanya diketahui.

Misalkan $A$ dan $B$ adalah sembarang himpunan. Perhatikan hubungan kedua himpunan tersebut dalam diagram Venn berikut.
Notasi $| A |$ (atau $n (A)$ ) dan $| B |$ (atau $n (B)$ ) berturut-turut menyatakan banyaknya anggota (kardinalitas) himpunan $A$ dan $B .$ Penjumlahan $| A | + | B |$ menghitung banyaknya anggota $A$ yang tidak terdapat dalam $B$ dan banyaknya anggota $B$ yang tidak terdapat dalam $A$ tepat sekali, dan banyaknya anggota yang terdapat dalam $A \cap B$ sebanyak dua kali. Oleh karena itu, pengurangan banyaknya anggota yang terdapat dalam $A \cap B$ dari $| A | + | B |$ membuat banyaknya anggota $A \cap B$ dihitung tepat sekali. Dengan demikian,
$| A \cup B | = | A | + | B | - | A \cap B |$ Generalisasi dari konsep tersebut bagi gabungan dari sejumlah himpunan disebut sebagai prinsip inklusi-eksklusi (PIE).

Khusus untuk tiga himpunan, prinsip inklusi-eksklusi menjamin berlakunya hubungan berikut.
$| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |$ Khusus untuk empat himpunan, prinsip inklusi-eksklusi menjamin berlakunya hubungan berikut.
$\begin{aligned} | A \cup B \cup C \cup D | = & | A | + | B | + | C | + | D | - | A \cap B | - | A \cap C | - | A \cap D | - | B \cap C | - | B \cap D | \\ - | C \cap D | + | A \cap B \cap C | + | A \cap B \cap D | + | A \cap C \cap D | + \\ | B \cap C \cap D | - | A \cap B \cap C \cap D | \end{aligned}$ Sudah tampak polanya, kan?

Secara umum, prinsip inklusi-eksklusi untuk himpunan hingga $A_{1}, A_{2}, A_{3}, \dots, A_{n}$ adalah sebagai berikut.
$\begin{aligned} | A_{1} \cup A_{2} \cup A_{3} \cup \dots \cup A_{n} | = & \sum_{1 \leq i \leq n} | A_{i} | - \sum_{1 \leq i < j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \\ \dots + (- 1)^{n + 1} | A_{i} \cap A_{j} \cap \dots \cap A_{n} | \end{aligned}$

Dengan cara yang sama, kita juga bisa merumuskan jumlah anggota hasil operasi beda setangkup (disimbolkan dengan notasi $\oplus$ ) dari dua himpunan $A$ dan $B$ , yaitu banyaknya anggota $A \cup B$ yang tidak termasuk dalam $A \cap B .$
$| A \oplus B | = | A \cup B | - | A \cap B |$ Perhatikan bahwa $A \oplus B$ dibaca $A$ beda setangkup $B .$
Karena menurut prinsip inklusi-eksklusi berlaku $| A \cup B | = | A | + | B | - | A \cap B |,$ maka kita peroleh
$\begin{aligned} | A \oplus B | & = | A \cup B | - | A \cap B | \\ = (| A | + | B | - | A \cap B |) - | A \cap B | \\ = | A | + | B | - 2 | A \cap B | . \end{aligned}$

Peracakan

Prinsip inklusi-eksklusi dapat diaplikasikan untuk menghitung banyak permutasi dari $n$ objek dengan syarat bahwa tidak ada objek yang berada pada posisi semula. Permutasi seperti itu dinamakan peracakan (derangement). Sebagai contoh, banyak peracakan dari $123$ adalah $2,$ yaitu $231$ dan $312.$ Notasi $D_{n}$ (huruf D berasal dari kata derangement) sering digunakan untuk menyatakan banyak peracakan dari $n$ objek.

Contoh lain diberikan sebagai berikut.
Tuliskan semua peracakan dari ${1, 2, 3, 4} .$

Pembahasan: Peracakan dari $4$ objek, yaitu $1, 2, 3,$ dan $4$ didaftarkan sebagai berikut.
$\begin{array}{cc} 2143 & 2341 \\ 2413 & 3142 \\ 3412 & 3421 \\ 4123 & 4312 \\ 4321 \end{array}$ Catatan: Urutan di atas dibaca secara menyamping. Tuliskan peracakannya secara terstruktur agar tidak ada yang tertinggal atau terhitung lebih dari sekali.

Prinsip inklusi-eksklusi menjadi landasan utama ditemukannya teorema untuk menghitung banyak peracakan dari $n$ objek. Bunyi teorema tersebut adalah sebagai berikut.

Teorema: Banyak Peracakan

Banyak peracakan dari

n

objek dinyatakan oleh

D_{n} = n! [1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!}] .

Bukti

Misalkan suatu permutasi dikatakan memenuhi syarat $P_{i}$ jika objek $i$ tetap di posisi semula. Ini berarti banyak peracakan sama dengan banyak permutasi sehingga syarat $P_{i}$ untuk $i \in {1, 2, 3, \dots, n}$ tidak terpenuhi, atau secara matematis, ditulis
$D_{n} = N (P_{1}^{'} P_{2}^{'} \dots P_{n}^{'}) .$ Dengan menggunakan prinsip inklusi-eksklusi, didapat
$D_{n} = N - \sum_{i} N (P_{i}) + \sum_{i < j} N (P_{i} P_{j}) - \sum_{i < j < k} N (P_{i} P_{j} P_{k}) + \dots + (- 1)^{n} N (P_{1} P_{2} \dots P_{n})$ dengan $N$ menyatakan banyak permutasi dari $n$ objek. Persamaan di atas menyatakan bahwa banyak permutasi yang semua objeknya tidak berada di posisi semula sama dengan banyak permutasi secara keseluruhan, dikurang banyak permutasi yang minimal satu objeknya berada di posisi semula, ditambah banyak permutasi yang minimal dua objeknya berada di posisi semula, dan seterusnya. Dengan demikian, kita perlu mencari nilai dari setiap suku pada ruas kanan persamaan tersebut.

Pertama, perhatikan bahwa $N = n!$ yang menyatakan banyak permutasi dari $n$ objek. $N (P_{i}) = (n - 1)! .$ Ini berlaku sebagai akibat dari aturan perkalian karena $N (P_{i})$ menyatakan banyak permutasi yang membuat objek ke- $i$ tetap di posisi semula sehingga $(n - 1)$ objek lain dapat dipermutasi secara sembarang. Hal yang serupa juga berlaku untuk $N (P_{i} P_{j}) = (n - 2)!$ karena $(n - 2)$ objek lain dapat dipermutasi secara sembarang. Secara umum, berlaku
$N (P_{i_{1}} P_{i_{2}} \dots P_{i_{m}}) = (n - m)!$ karena $(n - m)$ objek lain dapat dipermutasi secara sembarang. Karena ada $C (n, m)$ cara untuk memilih $m$ dari $n$ objek, diperoleh
$\begin{aligned} \sum_{1 \leq i \leq n} N (P_{i}) & = C (n, 1) (n - 1)! \\ \sum_{1 \leq i < j \leq n} N (P_{i} P_{j}) & = C (n, 2) (n - 2)! \\ \dots & \dots \\ \sum_{1 \leq i_{i} < i_{2} < \dots < i_{m} \leq n} N (P_{i_{1}} P_{i_{2}} \dots P_{i_{m}}) & = C (n, m) (n - m)! . \end{aligned}$ Akibatnya, dengan substitusi nilai-nilai ini pada persamaan, diperoleh
$\begin{aligned} D_{n} & = n! - C (n, 1) (n - 1)! + C (n, 2) (n - 2)! - \dots + (- 1)^{n} C (n, n) (n - n)! \\ = n! - \frac{n!}{1! (n - 1)!} (n - 1)! + \frac{n!}{2! (n - 2)!} (n - 2)! - \dots + (- 1)^{n} \frac{n!}{n! \cdot 0!} 0! \\ = n! - \frac{n!}{1!} + \frac{n!}{2} - \dots + (- 1)^{n} \frac{n!}{n!} \\ = n! [1 - \frac{1}{1!} + \frac{1}{2!} - \dots + (- 1)^{n} \frac{1}{n!}] . \end{aligned}$ Jadi, teorema terbukti benar.

[collapse]

Berikut ini telah disediakan sejumlah soal dan pembahasan tentang penggunaan prinsip inklusi-eksklusi. Semoga dapat dijadikan sumber belajar.

Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Salah satu sumber yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

$\begin{array}{ccc} No. & Bahasa Indonesia & Bahasa Inggris \\ 1. & Prinsip Inklusi-Eksklusi & Inclusion-Exclusion Principle \\ 2. & Pencacahan Ganda & Double Counting \\ 3. & Saling Lepas Berpasangan & Pairwise Disjoint \\ 4. & Fungsi Pada & Onto Function \\ 5. & Bita & Byte \\ 6. & Untaian Bit & Bitstring \\ 7. & Peracakan & Derangement \\ 8. & Saringan Eratosthenes & Sieve of Eratosthenes \end{array}$

Quote by Michel de Montaigne

Kita dapat menjadi berpengetahuan dengan pengetahuan orang lain, tetapi kita tidak dapat menjadi bijaksana dengan menggunakan kearifan orang lain.

Bagian Pilihan Ganda

Soal Nomor 1

Kelas X terdiri dari $31$ siswa. Sebanyak $15$ siswa mengikuti kompetisi matematika, $13$ siswa mengikuti kompetisi IPA, dan $7$ siswa tidak mengikuti kompetisi tersebut. Banyak siswa yang mengikuti kedua kompetisi tersebut adalah $\dots \cdot$
A. $2$ siswa D. $5$ siswa
B. $3$ siswa E. $8$ siswa
C. $4$ siswa

Pembahasan

Misalkan $A$ menyatakan himpunan siswa yang mengikuti kompetisi matematika, sedangkan $B$ kompetisi IPA, serta $S$ menyatakan himpunan siswa kelas X sehingga ditulis
$\begin{aligned} | S | & = 31 \\ | A | & = 15 \\ | B | & = 13 \\ | A \cup B |^{c} & = 7 \end{aligned}$
Ini berarti
$\begin{aligned} | A \cup B | & = | S | - | A \cup B |^{c} \\ = 31 - 7 = 24. \end{aligned}$
Dengan demikian,
$\begin{aligned} | A \cap B | & = | A | + | B | - | A \cup B | \\ = 15 + 13 - 24 = 4. \end{aligned}$ Jadi, ada $4$ siswa yang mengikuti kedua kompetisi tersebut.
(Jawaban C)

[collapse]

Soal Nomor 2

Data kegiatan sarapan pagi $38$ orang siswa adalah sebagai berikut.
Ada $6$ orang yang sarapan dengan roti dan nasi goreng. Ada $5$ orang yang tidak sarapan pagi. Jika banyak siswa yang sarapan nasi goreng dua kali banyak siswa yang sarapan roti, maka banyak siswa yang sarapan nasi goreng saja adalah $\dots \cdot$
A. $35$ orang D. $20$ orang
B. $30$ orang E. $18$ orang
C. $25$ orang

Pembahasan

Misalkan $R$ dan $N$ berturut-turut menyatakan himpunan siswa yang sarapan dengan roti dan nasi goreng. Himpunan $S$ menyatakan himpunan seluruh siswa dalam kasus ini. Diketahui:
$\begin{aligned} | N | & = 2 | R | \\ | R \cap N | & = 6 \\ | (R \cap N)^{C} | & = 5 \\ | S | & = 38 \end{aligned}$ Menurut prinsip inklusi-eksklusi, berlaku
$\begin{aligned} | S | - | (R \cap N)^{C} | & = | R | + | N | - | R \cap N | \\ 38 - 5 & = | R | + 2 | R | - 6 \\ 33 & = 3 | R | - 6 \\ 39 & = 3 | R | \\ 13 & = | R | . \end{aligned}$ Banyak siswa yang sarapan dengan nasi goreng adalah $2 | R | = 2 (13) = 26$ orang. Oleh karena itu, banyak siswa yang sarapan dengan nasi goreng SAJA adalah $| N | - | R \cap N | = 26 - 6 = 20$ orang.
(Jawaban D)

[collapse]

Soal Nomor 3

Dari sekelompok anak terdapat $20$ anak gemar voli, $28$ anak gemar basket, dan $27$ anak gemar pingpong, $13$ anak gemar voli dan basket, $11$ anak gemar basket dan pingpong, $9$ anak gemar voli dan pingpong, serta $5$ anak gemar ketiga-tiganya. Jika dalam kelompok tersebut ada $55$ anak, banyak anak yang tidak gemar satu pun dari ketiga jenis permainan tersebut adalah $\dots \cdot$
A. $8$ anak D. $18$ anak
B. $13$ anak E. $20$ anak
C. $15$ anak

Pembahasan

Misalkan $V, B,$ dan $P$ berturut-turut menyatakan himpunan anak yang menggemari voli, basket, dan pingpong. Himpunan $S$ menyatakan himpunan seluruh anak di kelompok tersebut. Diketahui:
$\begin{matrix} V | = 20 & | B \cap P | = 11 \\ | B | = 28 & | V \cap P | = 9 \\ | P | = 27 & | V \cap B \cap P | = 5 \\ | V \cap B | = 13 & | S | = 55 \end{matrix}$ Misalkan $x$ menyatakan jumlah anak yang tidak gemar ketiga jenis permainan tersebut.
Berdasarkan prinsip inklusi-eksklusi, berlaku
$\begin{aligned} | S | - x & = | V | + | B | + | P | - | V \cap B | - | V \cap P | - | B \cap P | + | V \cap B \cap P | \\ x & = | S | - (| V | + | B | + | P |) + (| V \cap B | + | V \cap P | + | B \cap P |) - | V \cap B \cap P | \\ x & = 55 - (20 + 28 + 27) + (13 + 11 + 9) - 5 \\ = 55 - 75 + 33 - 5 = 8. \end{aligned}$ Jadi, ada $8 anak$ yang tidak gemar ketiga jenis permainan tersebut.
(Jawaban A)

[collapse]

Baca: Materi, Soal, dan Pembahasan – Relasi Rekurens Homogen Linear dengan Koefisien Konstan

Soal Nomor 4

Misalkan terdapat gantang yang berisikan $100$ buah apel. Sebanyak $20$ buah di antaranya berulat, sedangkan $15$ buah di antaranya memiliki kulit yang keriput (gejala kebusukan apel). Hanya apel yang tidak berulat dan tidak memiliki kulit yang keriput-lah yang boleh dijual. Jika terdapat $10$ buah apel berkulit keriput yang juga berulat, banyak apel yang boleh dijual adalah $\dots \cdot$
A. $85$ C. $75$ E. $55$
B. $80$ D. $60$

Pembahasan

Misalkan $| A |$ dan $| B |$ berturut-turut menyatakan banyak apel yang berulat dan memiliki kulit yang keriput. Menurut prinsip inklusi-eksklusi, banyak apel yang tidak berulat dan juga tidak memiliki kulit yang keriput sama dengan banyak apel seluruhnya dikurangi banyak apel yang berulat dan banyak apel yang memiliki kulit yang keriput, lalu ditambah banyak apel yang berulat sekaligus kulitnya keriput. Secara matematis, ditulis
$\begin{aligned} | (A \cup B)^{c} | & = 100 - (| A | + | B | - | A \cap B |) \\ = 100 - (20 + 15 - 10) \\ = 75. \end{aligned}$ Jadi, apel yang boleh dijual ada sebanyak $75$ buah.
(Jawaban C)

[collapse]

Soal Nomor 5

Dari $50$ siswa, $30$ siswa menyukai aritmetika, $30$ siswa menyukai geometri, dan $30$ siswa menyukai aljabar. Banyaknya siswa yang menyukai aritmetika dan geometri adalah $15$ orang. Banyaknya siswa yang menyukai aritmetika dan aljabar juga $15$ orang, sama halnya dengan yang menyukai aljabar dan geometri. Berapa banyak siswa yang menyukai ketiga-ketiganya?
A. $2$ siswa D. $5$ siswa
B. $3$ siswa E. $8$ siswa
C. $4$ siswa

Pembahasan

Misalkan $A$ menyatakan himpunan siswa yang menyukai aritmetika, $G$ geometri, dan $J$ aljabar, serta $S$ sebagai himpunan semesta. Untuk itu, diketahui
$\begin{aligned} | S | & = 50 \\ | A | & = 30 \\ | G | & = 30 \\ | J | & = 30 \\ | A \cap G | & = 15 \\ | A \cap J | & = 15 \\ | G \cap J | & = 15 \end{aligned}$
Ditanya: $| A \cap G \cap J |$
Menurut prinsip inklusi-eksklusi, berlaku
$\begin{aligned} | S | & = | A | + | G | + | J | - | A \cap G | - | A \cap J | - | G \cap J | + | A \cap G \cap J | \\ 50 & = 30 + 30 + 30 - 15 - 15 - 15 + | A \cap G \cap J | \\ 50 & = 45 + | A \cap G \cap J | \\ | A \cap G \cap J | & = 50 - 45 = 5. \end{aligned}$ Jadi, ada $5$ siswa yang menyukai aritmetika, geometri, dan aljabar sekaligus.
(Jawaban D)

[collapse]

Soal Nomor 6

Dari satu kelas terdata $\frac{5}{2}$ dari jumlah siswa yang menyukai matematika sekaligus fisika akan mengikuti olimpiade fisika. Empat kali dari jumlah siswa yang menyukai keduanya akan mengikuti olimpiade matematika. Jika jumlah seluruh siswa ada $44$ orang dan siswa yang mengikuti olimpiade secara otomatis menyukai pelajaran yang dilombakan, maka banyak siswa yang hanya mengikuti olimpiade matematika (hanya menyukai matematika) adalah $\dots$ orang.
A. $8$ C. $24$ E. $36$
B. $20$ D. $32$

Pembahasan

Misalkan $M$ dan $F$ berturut-turut menyatakan himpunan siswa yang menyukai matematika dan fisika. Diketahui:
$\begin{aligned} | F | & = \frac{5}{2} | F \cap M | \\ | M | & = 4 | F \cap M | \\ | F \cup M | & = 44. \end{aligned}$
Menurut prinsip inklusi-eksklusi, kita peroleh
$\begin{aligned} | F \cup M | & = | F | + | M | - | F \cap M | \\ 44 & = \frac{5}{2} | F \cap M | + 4 | F \cap M | - | F \cap M | \\ 44 & = (\frac{5}{2} + 4 - 1) | F \cap M | \\ 44 & = \frac{11}{2} | F \cap M | \\ | F \cap M | & = 44 \times \frac{2}{11} = 8. \end{aligned}$ Banyak siswa yang hanya mengikuti olimpiade matematika adalah $| M | - | F \cap M | = 4 (8) - 8 = 24$
(Jawaban C)

[collapse]

Soal Nomor 7

Dari $1.000$ pendaftar program perjalanan menuju puncak Gunung Merapi, sebanyak $450$ pendaftar mengalami mabuk ketinggian (altitude sickness), $622$ pendaftar dalam keadaan kurang bugar, dan $30$ pendaftar memiliki alergi. Seorang pendaftar dinyatakan lolos untuk mengikuti program jika dan hanya jika ia tidak mabuk ketinggian, dalam keadaan bugar, dan tidak memiliki alergi. Jika $111$ pendaftar mengalami mabuk ketinggian dan dalam keadaan kurang bugar, $14$ pendaftar mengalami mabuk ketinggian dan memiliki alergi, $18$ pendaftar dalam keadaan kurang bugar dan memiliki alergi, dan $9$ pendaftar mengalami mabuk ketinggian, dalam keadaan kurang bugar, dan memiliki alergi, maka berapa banyak pendaftar yang lolos?
A. $12$ orang. D. $32$ orang.
B. $18$ orang. E. $40$ orang.
C. $24$ orang.

Pembahasan

Misalkan $| M |, | B |,$ dan $| A |$ berturut-turut menyatakan banyak pendaftar yang mengalami mabuk ketinggian, dalam keadaan kurang bugar, dan memiliki alergi. Diketahui bahwa
$\begin{array}{ccc} | M | = 450 & | B | = 622 & | A | = 30 \\ | M \cap B | = 111 & | M \cap A | = 14 & | B \cap A | = 18 \\ | M \cap B \cap A | = 9. \end{array}$ Dalam kasus ini, kita akan menentukan nilai $| (M \cup B \cup A)^{c} | .$
Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} | (M \cup B \cup A)^{c} | & = 1.000 - (| M | + | B | + | A | - | M \cap B | - | M \cap A | - | B \cap A | + | M \cap B \cap A |) \\ = 1.000 - (450 + 622 + 30 - 111 - 14 - 18 + 9) \\ = 32. \end{aligned}$ Jadi, banyak pendaftar yang lolos adalah $32$ orang.
(Jawaban D)

[collapse]

Soal Nomor 8

Misalkan $A, B, C, D, E,$ dan $F$ merupakan himpunan takkosong. Dengan menggunakan prinsip inklusi-eksklusi, $| A \cup B \cup C \cup D \cup E \cup F |$ dinyatakan dalam berapa banyak suku?
A. $31$ suku. D. $63$ suku.
B. $45$ suku. E. $71$ suku.
C. $62$ suku.

Pembahasan

Untuk $6$ himpunan, banyak suku yang terlibat adalah
$\begin{aligned} n & = (\binom{6}{1}) + (\binom{6}{2}) + (\binom{6}{3}) + (\binom{6}{4}) + (\binom{6}{5}) + (\binom{6}{6}) \\ = 6 + 15 + 20 + 15 + 6 + 1 \\ = 63. \end{aligned}$ Catatan: $(\binom{6}{k})$ menyatakan banyaknya cara memilih $k$ dari $6$ himpunan tanpa memperhatikan urutan.
Jadi, $| A \cup B \cup C \cup D \cup E \cup F |$ dinyatakan dalam $63$ suku.
(Jawaban D)

[collapse]

Soal Nomor 9

Banyaknya bilangan bulat positif $\leq 100$ yang merupakan bilangan ganjil atau bilangan kuadrat adalah $\dots \cdot$
A. $40$ C. $50$ E. $65$
B. $45$ D. $55$

Pembahasan

Misalkan $G$ dan $K$ berturut-turut menyatakan himpunan bilangan ganjil ${1, 3, 5, \dots, 99}$ dan himpunan bilangan kuadrat ${1^{2}, 2^{2}, \dots, 10^{2}} .$ Ini berarti $| G | = 50$ dan $| K | = 10.$ Selain itu, $G \cap K = {1^{2}, 3^{2}, 5^{2}, 7^{2}, 9^{2}}$ sehingga $| G \cap K | = 5.$ Menurut prinsip inklusi-eksklusi, didapat
$\begin{aligned} | G \cup K | & = | G | + | K | - | G \cap K | \\ = 50 + 10 - 5 \\ = 55. \end{aligned}$ Jadi, ada $55$ bilangan bulat positif $\leq 100$ yang merupakan bilangan ganjil atau bilangan kuadrat.
(Jawaban D)

[collapse]

Soal Nomor 10

Dipilih suatu bilangan $4$ digit. Berapakah peluang bilangan tersebut habis dibagi $5$ atau $7$ ?
A. $\frac{617}{1.800}$ D. $\frac{943}{3.000}$
B. $\frac{617}{2.000}$ E. $\frac{2.829}{3.000}$
C. $\frac{707}{2.250}$

Pembahasan

Notasi $⌊ x ⌋$ menyatakan fungsi lantai dari $x$ , artinya bilangan bulat terbesar yang lebih kecil dari $x .$ Sebagai contoh, $⌊ 2, 83 ⌋ = 2$ dan $⌊ 4, 003 ⌋ = 4.$
Misalkan $A$ menyatakan himpunan bilangan 4 digit yang habis dibagi $5.$ Banyak anggota $A$ sama dengan banyak bilangan yang habis dibagi $5$ dari $1$ sampai $9.999$ dikurangi banyak bilangan yang habis dibagi $5$ dari $1$ sampai $999.$
$\begin{aligned} | A | & = ⌊ \frac{9.999}{5} ⌋ - ⌊ \frac{999}{5} ⌋ \\ = 1.999 - 199 \\ = 1.800 \end{aligned}$ Misalkan $B$ menyatakan himpunan bilangan 4 digit yang habis dibagi $7.$ Banyak anggota $B$ sama dengan banyak bilangan yang habis dibagi $7$ dari $1$ sampai $9.999$ dikurangi banyak bilangan yang habis dibagi $7$ dari $1$ sampai $999.$
$\begin{aligned} | B | & = ⌊ \frac{9.999}{7} ⌋ - ⌊ \frac{999}{7} ⌋ \\ = 1.428 - 142 \\ = 1.286 \end{aligned}$ Bilangan kelipatan $5$ dan $7$ (sekaligus) terhitung dua kali sehingga perlu dihitung banyaknya agar bisa dikurangi.
Misalkan $A \cap B$ menyatakan himpunan bilangan 4 digit yang habis dibagi $5$ dan $7$ , yaitu bilangan kelipatan $KPK (5, 7) = 35$ sehingga
$\begin{aligned} | A \cap B | & = ⌊ \frac{9.999}{35} ⌋ - ⌊ \frac{999}{35} ⌋ \\ = 285 - 28 \\ = 257 \end{aligned}$ Menurut prinsip inklusi-eksklusi, banyaknya bilangan 4 digit yang habis dibagi oleh $5$ atau $7$ adalah
$\begin{aligned} | A \cup B | & = | A | + | B | - | A \cap B | \\ = 1.800 + 1.286 - 257 \\ = 2.829 \end{aligned}$ Jadi, terdapat $2.829$ bilangan 4 digit yang memenuhi kondisi tersebut.

Karena banyak bilangan 4 digit semuanya (dari $1.000$ sampai $9.999$ ) ada $9.000,$ maka peluang yang dimaksud sebesar $\frac{2.829}{9.000} = \frac{943}{3.000}$
(Jawaban D)

[collapse]

Baca: Materi, Soal, dan Pembahasan – Fungsi Lantai dan Fungsi Atap

Soal Nomor 11

Suatu bilangan bulat positif dikatakan bebas kuadrat (squarefree) jika bilangan bulat itu tidak habis dibagi oleh bilangan kuadrat yang lebih besar dari $1.$ Contoh bilangan bebas kuadrat adalah $1$ dan $14.$ Banyak bilangan bebas kuadrat yang kurang dari $100$ adalah $\dots \cdot$
A. $52$ C. $61$ E. $69$
B. $57$ D. $65$

Pembahasan

Misalkan $| A |, | B |, | C |,$ dan $| D |$ berturut-turut menyatakan banyak bilangan yang habis dibagi $2^{2} = 4,$ $3^{2} = 9,$ $5^{2} = 25,$ dan $7^{2} = 49$ pada selang bilangan bulat dari $1$ sampai $99$ (ada $99$ bilangan). Ini berarti bilangan bebas kuadrat dari $1$ sampai $99$ adalah bilangan yang memiliki karakteristik tidak habis dibagi oleh $4, 9, 25,$ dan $49.$
Diketahui bahwa
$\begin{aligned} | A | & = ⌊ \frac{99}{4} ⌋ = 24 \\ | B | & = ⌊ \frac{99}{9} ⌋ = 11 \\ | C | & = ⌊ \frac{99}{25} ⌋ = 3 \\ | D | & = ⌊ \frac{99}{49} ⌋ = 2 \\ | A \cap B | & = ⌊ \frac{99}{4 \times 9} ⌋ = 2 \end{aligned}$ dan bernilai $0$ untuk kombinasi suku-suku lainnya.
Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} | (A \cup B \cup C \cup D)^{c} | & = 99 - (| A | + | B | + | C | + | D | - | A \cap B |) \\ = 99 - (24 + 11 + 3 + 2 - 2) \\ = 61. \end{aligned}$ Jadi, ada $61$ bilangan bebas kuadrat yang kurang dari $100.$
(Jawaban C)

[collapse]

Soal Nomor 12

Banyak solusi dari persamaan $x_{1} + x_{2} + x_{3} = 13$ dengan $x_{1}, x_{2},$ dan $x_{3}$ merupakan bilangan bulat nonnegatif yang masing-masing nilainya kurang dari $6$ adalah $\dots \cdot$
A. $4$ C. $8$ E. $36$
B. $6$ D. $12$

Pembahasan

Misalkan $| A |, | B |,$ dan $| C |$ berturut-turut menyatakan banyak solusi persamaan ketika $x_{1} \geq 6,$ $x_{2} \geq 6,$ dan $x_{3} \geq 6.$
Dengan menggunakan teorema bintang dan garis (kombinasi berulang), diperoleh informasi berikut.
$\begin{aligned} | A | & = | B | = | C | = (\binom{7 + 3 - 1}{3 - 1}) = (\binom{9}{2}) = 36 \\ | A \cap B | & = | A \cap C | = | B \cap C | = (\binom{1 + 3 - 1}{3 - 1}) = (\binom{3}{2}) = 3 \\ | A \cap B \cap C | & = 0 \end{aligned}$ Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} | (A \cup B \cup C)^{c} | & = (\binom{13 + 3 - 1}{3 - 1}) - (| A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |) \\ = (\binom{15}{2}) - (36 + 36 + 36 - 3 - 3 - 3 + 0) \\ = 105 - 99 \\ = 6. \end{aligned}$ Jadi, banyak solusi dari persamaan tersebut dengan kriteria yang diberikan adalah $6$
(Jawaban B)

[collapse]

Soal Nomor 13

Banyak solusi dari persamaan $x_{1} + x_{2} + x_{3} + x_{4} = 17$ dengan $x_{i}, i \in {1, 2, 3, 4}$ merupakan bilangan bulat nonnegatif yang memenuhi $x_{1} \leq 3,$ $x_{2} \leq 4,$ $x_{3} \leq 5,$ dan $x_{4} \leq 8$ adalah $\dots \cdot$
A. $9$ C. $15$ E. $35$
B. $13$ D. $20$

Pembahasan

Misalkan $| A |, | B |,$ $| C |,$ dan $| D |$ berturut-turut menyatakan banyak solusi persamaan ketika $x_{1} > 3,$ $x_{2} > 4,$ $x_{3} > 5,$ dan $x_{4} > 8.$
Dengan menggunakan teorema bintang dan garis (kombinasi berulang), diperoleh informasi berikut.
$\begin{aligned} | A | & = (\binom{13 + 4 - 1}{4 - 1}) = (\binom{16}{3}) = 560 \\ | B | & = (\binom{12 + 4 - 1}{4 - 1}) = (\binom{15}{3}) = 455 \\ | C | & = (\binom{11 + 4 - 1}{4 - 1}) = (\binom{14}{3}) = 364 \\ | D | & = (\binom{8 + 4 - 1}{4 - 1}) = (\binom{11}{3}) = 165 \\ | A \cap B | & = (\binom{8 + 4 - 1}{4 - 1}) = (\binom{11}{3}) = 165 \\ | A \cap C | & = (\binom{7 + 4 - 1}{4 - 1}) = (\binom{10}{3}) = 120 \\ | A \cap D | & = (\binom{4 + 4 - 1}{4 - 1}) = (\binom{7}{3}) = 35 \\ | B \cap C | & = (\binom{6 + 4 - 1}{4 - 1}) = (\binom{9}{3}) = 84 \\ | B \cap D | & = (\binom{3 + 4 - 1}{4 - 1}) = (\binom{6}{3}) = 20 \\ | C \cap D | & = (\binom{2 + 4 - 1}{4 - 1}) = (\binom{5}{3}) = 10 \\ | A \cap B \cap C | & = (\binom{2 + 4 - 1}{4 - 1}) = (\binom{5}{3}) = 10 \\ | A \cap B \cap D | & = 0 \\ | A \cap C \cap D | & = 0 \\ | B \cap C \cap D | & = 0 \\ | A \cap B \cap C \cap D | & = 0 \end{aligned}$ Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} | (A \cup B \cup C \cup D)^{c} | = & (\binom{17 + 4 - 1}{4 - 1}) - (| A | + | B | + | C | + | D | - | A \cap B | - | A \cap C | - | A \cap D | - | B \cap C | - | B \cap D | - | C \cap D | + \\ | A \cap B \cap C | + | A \cap B \cap D | + | A \cap C \cap D | + | B \cap C \cap D | - | A \cap B \cap C \cap D |) \\ = & (\binom{20}{3}) - (560 + 455 + 364 + 165 - 165 - 120 - 35 - 84 - 20 - 10 + 10 + 0 + 0 + 0 - 0) \\ = & 1.140 - 1.125 \\ = & 15. \end{aligned}$ Jadi, banyak solusi dari persamaan tersebut dengan kriteria yang diberikan adalah $15$
(Jawaban C)

[collapse]

Soal Nomor 14

Pada suatu acara perpisahan, $6$ orang yang saling bersahabat melakukan tukar kado. Setiap orang membawa tepat satu kado. Kado dari setiap orang dikumpulkan, kemudian dibagikan kembali secara acak. Peluang kejadian tidak ada orang yang mendapatkan kadonya sendiri adalah $\dots \cdot$
A. $\frac{49}{144}$ D. $\frac{53}{720}$
B. $\frac{53}{144}$ E. $\frac{59}{720}$
C. $\frac{59}{144}$

Pembahasan

Kasus ini analog dengan mencari banyak peracakan dari $6$ objek. Berdasarkan teorema peracakan, diperoleh banyak peracakannya adalah
$\begin{aligned} N & = 6! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!}) \\ = 265. \end{aligned}$ Karena banyak permutasi dari $6$ objek adalah $6! = 720,$ peluang kejadian tidak ada orang yang mendapatkan kadonya sendiri adalah $\frac{265}{720} = \frac{53}{144}$
(Jawaban B)

[collapse]

Bagian Uraian

Soal Nomor 1

Dalam suatu kelas terdapat $23$ siswa yang menyukai matematika, sedangkan $18$ siswa menyukai fisika. Jika $8$ orang di antaranya menyukai keduanya, berapa banyak siswa di dalam kelas tersebut?

Pembahasan

Misalkan $A$ adalah himpunan siswa yang menyukai matematika dan $B$ adalah himpunan siswa yang menyukai fisika sehingga $A \cap B$ menyatakan himpunan siswa yang menyukai keduanya. Banyaknya siswa yang menyukai salah satu mata pelajaran tersebut atau keduanya dinyatakan oleh himpunan $A \cup B .$ Dengan demikian,
$\begin{aligned} | A \cup B | & = | A | + | B | - | A \cap B | \\ = 23 + 18 - 8 \\ = 33. \end{aligned}$ Jadi, ada $33$ siswa di dalam kelas tersebut.

[collapse]

Soal Nomor 2

Suatu survei terkait penggunaan kipas angin dan AC dilakukan pada rumah penduduk di desa X. Dari survei tersebut, diperoleh informasi bahwa AC terpasang pada $96 %$ rumah, kipas angin terpasang pada $98 %$ rumah, dan dua peralatan elektronik tersebut terpasang pada $95 %$ rumah. Berapa persen rumah penduduk di desa X yang tidak terpasang kipas angin maupun AC?

Pembahasan

Asumsikan persentase sebagai kardinalitas dari himpunan dengan menganggap rumah penduduk ada sebanyak $100.$
Misalkan $K$ dan $A$ berturut-turut menyatakan rumah penduduk di desa X yang terpasang kipas angin dan AC. Ini berarti $| K | = 98,$ $| A | = 96,$ dan $| K \cap A | = 95.$ Dengan menggunakan prinsip inklusi-eksklusi, persentase rumah penduduk di desa X yang terpasang kipas angin atau AC adalah
$\begin{aligned} | K \cup A | & = | K | + | A | - | K \cap A | \\ = 98 + 96 - 95 \\ = 99. \end{aligned}$ Sebaliknya, didapat bahwa sebanyak $1 %$ rumah penduduk di desa X yang tidak terpasang kipas angin maupun AC.

[collapse]

Soal Nomor 3

Berapa banyak elemen di $A_{1} \cup A_{2}$ jika diketahui terdapat $12$ elemen di $A_{1},$ $18$ elemen di $A_{2},$ dan
a. $A_{1} \cap A_{2} = \emptyset$ ?
b. $| A_{1} \cap A_{2} | = 1$ ?
c. $| A_{1} \cap A_{2} | = 6$ ?
d. $A_{1} \subseteq A_{2}$ ?

Pembahasan

Diketahui $| A_{1} | = 12$ dan $| A_{2} | = 18.$ Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} | A_{1} \cup A_{2} | & = | A_{1} | + | A_{2} | - | A_{1} \cap A_{2} | \\ = 12 + 18 - | A_{1} \cap A_{2} | \\ = 30 - | A_{1} \cap A_{2} | . \end{aligned}$ Jawaban a)
Karena $A_{1} \cap A_{2} = \emptyset,$ haruslah $| A_{1} \cap A_{2} | = 0$ (dua himpunan tersebut saling lepas). Akibatnya, $| A_{1} \cup A_{2} | = 30 - 0 = 30.$ Jadi, banyak elemen di $A_{1} \cup A_{2}$ adalah $30$
Jawaban b)
Karena $| A_{1} \cap A_{2} | = 1,$ didapat $| A_{1} \cup A_{2} | = 30 - 1 = 29.$ Jadi, banyak elemen di $A_{1} \cup A_{2}$ adalah $29$
Jawaban c)
Karena $| A_{1} \cap A_{2} | = 6,$ didapat $| A_{1} \cup A_{2} | = 30 - 6 = 24.$ Jadi, banyak elemen di $A_{1} \cup A_{2}$ adalah $24$
Jawaban d)
Karena $A_{1} \subseteq A_{2},$ haruslah $A_{1} \cap A_{2} = A_{1} .$ Akibatnya, $| A_{1} \cap A_{2} | = | A_{1} | = 12$ sehingga $| A_{1} \cup A_{2} | = 30 - 12 = 18.$ Jadi, banyak elemen di $A_{1} \cup A_{2}$ adalah $18$

[collapse]

Soal Nomor 4

Tentukan banyak elemen di $A_{1} \cup A_{2} \cup A_{3}$ jika terdapat $100$ elemen pada masing-masing himpunan dan

himpunannya saling lepas berpasangan (pairwise disjoint).
ada $50$ elemen yang sama pada tiap pasang himpunan serta tidak ada elemen yang menjadi irisan dari tiga himpunan tersebut.
ada $50$ elemen yang sama pada tiap pasang himpunan serta ada $25$ elemen yang menjadi irisan dari tiga himpunan tersebut.
tiga himpunan itu sama (equal).

Pembahasan

Diketahui $| A_{1} | = | A_{2} | = | A_{3} | = 100.$
Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$| A_{1} \cup A_{2} \cup A_{3} | = | A_{1} | + | A_{2} | + | A_{3} | - | A_{1} \cap A_{2} | - | A_{1} \cap A_{3} | - | A_{2} \cap A_{3} | + | A_{1} \cap A_{2} \cap A_{3} | .$ Jawaban a)
Jika setiap dua himpunan saling lepas, didapat $| A_{1} \cap A_{2} | = | A_{1} \cap A_{3} | = | A_{2} \cap A_{3} | = | A_{1} \cap A_{2} \cap A_{3} | = 0.$ Jadi, $\begin{aligned} | A_{1} \cup A_{2} \cup A_{3} | & = | A_{1} | + | A_{2} | + | A_{3} | \\ = 100 + 100 + 100 \\ = 300. \end{aligned}$ Dengan demikian, banyak elemen di $A_{1} \cup A_{2} \cup A_{3}$ dengan kondisi seperti itu adalah $300$ elemen.
Jawaban b)
Diketahui $| A_{1} \cap A_{2} | = | A_{1} \cap A_{3} | = | A_{2} \cap A_{3} | = 50$ dan $| A_{1} \cap A_{2} \cap A_{3} | = 0$ sehingga diperoleh
$| A_{1} \cup A_{2} \cup A_{3} | = 100 + 100 + 100 - 50 - 50 - 50 + 0 = 150.$ Dengan demikian, banyak elemen di $A_{1} \cup A_{2} \cup A_{3}$ dengan kondisi seperti itu adalah $150$ elemen.
Jawaban c)
Diketahui $| A_{1} \cap A_{2} | = | A_{1} \cap A_{3} | = | A_{2} \cap A_{3} | = 50$ dan $| A_{1} \cap A_{2} \cap A_{3} | = 25$ sehingga diperoleh
$| A_{1} \cup A_{2} \cup A_{3} | = 100 + 100 + 100 - 50 - 50 - 50 + 25 = 175.$ Dengan demikian, banyak elemen di $A_{1} \cup A_{2} \cup A_{3}$ dengan kondisi seperti itu adalah $175$ elemen.
Jawaban d)
Jika tiga himpunan itu sama ( $A_{1} = A_{2} = A_{3}$ ), jelas bahwa $| A_{1} \cup A_{2} \cup A_{3} | = | A_{1} | = | A_{2} | = | A_{3} | = 100.$ Dengan demikian, banyak elemen di $A_{1} \cup A_{2} \cup A_{3}$ dengan kondisi seperti itu adalah $100$ elemen.

[collapse]

Soal Nomor 5

Informasi terkecil yang dapat disimpan di dalam memori komputer adalah bita (byte). Setiap bita disusun oleh $8$ bit. Berapa banyak bita yang dimulai dengan $11$ atau berakhir dengan $11 ?$

Pembahasan

Misalkan
$\begin{aligned} A & = himpunan bita yang dimulai dengan 11 \\ B & = himpunan bita yang diakhiri dengan 11 \\ A \cap B & = himpunan bita yang dimulai dan diakhiri dengan 11 . \end{aligned}$ sehingga
$A \cup B = himpunan bita yang dimulai atau diakhiri dengan 11 .$ Perhatikan sketsa gambar berikut.
Jumlah bita yang dimulai dengan $11$ ada $2^{6} = 64$ karena $2$ posisi pertama sudah diisi sehingga kita hanya perlu mengisi $6$ posisi lainnya dengan $2$ pilihan angka, yaitu $0$ dan $1.$ Jadi, $| A | = 64.$
Hal yang demikian juga berlaku untuk jumlah bita yang diakhiri dengan $11,$ yaitu ada $2^{6} = 64$ karena $2$ posisi terakhir sudah diisi sehingga kita hanya perlu mengisi $6$ posisi lainnya dengan $2$ pilihan angka, yaitu $0$ dan $1.$ Jadi, $| B | = 64.$
Jumlah bita yang berawal dan berakhir dengan $11$ ada sebanyak $2^{4} = 16$ karena sekarang tersisa $4$ posisi yang dapat diisi. Jadi, $| A \cap B | = 16.$
Dengan menggunakan prinsip inklusi-eksklusi, jumlah bita yang dimulai atau diakhiri dengan $11$ ada sebanyak
$\begin{aligned} | A \cup B | & = | A | + | B | - | A \cap B | \\ = 64 + 64 - 16 \\ = 112. \end{aligned}$

[collapse]

Soal Nomor 6

Ada berapa bilangan bulat positif yang lebih kecil atau sama dengan $100$ yang habis dibagi oleh $6$ atau $9 ?$

Pembahasan

Notasi $⌊ x ⌋$ menyatakan fungsi lantai dari $x$ , artinya bilangan bulat terbesar yang lebih kecil dari $x .$ Sebagai contoh, $⌊ 2, 83 ⌋ = 2$ dan $⌊ 4, 003 ⌋ = 4.$
Misalkan $A$ menyatakan himpunan bilangan bulat positif $\leq 100$ yang habis dibagi $6$ sehingga
$| A | = ⌊ \frac{100}{6} ⌋ = 16.$ Misalkan $B$ menyatakan himpunan bilangan bulat positif $\leq 100$ yang habis dibagi $9$ sehingga
$| B | = ⌊ \frac{100}{9} ⌋ = 11.$ Bilangan kelipatan $6$ dan $9$ (sekaligus) terhitung dua kali sehingga perlu dihitung banyaknya agar bisa dikurangi.
Misalkan $A \cap B$ menyatakan himpunan bilangan bulat positif $\leq 100$ yang habis dibagi $6$ dan $9$ , yaitu bilangan kelipatan $KPK (6, 9) = 18$ sehingga
$| A \cap B | = ⌊ \frac{100}{18} ⌋ = 5.$ Menurut prinsip inklusi-eksklusi, banyaknya bilangan bulat positif yang lebih kecil atau sama dengan $100$ yang habis dibagi oleh $6$ atau $9$ adalah
$\begin{aligned} | A \cup B | & = | A | + | B | - | A \cap B | \\ = 16 + 11 - 5 \\ = 22. \end{aligned}$ Jadi, terdapat $22$ bilangan bulat positif yang memenuhi kondisi tersebut.

[collapse]

Soal Nomor 7

Berapa banyak bilangan bulat positif yang tidak melampaui $1.000$ dan habis dibagi oleh $7$ atau $11$ ?

Pembahasan

Misalkan $A$ menyatakan himpunan bilangan bulat positif $\leq 1.000$ yang habis dibagi $7$ sehingga
$| A | = ⌊ \frac{1.000}{7} ⌋ = 142.$ Misalkan $B$ menyatakan himpunan bilangan bulat positif $\leq 1.000$ yang habis dibagi $11$ sehingga
$| B | = ⌊ \frac{1.000}{11} ⌋ = 90.$ Bilangan kelipatan $7$ dan $11$ (sekaligus) terhitung dua kali sehingga perlu dihitung banyaknya agar bisa dikurangi.
Misalkan $A \cap B$ menyatakan himpunan bilangan bulat positif $\leq 1.000$ yang habis dibagi $7$ dan $11$ , yaitu bilangan kelipatan $77$ sehingga
$| A \cap B | = ⌊ \frac{1.000}{77} ⌋ = 12.$ Menurut prinsip inklusi-eksklusi, banyaknya bilangan bulat positif yang tidak melampaui $1.000$ dan habis dibagi oleh $7$ atau $11$ adalah
$\begin{aligned} | A \cup B | & = | A | + | B | - | A \cap B | \\ = 142 + 90 - 12 \\ = 220. \end{aligned}$ Jadi, terdapat $220$ bilangan bulat positif yang tidak melampaui $1.000$ dan habis dibagi oleh $7$ atau $11.$

[collapse]

Soal Nomor 8

Berapa banyak bilangan bulat positif yang tidak melampaui $1.000$ dan habis dibagi oleh $5, 7,$ atau $11 ?$

Pembahasan

Misalkan $A$ menyatakan himpunan bilangan bulat positif $\leq 1.000$ yang habis dibagi $5$ sehingga
$| A | = ⌊ \frac{1.000}{5} ⌋ = 200.$ Misalkan $B$ menyatakan himpunan bilangan bulat positif $\leq 1.000$ yang habis dibagi $7$ sehingga
$| A | = ⌊ \frac{1.000}{7} ⌋ = 142.$ Misalkan $C$ menyatakan himpunan bilangan bulat positif $\leq 1.000$ yang habis dibagi $11$ sehingga
$| C | = ⌊ \frac{1.000}{11} ⌋ = 90.$ Berikutnya, kita perlu mencari kardinalitas dari irisan dua himpunan dan tiga himpunan.
$\begin{aligned} | A \cap B | & = ⌊ \frac{1.000}{KPK (5, 7)} ⌋ = ⌊ \frac{1.000}{35} ⌋ = 28 \\ | A \cap C | & = ⌊ \frac{1.000}{KPK (5, 11)} ⌋ = ⌊ \frac{1.000}{55} ⌋ = 18 \\ | B \cap C | & = ⌊ \frac{1.000}{KPK (7, 11)} ⌋ = ⌊ \frac{1.000}{77} ⌋ = 12 \\ | A \cap B \cap C | & = ⌊ \frac{1.000}{KPK (5, 7, 11)} ⌋ = ⌊ \frac{1.000}{385} ⌋ = 2 \end{aligned}$
Menurut prinsip inklusi-eksklusi, banyaknya bilangan bulat positif yang tidak melampaui $1.000$ dan habis dibagi oleh $5, 7,$ atau $11$ adalah
$\begin{aligned} | A \cup B \cup C | & = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C | \\ = 200 + 142 + 90 - 28 - 18 - 12 + 2 \\ = 376. \end{aligned}$ Jadi, terdapat $376$ bilangan bulat positif yang memenuhi kondisi tersebut.

[collapse]

Soal Nomor 9

Berapa banyak untaian bit dengan panjang $8$ yang dimulai dengan $1$ atau berakhir dengan $00 ?$

Pembahasan

Untuk memperjelas masalah, contoh untaian bit dengan panjang $8$ adalah $10001100,$ $11110000,$ dan sebagainya.
Kasus 1:
Misalkan $A$ adalah kejadian munculnya untaian bit dengan panjang $8$ yang dimulai dengan $1.$ Hanya ada $1$ cara untuk mengisi bit pertama, sedangkan masing-masing ada $2$ cara untuk mengisi tujuh bit lainnya. Jadi, banyak untaian bit yang dapat dibuat adalah $| A | = 1 \times 2^{7} = 128.$
Kasus 2:
Misalkan $B$ adalah kejadian munculnya untaian bit dengan panjang $8$ yang berakhir dengan $00.$ Masing-masing ada $2$ cara untuk mengisi bit pertama sampai bit keenam, sedangkan bit ketujuh dan kedelapan hanya dapat diisi oleh $0$ sehingga ada $1$ cara saja. Jadi, banyak untaian bit yang dapat dibuat adalah $| B | = 2^{6} \times 1^{2} = 64.$

Perhatikan bahwa Kasus 1 dan Kasus 2 dapat terjadi secara bersamaan, yaitu ketika untaian bit dengan panjang $8$ dimulai dengan $1$ dan berakhir dengan $00.$ Jadi, kita perlu tinjau dua kasus ini sekaligus. Pada untaian bit tersebut, bit pertama, bit ketujuh, dan bit kedelapan hanya dapat diisi dengan $1$ cara, sedangkan lima bit lainnya dapat diisi dengan $2$ cara. Jadi, banyak untaian bit yang dapat dibuat adalah $| A \cap B | = 1^{3} \times 2^{5} = 32.$

Dengan menggunakan PIE, banyak untaian bit dengan panjang $8$ yang dimulai dengan $1$ atau berakhir dengan $00$ adalah $| A | + | B | - | A \cap B | = 128 + 64 - 32 = 160$

[collapse]

Soal Nomor 10

Berapa banyak bilangan bulat positif kurang dari $10.000$ yang bukan merupakan bilangan hasil pangkat dua atau lebih?

Pembahasan

Masalah di atas dapat diselesaikan dengan menggunakan prinsip inklusi-eksklusi jika menggunakan pendekatan seperti berikut. Pertama, tinjau bilangan bulat positif yang lebih besar dari $1.$ Jika bilangan $N$ merupakan hasil pangkat dari suatu bilangan bulat, maka jelas bahwa pangkat tersebut bernilai prima. Jika tidak demikian, berarti $N = x^{k}$ dengan $k = m p$ dan $p$ merupakan bilangan prima, padahal dapat ditulis $N = (x^{m})^{p} .$ Oleh karena itu, cukup tinjau bilangan hasil pangkat $2, 3, 5, 7$ , dan bilangan-bilangan prima berikutnya.
Misalkan $| A |, | B |, | C |,$ $| D |, | E |,$ dan $| F |$ berturut-turut menyatakan banyak bilangan hasil pangkat $2, 3, 5, 7,$ $11,$ dan $13.$ Perhatikan bahwa bilangan hasil pangkat $17$ (dan seterusnya) tidak ditinjau karena $2^{17} \geq 10.000 .$ Dengan demikian, diperoleh
$\begin{aligned} | A | & = ⌊ \sqrt{9999} ⌋ - 1 = 98 & (2^{2} sampai 99^{2}) \\ | B | & = ⌊ \sqrt[3]{9999} ⌋ - 1 = 20 & (2^{3} sampai 21^{3}) \\ | C | & = ⌊ \sqrt[5]{9999} ⌋ - 1 = 5 & (2^{5} sampai 6^{5}) \\ | D | & = ⌊ \sqrt[7]{9999} ⌋ - 1 = 2 & (2^{7} dan 3^{7}) \\ | E | & = ⌊ \sqrt[11]{9999} ⌋ - 1 = 1 & (2^{11}) \\ | F | & = ⌊ \sqrt[13]{9999} ⌋ - 1 = 1. & (2^{13}) \end{aligned}$ Namun, pencacahan ganda (double counting) terjadi. Ada $⌊ \sqrt[6]{9999} ⌋ - 1 = 3$ bilangan berpangkat $2 \times 3 = 6$ yang dihitung dua kali sebagai bilangan berpangkat $2$ dan $3.$ Selain itu, ada $⌊ \sqrt[10]{9999} ⌋ - 1 = 1$ bilangan berpangkat $2 \times 5 = 10$ yang dihitung dua kali sebagai bilangan berpangkat $2$ dan $5.$ Pencacahan ganda hanya terjadi pada dua kasus ini. Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} | (A \cup B \cup C \cup D \cup E \cup F)^{c} | & = 9.998 - (98 + 20 + 5 + 2 + 1 + 1 - 3 - 1) \\ = 9.875 . \end{aligned}$ Jadi, ada $9.875$ bilangan bulat positif kurang dari $10.000$ yang bukan merupakan hasil bilangan berpangkat dua atau lebih.

[collapse]

Soal Nomor 11

Berapa banyak fungsi surjektif (fungsi pada) dari himpunan beranggotakan $7$ elemen ke himpunan beranggotakan $5$ elemen?
Catatan: Suatu fungsi $f : X \to Y$ dikatakan surjektif jika untuk setiap elemen $y \in Y,$ terdapat elemen $x \in X$ sehingga $f (x) = y .$

Pembahasan

Misalkan fungsi $f : X \to Y$ dengan $| X | = 7,$ $| Y | = 5,$ dan $Y = {y_{1}, y_{2}, \dots, y_{5}} .$
Diketahui banyak fungsi $f$ tanpa syarat apa pun adalah $5^{7} = 78.125 .$ Diketahui pula banyak fungsi $f$ sehingga $y_{1}$ tidak memiliki prapeta adalah $4^{7} .$ Hal ini simetris dengan kejadian ketika $y_{2}, y_{3}, y_{4},$ dan $y_{5}$ tidak memiliki prapeta sehingga dapat dipersingkat perhitungannya dengan menggunakan aturan kombinasi, yaitu dengan memilih $1$ dari $5$ elemen $Y .$ Ini berarti ada $(\binom{5}{1}) 4^{7}$ fungsi berbeda yang dapat dibuat.
Dengan cara yang serupa, banyak fungsi $f$ sehingga terdapat pasangan dua elemen $B$ yang tidak memiliki prapeta (pilih $2$ dari $5$ ) adalah $(\binom{5}{2}) 3^{7},$ dan begitu seterusnya. Menurut prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} N & = 78.125 - ((\binom{5}{1}) 4^{7} - (\binom{5}{2}) 3^{7} + (\binom{5}{3}) 2^{7} - (\binom{5}{4}) 1^{7} + (\binom{5}{5}) 0^{7}) \\ = 78.125 - (81.920 - 21.870 + 1.280 - 5 + 0) \\ = 16.800 . \end{aligned}$ Jadi, ada $16.800$ fungsi surjektif (fungsi pada) dari himpunan beranggotakan $7$ elemen ke himpunan beranggotakan $5$ elemen.

[collapse]

Teorema: Banyak Fungsi Surjektif

Misalkan

m

dan

n

merupakan bilangan bulat positif dengan

m \geq n .

Terdapat

n^{m} - ((\binom{n}{1}) (n - 1)^{m} + (\binom{n}{2}) (n - 2)^{m} - \dots + (- 1)^{n - 1} (\binom{n}{n - 1}) (1)^{m})

fungsi surjektif dari himpunan beranggotakan

m

elemen ke himpunan beranggotakan

n

elemen.

Soal Nomor 12

Berapa banyak cara mendistribusikan $6$ mainan berbeda pada $3$ anak berbeda sehingga masing-masing anak mendapatkan setidaknya satu mainan?

Pembahasan

Kasus ini analog dengan mencari banyak fungsi surjektif dari himpunan yang beranggotakan $6$ elemen (mainan) ke himpunan yang beranggotakan $3$ elemen (anak-anak) karena masing-masing mainan diberikan pada satu anak (mengikuti definisi fungsi). Dengan menggunakan teorema untuk mencari banyak fungsi surjektif, terdapat $3^{6} - ((\binom{3}{1}) 2^{6} - (\binom{3}{2}) 1^{6}) = 540$ fungsi surjektif. Ini berarti ada $540$ cara mendistribusikan $6$ mainan berbeda pada $3$ anak berbeda sehingga masing-masing anak mendapatkan setidaknya satu mainan.

[collapse]

Soal Nomor 13

Berapa banyak cara mendistribusikan $8$ bola berbeda ke dalam $3$ kotak berbeda sehingga setiap kotak harus memuat setidaknya satu bola?

Pembahasan

Kasus ini analog dengan mencari banyak fungsi surjektif dari himpunan yang beranggotakan $8$ elemen (bola) ke himpunan yang beranggotakan $3$ elemen (kotak) karena masing-masing bola diberikan pada satu kotak (mengikuti definisi fungsi). Dengan menggunakan teorema untuk mencari banyak fungsi surjektif, terdapat $3^{8} - ((\binom{3}{1}) 2^{8} - (\binom{3}{2}) 1^{8}) = 5.796$ fungsi surjektif. Ini berarti ada $5.796$ cara mendistribusikan $8$ bola berbeda ke dalam $3$ kotak berbeda sehingga setiap kotak harus memuat setidaknya satu bola.

[collapse]

Soal Nomor 14

Berapa banyak cara untuk menugaskan $7$ pekerjaan berbeda pada $4$ karyawan berbeda sehingga masing-masing karyawan mendapatkan setidaknya satu pekerjaan dan pekerjaan paling sulit ditugaskan kepada karyawan terbaik?
Catatan: Pekerjaan paling sulit dan karyawan terbaik masing-masing hanya ada satu.

Pembahasan

Pertama, abaikan terlebih dahulu ketentuan bahwa pekerjaan paling sulit ditugaskan kepada karyawan terbaik (artinya satu pekerjaan tertentu hanya dapat dikerjakan oleh satu karyawan tertentu). Kasus menjadi analog dengan mencari banyak fungsi surjektif dari himpunan yang beranggotakan $7$ elemen (pekerjaan) ke himpunan yang beranggotakan $4$ elemen (karyawan) karena masing-masing pekerjaan ditugaskan pada satu karyawan (mengikuti definisi fungsi). Dengan menggunakan teorema banyak fungsi surjektif, terdapat $4^{7} - ((\binom{4}{1}) 3^{7} - (\binom{4}{2}) 2^{7} + (\binom{4}{1}) 1^{7}) = 8.400$ fungsi surjektif. Ini berarti ada $8.400$ cara untuk menugaskan $7$ pekerjaan berbeda pada $4$ karyawan berbeda sehingga masing-masing karyawan mendapatkan setidaknya satu pekerjaan. Karena ada $4$ karyawan, banyak cara agar satu pekerjaan tertentu dikerjakan oleh salah satu dari $4$ karyawan tersebut (yang sifatnya simetris) adalah $\frac{1}{4} \cdot 8.400 = 2.100$
Catatan: Jika karyawan tersebut bernama $A, B, C,$ dan $D,$ banyak cara agar pekerjaan tersulit diberikan pada $A, B, C,$ dan $D$ masing-masing adalah sama, yaitu $2.100$ cara. Inilah yang dimaksud dengan “simetris” pada kalimat di atas.

[collapse]

Soal Nomor 15

Carilah banyaknya bilangan prima yang tidak melebihi $200$ dengan menggunakan prinsip inklusi-eksklusi.
Catatan: Saringan Eratosthenes merupakan prosedur yang dipakai untuk menentukan banyak bilangan prima yang kurang dari atau sama dengan bilangan bulat tertentu.

Pembahasan

Karena $1$ bukan bilangan prima, kita hanya meninjau $199$ bilangan, yaitu dari $2$ sampai $200.$ Ide utama yang dipakai adalah fakta bahwa bilangan komposit pada interval tersebut pasti mempunyai setidaknya satu dari enam faktor berikut: $2, 3, 5, 7,$ $11,$ atau $13.$
Misalkan $| A |, | B |, | C |,$ $| D |, | E |,$ dan $| F |$ berturut-turut menyatakan banyak bilangan dari $2$ sampai $200$ yang habis dibagi $2, 3, 5, 7,$ $11,$ dan $13.$
Dengan demikian, banyak bilangan prima dari $2$ sampai $200$ adalah $6 + | (A \cup B \cup C \cup D \cup E \cup F)^{c} | .$ Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$\begin{aligned} | (A \cup B \cup C \cup D \cup E \cup F)^{c} | = & 199 - (| A | + | B | + | C | + | D | + | E | + | F | - | A \cap B | - | A \cap C | - | A \cap D | - | A \cap E | - \\ A \cap F | - | B \cap C | - | B \cap D | - | B \cap E | - | B \cap F | - | C \cap D | - | C \cap E | - | C \cap F | - \\ | D \cap E | - | D \cap F | - | E \cap F | + | A \cap B \cap C | + | A \cap B \cap D | + | A \cap B \cap E | + | A \cap B \cap F | + \\ | A \cap C \cap D | + | A \cap C \cap E | + | A \cap C \cap F | + | A \cap D \cap E | + | A \cap D \cap F | + | A \cap E \cap F | + \\ | B \cap C \cap D | + | B \cap C \cap E | + | B \cap C \cap F | + | B \cap D \cap E | + | B \cap D \cap F | + | B \cap E \cap F | + \\ | C \cap D \cap E | + | C \cap D \cap F | + | C \cap E \cap F | + | D \cap E \cap F | - | A \cap B \cap C \cap D | - | A \cap B \cap C \cap E | - \\ | A \cap B \cap C \cap F | - | A \cap B \cap D \cap E | - | A \cap B \cap D \cap F | - | A \cap B \cap E \cap F | - \\ | A \cap C \cap D \cap E | - | A \cap C \cap D \cap F | - | A \cap C \cap E \cap F | - | A \cap D \cap E \cap F | - \\ | B \cap C \cap D \cap E | - | B \cap C \cap D \cap F | - | B \cap C \cap E \cap F | - | B \cap D \cap E \cap F | - \\ | C \cap D \cap E \cap F | + | A \cap B \cap C \cap D \cap E | + | A \cap B \cap C \cap D \cap F | + | A \cap B \cap C \cap E \cap F | + \\ | A \cap B \cap D \cap E \cap F | + | A \cap C \cap D \cap E \cap F | + | B \cap C \cap D \cap E \cap F | \\ - | A \cap B \cap C \cap D \cap E \cap F |) . \end{aligned}$ Kita akan mencari nilai dari setiap suku di atas.
$\begin{aligned} | A | & = ⌊ \frac{200}{2} ⌋ = 100 \\ | B | & = ⌊ \frac{200}{3} ⌋ = 66 \\ | C | & = ⌊ \frac{200}{5} ⌋ = 40 \\ | D | & = ⌊ \frac{200}{7} ⌋ = 28 \\ | E | & = ⌊ \frac{200}{11} ⌋ = 18 \\ | F | & = ⌊ \frac{200}{13} ⌋ = 15 \\ | A \cap B | & = ⌊ \frac{200}{2 \times 3} ⌋ = 33 \\ | A \cap C | & = ⌊ \frac{200}{2 \times 5} ⌋ = 20 \\ | A \cap D | & = ⌊ \frac{200}{2 \times 7} ⌋ = 14 \\ | A \cap E | & = ⌊ \frac{200}{2 \times 11} ⌋ = 9 \\ | A \cap F | & = ⌊ \frac{200}{2 \times 13} ⌋ = 7 \\ | B \cap C | & = ⌊ \frac{200}{3 \times 5} ⌋ = 13 \\ | B \cap D | & = ⌊ \frac{200}{3 \times 7} ⌋ = 9 \\ | B \cap E | & = ⌊ \frac{200}{3 \times 11} ⌋ = 6 \\ | B \cap F | & = ⌊ \frac{200}{3 \times 13} ⌋ = 5 \\ | C \cap D | & = ⌊ \frac{200}{5 \times 7} ⌋ = 5 \\ | C \cap E | & = ⌊ \frac{200}{5 \times 11} ⌋ = 3 \\ | C \cap F | & = ⌊ \frac{200}{5 \times 13} ⌋ = 3 \\ | D \cap E | & = ⌊ \frac{200}{7 \times 11} ⌋ = 2 \\ | D \cap F | & = ⌊ \frac{200}{7 \times 13} ⌋ = 2 \\ | E \cap F | & = ⌊ \frac{200}{11 \times 13} ⌋ = 1 \\ | A \cap B \cap C | & = ⌊ \frac{200}{2 \times 3 \times 5} ⌋ = 6 \\ | A \cap B \cap D | & = ⌊ \frac{200}{2 \times 3 \times 7} ⌋ = 4 \\ | A \cap B \cap E | & = ⌊ \frac{200}{2 \times 3 \times 11} ⌋ = 3 \\ | A \cap B \cap F | & = ⌊ \frac{200}{2 \times 3 \times 13} ⌋ = 2 \\ | A \cap C \cap D | & = ⌊ \frac{200}{2 \times 5 \times 7} ⌋ = 2 \\ | A \cap C \cap E | & = ⌊ \frac{200}{2 \times 5 \times 11} ⌋ = 1 \\ | A \cap C \cap F | & = ⌊ \frac{200}{2 \times 5 \times 13} ⌋ = 1 \\ | A \cap D \cap E | & = ⌊ \frac{200}{2 \times 7 \times 11} ⌋ = 1 \\ | A \cap D \cap F | & = ⌊ \frac{200}{2 \times 7 \times 13} ⌋ = 1 \\ | A \cap E \cap F | & = ⌊ \frac{200}{2 \times 11 \times 13} ⌋ = 0 \\ | B \cap C \cap D | & = ⌊ \frac{200}{3 \times 5 \times 7} ⌋ = 1 \\ | B \cap C \cap E | & = ⌊ \frac{200}{3 \times 5 \times 11} ⌋ = 1 \\ | B \cap C \cap F | & = ⌊ \frac{200}{3 \times 5 \times 13} ⌋ = 1 \end{aligned}$ dan $0$ untuk nilai suku lainnya. Jadi,
$\begin{aligned} | (A \cup B \cup C \cup D \cup E \cup F)^{c} | = & 199 - (100 + 66 + 40 + 28 + 18 + 15 - 33 - 20 - 14 - \\ 9 - 7 - 13 - 9 - 6 - 5 - 5 - 3 - 3 - 2 - 2 - 1 + 6 + \\ 4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 0 + 1 + 1 + 1) \\ = 199 - 159 = 40. \end{aligned}$ Ini berarti terdapat $6 + 40 = 46$ bilangan prima yang nilainya tidak melebihi $200.$

[collapse]

Soal Nomor 16

Misalkan $m$ dan $n$ merupakan bilangan bulat positif. Berapa peluang kejadian mendapatkan suatu bilangan bulat positif yang kurang dari $m n$ dan bilangan tersebut tidak habis dibagi oleh $m$ atau $n ?$

Pembahasan

Misalkan $m$ dan $n$ merupakan bilangan bulat positif. Adapun langkah yang akan dilakukan untuk menyelesaikan soal ini adalah sebagai berikut.

Tentukan banyak bilangan yang kurang dari $m n$ dan habis dibagi oleh $m .$
Tentukan banyak bilangan yang kurang dari $m n$ dan habis dibagi oleh $n .$
Tentukan banyak bilangan yang kurang dari $m n$ dan habis dibagi oleh $m$ dan $n$ sekaligus.
Tentukan banyak bilangan yang kurang dari $m n$ dan habis dibagi oleh $m$ atau $n .$
Tentukan banyak bilangan yang kurang dari $m n,$ tetapi tidak habis dibagi oleh $m$ atau $n .$

Bilangan bulat $m, 2 m, 3 m, \dots, n m$ jelas dapat dibagi oleh $m .$ Ini berarti ada $(n - 1)$ bilangan yang kurang dari $m n$ sehingga habis dibagi oleh $m .$ Dengan cara yang serupa, juga ada $(m - 1)$ bilangan yang kurang dari $m n$ sehingga habis dibagi oleh $n .$ Berikutnya, perlu dicari banyak bilangan yang habis dibagi oleh $m$ dan $n$ sekaligus. Suatu bilangan habis dibagi oleh $m$ dan $n$ sekaligus jika dan hanya jika bilangan itu habis dibagi oleh kelipatan persekutuan terkecil dari $m$ dan $n,$ yaitu $KPK (m, n) .$ Misalkan $L = KPK (m, n) .$ Bilangan yang habis dibagi oleh $m$ dan $n$ adalah $L, 2 L, 3 L, \dots, m n .$ Bilangannya ada sebanyak $FPB (m, n)$ karena $KPK (m, n) \cdot FPB (m, n) = m n .$ Oleh karena itu, ada $FPB (m, n) - 1$ bilangan yang kurang dari $m n$ serta habis dibagi oleh $m$ dan $n .$
Dengan menggunakan prinsip inklusi-eksklusi, ada
$(m - 1) + (n - 1) + (FPB (m, n) - 1) = m + n - FPB (m, n) - 1$ bilangan yang kurang dari $m n$ dan habis dibagi oleh $m$ atau $n .$ Karena banyak bilangan yang kurang dari $m n$ adalah $(m n - 1),$ diperoleh
$\begin{aligned} (m n - 1) - (m + n - FPB (m, n) - 1) & = (m n - m - n + 1) + FPB (m, n) - 1 \\ = (m - 1) (n - 1) + FPB (m, n) - 1 \end{aligned}$ bilangan yang kurang dari $m n,$ tetapi tidak habis dibagi oleh $m$ atau $n .$
Jadi, peluang kejadian mendapatkan suatu bilangan bulat positif yang kurang dari $m n$ dan bilangan tersebut tidak habis dibagi oleh $m$ atau $n ?$ adalah $\frac{(m - 1) (n - 1) + FPB (m, n) - 1}{m n - 1}$

[collapse]

Soal Nomor 17

Suatu mesin memiliki fungsi untuk memasukkan surat ke dalam amplop. Diketahui masing-masing surat dipasangkan pada satu amplop tertentu. Karena malafungsi, mesin tersebut memasukkan surat ke dalam amplop secara sembarang. Pada kumpulan $100$ surat, berapa peluang kejadian sehingga

tidak ada surat yang dimasukkan ke dalam amplop yang sesuai.
ada tepat $1$ surat yang dimasukkan ke dalam amplop yang sesuai.
ada tepat $98$ surat yang dimasukkan ke dalam amplop yang sesuai.
ada tepat $99$ surat yang dimasukkan ke dalam amplop yang sesuai.
semua surat dimasukkan ke dalam amplop yang sesuai.

Pembahasan

Jawaban a)
Kejadian sehingga tidak ada surat yang dimasukkan ke dalam amplop yang sesuai merupakan kasus peracakan. Karena ada $100$ surat, banyak peracakannya adalah $D_{100},$ sedangkan banyak permutasi keseluruhan adalah $100! .$ Dengan demikian, peluang kejadian sehingga tidak ada surat yang dimasukkan ke dalam amplop yang sesuai adalah $\frac{D_{100}}{100!}$
Jawaban b)
Kita perlu menghitung banyak cara memasukkan tepat $1$ surat ke dalam amplop yang sesuai. Pertama, ada $C (100, 1) = 100$ cara untuk memilih $1$ surat yang akan dimasukkan ke dalam amplop yang sesuai. Selanjutnya, ada $D_{99}$ cara sehingga $99$ surat lain tidak dimasukkan ke dalam amplop yang sesuai. Berdasarkan aturan perkalian, ada $100 D_{99}$ cara secara keseluruhan. Jadi, peluang kejadian ada tepat $1$ surat yang dimasukkan ke dalam amplop yang sesuai adalah $\frac{100 D_{99}}{100!} = \frac{D_{99}}{99!}$
Jawaban c)
Untuk menghitung banyak cara memasukkan tepat $98$ surat ke dalam amplop yang sesuai, kita hanya perlu memilih $2$ surat agar salah dimasukkan. Jelas hanya ada $1$ cara hal itu dapat terjadi (misalnya, $A B$ menjadi $B A$ ). Untuk memilih $2$ surat tersebut, ada $C (100, 2) = 4.950$ cara. Jadi, peluang kejadian ada tepat $98$ surat yang dimasukkan ke dalam amplop yang sesuai adalah $\frac{4.950}{100!}$
Jawaban d)
Tidak mungkin ada tepat $99$ surat dimasukkan ke dalam amplop yang sesuai. Hal ini berlaku karena jika $99$ surat sudah dimasukkan ke dalam amplop yang sesuai, $1$ surat sisanya “terpaksa” harus dimasukkan ke dalam amplop yang sesuai pula. Jadi, peluang kejadian dengan kondisi seperti itu adalah $0$
Jawaban e)
Hanya ada $1$ dari $100!$ susunan sehingga semua surat dimasukkan ke dalam amplop yang sesuai. Jadi, peluangnya sebesar $\frac{1}{100!}$

[collapse]

Soal Nomor 18

Kumpulan $n$ siswa mengikuti dua pelajaran tertentu di dalam ruang kelas yang sama yang memuat $n$ kursi. Berapa banyak penempatan posisi duduk agar setiap siswa tidak menduduki kursi yang sama pada pelajaran pertama dan kedua?

Pembahasan

Misalkan himpunan siswa ${s_{1}, s_{2}, \dots, s_{n}}$ dikaitkan dengan himpunan kursi ${k_{1}, k_{2}, \dots, k_{n}}$ sehingga $(s_{1}, k_{1}),$ $(s_{2}, k_{2}),$ $\dots,$ $(s_{n}, k_{n})$ menyatakan siswa ke- $i$ menduduki kursi ke- $i$ untuk setiap $i \in {1, 2, \dots, n}$ pada pelajaran pertama. Ketika setiap siswa tidak menduduki kursi yang sama pada pelajaran kedua, kasus menjadi analog dengan mencari banyak peracakan pada $n$ objek, yaitu $D_{n} = n! [1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!}] .$ Namun, ${k_{1}, k_{2}, \dots, k_{n}}$ dapat dipermutasi sebanyak $n!$ cara. Ini berarti banyak peracakan secara keseluruhan adalah $n! \cdot D_{n} .$
Jadi, ada $n! \cdot D_{n}$ penempatan posisi duduk agar setiap siswa tidak menduduki kursi yang sama pada pelajaran pertama dan kedua.

[collapse]

Soal Nomor 19

Berapa banyak cara menyusun angka $0, 1, 2, 3,$ $4, 5, 6,$ $7, 8,$ dan $9$ sehingga tidak ada angka genap yang berada pada posisi semula?

Pembahasan

Teorema peracakan dapat digunakan dengan sedikit modifikasi, yaitu kita hanya meninjau angka genap agar tidak berpindah posisi. Jika tanpa syarat apa pun, banyak cara menyusun $10$ angka itu adalah $10! .$ Misalkan $a$ merupakan salah satu dari lima angka genap yang ada. Banyak permutasi sehingga $e$ berada pada posisi semula adalah $9!$ (karena $9$ angka lain dipermutasi). Oleh karena itu, $10!$ dikurangi oleh $5 \cdot 9!$ karena ada lima angka genap. Namun, kita melakukan pencacahan ganda karena ada $(\binom{5}{2}) 8!$ cara ketika dua angka genap tetap berada pada posisi semula, $(\binom{5}{3}) 7!$ cara ketika tiga angka genap tetap berada pada posisi semula, $(\binom{5}{4}) 6!$ cara ketika empat angka genap tetap berada pada posisi semula, dan $(\binom{5}{5}) 5!$ cara ketika semua angka genap tetap berada pada posisi semula. Dengan menggunakan prinsip inklusi-eksklusi, diperoleh
$10! - (5 \cdot 9! - (\binom{5}{2}) 8! + (\binom{5}{3}) 7! - (\binom{5}{4}) 6! + (\binom{5}{5}) 5!) = 2.170 .680 .$ Jadi, ada $2.170 .680$ cara menyusun angka $0, 1, 2, 3,$ $4, 5, 6,$ $7, 8,$ dan $9$ sehingga tidak ada angka genap yang berada pada posisi semula.

[collapse]

Tag: Pencacahan Ganda

Materi, Soal, dan Pembahasan – Prinsip Inklusi-Eksklusi

Ilustrasi Masalah

Teorema: Banyak Peracakan

Quote by Michel de Montaigne

Soal Nomor 1

Soal Nomor 2

Soal Nomor 3

Soal Nomor 4

Soal Nomor 5

Soal Nomor 6

Soal Nomor 7

Soal Nomor 8

Soal Nomor 9

Soal Nomor 10

Soal Nomor 11

Soal Nomor 12

Soal Nomor 13

Soal Nomor 14

Soal Nomor 1

Soal Nomor 2

Soal Nomor 3

Soal Nomor 4

Soal Nomor 5

Soal Nomor 6

Soal Nomor 7

Soal Nomor 8

Soal Nomor 9

Soal Nomor 10

Soal Nomor 11

Teorema: Banyak Fungsi Surjektif

Soal Nomor 12

Soal Nomor 13

Soal Nomor 14

Soal Nomor 15

Soal Nomor 16

Soal Nomor 17

Soal Nomor 18

Soal Nomor 19