SOAL DAN PEMBAHASAN BAB 4 Finish [PDF]

Citation preview

SOAL DAN PEMBAHASAN BAB 4 PRINSIP INKLUSI-EKSKLUSI



Mata kuliah: Matematika Diskrit Dosen pengampu: Leni Mrlena, S.Stat., M.Si.



Kelompok 4:



Adhi Widyanto Prima Nugraha



1501105005



Afifah Nafis



1501105005



Muhamad Chairudin



1501105077



PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH PROF. DR. HAMKA 2018



Soal dan Pembahasan 1. Berapa banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh 7 atau 11? Penyelesaian Misalkan: 



P himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7







Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11.



Dengan demikian P dan Q adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11, dan P ∩ Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan habis dibagi 11. 1000 = 142 7 1000 |𝑄| = = 90 11 1000 |𝑃 ∩ 𝑄| = = 12 77 |𝑃| =



|𝑃 ∪ 𝑄| = |𝑃| + |𝑄| − |𝑃 ∩ 𝑄| = 142 + 90 − 12 = 220 Jadi, terdapat 220 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11.



2. Sebanyak 1232 orang mahasiswa mengambil kuliah Bahasa Inggris, 879 orang mahasiswa mengambil kuliah Bahasa Perancis, dan 114 orang mahasiswa mengambil kuliah Bahasa Jerman. Sebanyak 103 orang mahasiswa mengambil kuliah Bahasa Inggris dan Perancis. 23 orang mahasiswa mengambil kuliah Bahasa Inggris dan Jerman, dan 14 orang mahasiswa mengambil kuliah Bahasa Perancis dan Bahasa Jerman. Jika 2092 orang mahasiswa mengambil paling sedikit satu buah kuliah Bahasa Inggris, Bahasa Perancis, dan Bahasa Jerman, berapa banyak mahasiswa yang mengambil kuliah ketiga buah bahasa tersebut? Penyelesaian Misalkan I = himpunan mahasiswa mengambil kuliah Bahasa Inggris 1



P = himpunan mahasiswa mengambil kuliah Bahasa Perancis J = himpunan mahasiswa mengambil kuliah Bahasa Jerman Maka 



|𝐼| = 1.232







|𝑃| = 879







|𝐽| = 114







|𝐼 ∩ 𝑃| = 103







|𝐼 ∩ 𝐽| = 23







|𝑃 ∩ 𝐽| = 14







|𝐼 ∪ 𝑃 ∪ 𝐽| = 2.092



Sehingga didapat: |𝐼 ∪ 𝑃 ∪ 𝐽| = |𝐼| + |𝑃| + |𝐽| − |𝐼 ∩ 𝑃| − |𝐼 ∩ 𝐽| − |𝑃 ∩ 𝐽| + |𝐼 ∩ 𝑃 ∩ 𝐽| |𝐼 ∩ 𝑃 ∩ 𝐽| = |𝐼 ∪ 𝑃 ∪ 𝐽| − |𝐼| − |𝑃| − |𝐽| + |𝐼 ∩ 𝑃| + |𝐼 ∩ 𝐽| + |𝑃 ∩ 𝐽| |𝐼 ∩ 𝑃 ∩ 𝐽| = 2.092 − 1.232 − 879 − 114 + 103 + 23 + 14 |𝐼 ∩ 𝑃 ∩ 𝐽| = 7 Jadi, terdapat 7 orang mahasiswa yang mengambil kuliah ketiga buah bahasa Inggris, Perancis dan Jerman.



3. Sebuah kata sandi dengan panjang 9 dibentuk dari angka-angka 0, 1 dan 2 sedemikian hingga tiap angka muncul tiga kali dan tiga angka berurutan dalam kata sandi tersebut tidak boleh sama. Ada berapa kata sandi yang dapat dibentuk? Penyelesaian: Misal S = himpunan kata sandi dengan 9-angka yang dapat dibentuk dari angka-angka “0”, “1”, dan “2” 𝑎1 = sifat muncul pola “000” 𝑎2 = sifat muncul pola “111” 𝑎3 = sifat muncul pola “222” 9!



N = isi = 3!3!3! = 



362.880 216



= 1.680



𝑁(𝑎1 ) = banyak anggota S yang mengandung pola “000” =



7! = 140 3! 3! 1! 2







𝑁(𝑎2 ) = banyak anggota S yang mengandung pola “111” =







𝑁(𝑎3 ) = banyak anggota S yang mengandung pola “222” =







5! = 20 3! 1! 1!



𝑁(𝑎2 𝑎3 ) = banyak anggota S yang mengandung pola “111” dan “222” =







5! = 20 3! 1! 1!



𝑁(𝑎1 𝑎3 ) = banyak anggota S yang mengandung pola “000” dan “222” =







7! = 140 3! 3! 1!



𝑁(𝑎1 𝑎2 ) = banyak anggota S yang mengandung pola “000” dan “111” =







7! = 140 3! 3! 1!



5! = 20 3! 1! 1!



𝑁(𝑎1 𝑎2 𝑎3 ) = banyak anggota S yang mengandung pola “000”, “111” dan “222” =



3! = 20 1! 1! 1!



Jadi dengan prinsip inklusi – eksklusi diperoleh banyak barisan 9 angka sedemikian sehingga tidak ada tiga angka yang berurutan sama adalah 𝑁(𝑎1′ , 𝑎2′ , 𝑎3′ ) = 1.680 − (140 + 140 + 140) + (20 + 20 + 20) − 6 = 1.314 4. Berapa banyak cara yang dapat 9 orang ke dalam 5 ruang berbeda jika terdapat tepat 2 yang kosong? Penyelesaian 𝑃𝑖 = ruang 𝑖 yang kosong. Kita ingin tepat dua ruang kosong jadi jumlah yang kita inginkan adalah 𝑒2 , dibutuhkan 𝑠2 , 𝑠3, 𝑠4, 𝑠5 𝑁(𝑃1 𝑃2 ) = ⋯ = 𝑁(𝑃4 𝑃5 ) = 39 𝑁(𝑃1 𝑃2 𝑃3 ) = ⋯ = 𝑁(𝑃3 𝑃4 𝑃5 ) = 29 𝑁(𝑃1 𝑃2 𝑃3 𝑃4 ) = ⋯ = 𝑁(𝑃2 𝑃3 𝑃4 𝑃5 ) = 19 = 1 𝑁(𝑃1 𝑃2 𝑃3 𝑃4 𝑃5 ) = 0



5 𝑗𝑎𝑑𝑖 𝑠2 = ( ) 39 2 5 𝑗𝑎𝑑𝑖 𝑠3 = ( ) 29 3 5 𝑗𝑎𝑑𝑖 𝑠4 = ( ) 4 𝑗𝑎𝑑𝑖 𝑠5 = 0



3



Sehingga, 4 3 5 𝑒2 = 𝑠2 − ( ) 𝑠3 + ( ) 𝑠4 − ( ) 𝑠5 2 2 2 4 5 3 5 5 5 5 = ( ) 39 − ( ) ( ) 29 + ( ) ( ) 1 − ( ) ( ) 0 2 3 2 4 2 2 5 = 10.19683 − 3.10.512 + 6.5 − 0 = 181500



5. Terdapat 8 pasang pemain ganda putra putri dalam suatu pertandingan bulu tangkis. Pertandingan tersebut serentak dan pemain putra harus berpasangan dengan pemain putri. Berapakah peluang terdapat tepat 4 pasang ganda putra putri dalam pertandingan bulu tangkis tersebut? Penyelesaian Diketahui: N = |S| = 6! r=8 m=4 7 6 8 5 𝑒4 = 𝑆4 − ( ) 𝑆5 + ( ) 𝑆6 − ( ) 𝑆7 + ( ) 𝑆8 3 2 4 1 7 8 8 6 8 5 8 = ( ) (8 − 4)! − ( ) ( ) (8 − 5)! + ( ) ( ) (8 − 6)! − ( ) ( ) (8 − 7)! + 3 7 4 2 6 1 5 8 8 ( ) ( ) (8 − 8)! 4 8 8! 5! 8! 6! 8! 7! 8! 8! 8! ( 4!)] − [ ( 3!)] + [ =[ . . 2!] − [ . 1!] + [ . 0!] 4! 4! 1! 4! 5! 3! 2! 4! 6! 2! 3! 4! 7! 1! 4! 4! 8! 0! 8! 8! 8! 8! 8! = − + − + 4! 1! 4! 2! 4! 3! 4! 4! 4! 8! 1 1 1 1 = [1 − + − + ] 4! 1! 2! 3! 4! 40.320 3 = [ ] 24 8 = 630



4



6. Cari jumlah banyaknya n-digit ternary urutan yang memiliki angka genap 0. Penyelesaian ai sifat bahwa i-th digits dari suatu urutan adalah 0. i = 1,2,3,…..,n. let ej dan sj didefinisikan sebagai dimana j = 0,1,2,….,n. 𝑛 Maka sj = ( 𝑗 ) 3𝑛−𝑗 dengan j= 0,1,2,….,n. Didapat 𝑛



1 𝑛 = [3𝑛 + ∑(−2)𝑗 ( 𝑗 ) 3𝑛−𝑗 ] 2



𝑒0 + 𝑒2 + 𝑒4 + ⋯



𝑗



1 𝑛 [3 + (3 − 2)𝑛 ] 2 1 = [3𝑛 + (1)𝑛 ] 2 1 = [3𝑛 + 1] 2 =



7. Terdapat banyak permutasi dai {1, 2, 3, 4, 5, 6}. Tentukanlah 𝑒0 + 𝑒2 + 𝑒4 + 𝑒6 Penyelesaian 𝑟



1 𝑒0 + 𝑒2 + 𝑒4 + 𝑒6 = [𝑆0 + ∑ (−2)𝑚 𝑆𝑚 ] 2 𝑚=0



6



1 6 = [( ) (6 − 0)! + ∑ (−2)𝑚 𝑆𝑚 ] 2 0 𝑚=6



6



1 6! ( 6!) + ∑ (−2)𝑚 𝑆𝑚 ] = [ 2 0! 6! 𝑚=6



1



= [720 + (−2)0 𝑆0 + (−2)1 𝑆1 + (−2)2 𝑆2 + (−2)3 𝑆3 + (−2)4 𝑆4 + 2



(−2)5 𝑆5 + (−2)6 𝑆6 ] 1



6!



6!



= 2 [720 + (1)(720) + [(−2) 1!5! ( 5!)] + [(4) 2!4! ( 4!)] + 6!



6!



6!



[(−8) 3!3! ( 3!)] + [(16) 4!2! ( 2!)] + [(−32) 5!1! ( 1!)] + 6!



[(64) 6!0! ( 0!)]]



5



1



= 2 [720 + 720 + (−1.440) + 1.440 + (−960) + 480 + (−192) + 64] =



1 (832) 2



= 416 8. Delapan kecelakaan terjadi dalam satu minggu. Dengan prinsip enklusi-eksklusi, hitung probabilitas bahwa terdapat paling sedikit satu kecelakaan setiap hari! Penyelesaian:



Misalkan, S ai  N  𝑁(𝑎𝑖 )



: {semua kemungkinan kecelakaan dapat terjadi} : sifat hari 1 terjadi kecelakaan dengan i ∊ {senin, selasa, rabu, kamis, jumat, sabtu, minggu} = |S| = 78 = 5764801 = Banyak angka S dengan tidak adak kecelakaan pada hari ke-i =(7 − 1)8 = 1679616



7  ∑𝑖 𝑁 (𝑎𝑖 ) = ( ) (7 − 1)8 = 7 ∙ 68 = 11757312 1  𝑁(𝑎𝑖 𝑎𝑗 ) = Banyak anggota dengan tidak ada kecelakaan pada hari i dan hari j = (7 − 2)8 = 390625 7  ∑𝑖 𝑁 (𝑎𝑖 𝑎𝑗 ) = ( ) (7 − 2)8 = 8203125 2  𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 ) = Banyak anggota dengan tidak ada kecelakaan pada hari i, j dan k = (7 − 3)8 = 65536 7  ∑𝑖 𝑁 (𝑎𝑖 𝑎𝑗 𝑎𝑘 ) = ( ) (7 − 3)8 = 22933760 3  𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 ) = Banyak anggota dengan tidak ada kecelakaan pada hari i, j, k dan l = (7 − 4)8 = 6561 7  ∑𝑖 𝑁 (𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 ) = ( ) (7 − 4)8 = 229635 4  𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 ) = Banyak anggota dengan tidak ada kecelakaan pada hari i, j, k, l dan m = (7 − 5)8 = 256 7  ∑𝑖 𝑁 (𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 ) = ( ) (7 − 5)8 = 5376 5 6



 𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 𝑎𝑛 ) = Banyak anggota dengan tidak ada kecelakaan pada hari i, j, k, l, m dan n = (7 − 6)8 = 1 7  ∑𝑖 𝑁 (𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 𝑎𝑛 ) = ( ) (7 − 6)8 = 7 6  𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 𝑎𝑛 𝑎𝑜 ) = Banyak anggota dengan tidak ada kecelakaan pada hari i, j, k, l, m, n dan o = (7 − 7)8 = 0 7  ∑𝑖,𝑗,𝑘,𝑙,𝑚,𝑛,𝑜 𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 𝑎𝑛 𝑎𝑜 ) = ( ) (7 − 7)8 = 0 7 Jadi, banyaknya kemungkinan kecelakaan ∋ terdapat paling sedikit satu kecelakaan setiap harinya, 𝑁(𝑎′𝑖 𝑎′𝑗 𝑎′𝑘 𝑎′𝑙 𝑎′𝑚 𝑎′𝑛 𝑎′𝑜 ) = 576801 − 1175312 + 8203125 − 2293760 + 229635 − 5376 + 7 − 0 = 141120 Dengan demikian: 𝑃(𝑎′ 𝑖 𝑎′𝑗 𝑎′ 𝑘 𝑎′ 𝑙 𝑎′ 𝑚 𝑎′ 𝑛 𝑎′ 𝑜 ) = 𝑁(𝑎′ 𝑖 𝑎′𝑗 𝑎′ 𝑘 𝑎′ 𝑙 𝑎′ 𝑚 𝑎′ 𝑛 𝑎′ 𝑜 ) =



141120 5764801 = 0,0245



9. Terdapat 10 pilot dan 5 pesawat terbang di bandara A udara. Kesepuluh pilot tersebut ditugasi oleh atasannya untuk menerbangkan kelima pesawat tersebut bersama-sama ke bandara udara B. ada berapa cara yang mungkin untuk mengelompokkan pilot-pilot tersebut ke dalam pesawat? Tidak ada pesawat yang kosong). Penyelesaian: Misalnya : S = {semua acara mengelompokkan 10 pilot ke dalam 5 buah pesawat terbang}. Ai = sifat pesawat ke-I tidak mempunyai pilot, i ∊ (1, 2, 3, 4, 5)  𝑁 = |𝑆| = 510 = 9765625  𝑁(𝑎𝑖 ) = Banyaknya cara mengelompokkan 10 pilot ke dalam 5 pesawat ∋ pesawat ke-i kosong. = (5 − 1)10 = 410 = 1.048.576 5 10  ∑10 = 5242880 𝑖 𝑁(𝑎𝑖 ) = ( ) (5 − 1) 1  𝑁(𝑎𝑖 𝑎𝑗 ) = Banyaknya cara mengelompokkan 10 pilot ke dalam 5 pesawat ∋ pesawat ke i dan j kosong. = (5 − 2)10 = 59049 7



5 10  ∑10 = 590490 𝑖 𝑁(𝑎𝑖 𝑎𝑗 ) = ( ) (5 − 2) 2  𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 ) = Banyaknya cara mengelompokkan 10 pilot ke dalam 5 pesawat ∋ pesawat ke i, j dan k kosong. = (5 − 3)10 = 1024 5 10  ∑10 = 10240 𝑖 𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 ) = ( ) (5 − 3) 3  𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 ) = Banyaknya cara mengelompokkan 10 pilot ke dalam 5 pesawat ∋ pesawat ke i, j, k dan l kosong. = (5 − 4)10 = 1 5 10  ∑10 =5 𝑖 𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 ) = ( ) (5 − 4) 4  𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 ) = Banyaknya cara mengelompokkan 10 pilot ke dalam 5 pesawat ∋ pesawat ke i, j, k, l dan m kosong. = (5 − 5)10 = 0 5 10  ∑10 =0 𝑖 𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑘 𝑎𝑙 𝑎𝑚 ) = ( ) (5 − 5) 5 Jadi, banyaknya cara mengelompokkan 10 pilot ke dalam 5 pesawat ∋ tidak ada pesawat yang kosong adalah: 𝑁(𝑎′𝑖 𝑎′𝑗 𝑎′𝑘 𝑎′𝑙 𝑎′𝑚 ) = 9765625 − 5242880 + 590490 − 10240 + 5 − 0 = 5.103.000 10. Terdapat 3 kantong plastic dan 5 bola. Dengan prinsip enklusi-eksklusi, hitung banyak cara yang mungkin untuk menempatkan bola ke dalam kantong plastic? Tidak ada plastic yang kosong) Penyelesaian: Misalnya : S = {semua acara menempatkan 5 bola ke dalam 3 kantong plastik}. ai = sifat pesawat ke-i tidak mempunyai pilot, i ∊ (1, 2,3)  𝑁 = |𝑆| = 35 = 243  𝑁(𝑎𝑖 ) = Banyaknya cara menempatkan 5 bola ke dalam 3 plastik ∋ plastik ke-i kosong = (3 − 1)5 = 32 3  ∑5𝑖 𝑁(𝑎𝑖 ) = ( ) (3 − 1)5 = 243 1 8



 𝑁(𝑎𝑖 𝑎𝑗 ) = Banyaknya cara menempatkan 5 bola ke dalam 3 plastik ∋ plastik ke-i dan j kosong = (3 − 2)5 = 1 3  ∑5𝑖 𝑁(𝑎𝑖 ) = ( ) (3 − 2)5 = 3 2  𝑁(𝑎𝑖 𝑎𝑗 , 𝑎𝑘 ) = Banyaknya cara menempatkan 5 bola ke dalam 3 plastik ∋ plastik ke-i, j dan k kosong = (3 − 3)5 = 0 3  ∑5𝑖 𝑁(𝑎𝑖 ) = ( ) (3 − 3)5 = 0 3 Jadi, banyaknya cara menempatkan 5 bola ke dalam 3 plastik ∋ tidak ada plastik yang kosong adalah: 𝑁(𝑎′𝑖 𝑎′𝑗 𝑎′𝑘 𝑎′𝑙 𝑎′𝑚 ) = 243 − 3 + 0 = 240



9