pertemuan 9
DESCRIPTION
Pertemuan 9. Chapter 4 4.1. The Basics of Counting 4.2. The Pigeonhole Principle 4.3. Skip 4.4. Skip 4.5. Skip 4.6. Skip. The Basics of Counting sub-bab 4.1. Prinsip dasar: Dua macam cara menghitung ( counting ) Aturan Perkalian The Product Rule Aturan Penambahan The Sum Rule. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/1.jpg)
Pertemuan 9
![Page 2: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/2.jpg)
Chapter 44.1. The Basics of Counting
4.2. The Pigeonhole Principle
4.3. Skip
4.4. Skip
4.5. Skip
4.6. Skip
![Page 3: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/3.jpg)
The Basics of Counting
sub-bab 4.1
![Page 4: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/4.jpg)
Prinsip dasar:
Dua macam cara menghitung (counting)
1. Aturan Perkalian
The Product Rule
2. Aturan Penambahan
The Sum Rule
![Page 5: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/5.jpg)
Aturan PerkalianSebuah proses dibagi dalam beberapa subproses yang berlanjut (subproses-1, subproses-2, …, dan seterusnya).
Jika subproses-1 dapat diselesaikan dalam n1 cara,
subproses-2 dapat diselesaikan dalam n2 cara,
……………..
subproses-p dapat diselesaikan dalam np cara,
maka ada
(n1) (n2) …..… (np)
cara untuk menyelesaikan proses tersebut
![Page 6: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/6.jpg)
Rule of Product Percobaan 1 p kemungkinan Percobaan 2 q kemungkinan Maka jika percobaan 1 dan 2 dilakukan Maka terdapat p x q kemungkinan P x q jika perc. 1 dan 2 dilakukan scr
simultan
![Page 7: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/7.jpg)
Restauran menyediakan 5 makanan : nasi goreng, roti, soto, sate, sop dan 3 jenis minuman : susu, kopi, teh. Jika setiap orang boleh memesan 1 makan dan 1 minum, berapakah kemungkinan pasangan makanan dan minuman dpt di pesan ?
![Page 8: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/8.jpg)
Pasangan makanan yang dapat di pesan
Nasi goreng
Roti
Soto
Sate
Sop
Susu
kopi
teh
Susu
kopi
teh
Susu
kopi
teh
Susu
kopi
teh
Susu
kopi
teh
![Page 9: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/9.jpg)
Pasangan makanan yang dapat di pesan Nasi goreng
Susu Kopi The
roti Susu Kopi teh
soto Susu Kopi teh
sate Susu Kopi teh
sop Susu Kopi teh
![Page 10: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/10.jpg)
Pasangan makanan yang dapat di pesan : 15 pasang
Orang harus memilih makanan dan minuman,
Sehingga dengan mengg aturan perkalian, makanan dan minuman yang di pesan adalah 15 pasang
![Page 11: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/11.jpg)
Ex: kursi di aula akan di beri nomor :
Diawali huruf Diikuti dengan bil yang tidak lebih dari 50 ( < 50) Ex : A 14 , B 18
Berapa jumlah max kursi yang dapat dinomeri Jawab :
Kemungkinan huruf 26 Angka kurang dari 50
Huruf kiri 0 1 2 3 4 Huruf kanan 0 1 2 3 4 5 6 7 8 9
Jadi jumlah maksimum kursi yang dinomori 26 x 5 x 10 = 1300
A
B
0
1
2
3
4
0
1
....
9
0
1
....
9
Idem
![Page 12: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/12.jpg)
Contoh: lihat Example 1
Penomoran kursi di auditorium berbentuk satu huruf disambung dengan integer positif tidak lebih dari 100.
n1 = 26, n2 = 100,
maka ada 2600 nomor kursi:
A001 A002 … A100
B001 B002 … B100
C001 C002 … C100
… …
Z001 Z002 … Z100
![Page 13: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/13.jpg)
Contoh: lihat Example 7Format nomor telepon NXX-NXX-XXXX
di mana N = 2 .. 9, X = 0 .. 9
NXX : 8 x 10 x 10 XXXX : 10 x 10 x 10 x 10 200, 201, …, 299 0000 …
9999300, 301, …, 399
………900, 901, …, 999
Contoh nomor telepon dengan format ini : 209-302-0089
Maka dengan format ini ada (800)(800)(10.000) = 6.400.000.000 nomor telepon
![Page 14: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/14.jpg)
Aturan PenambahanSebuah proses dapat dilakukan dalam beberapa cara, tetapi cara-cara ini tidak dapat dilaksanakan pada waktu yang sama.
Jika ada n1 cara-1,
n2 cara-2,
……………..
np cara-p,
maka ada
n1 + n2 + …..… + np
kemungkinan cara untuk menyelesaikan proses tersebut
![Page 15: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/15.jpg)
Rule of Sum Percobaan 1 p kemungkinan Percobaan 2 q kemungkinan Maka jika percobaan 1 atau 2 dilakukan Maka terdapat p + q kemungkinan P + q jika perc. 1 dan 2 dilakukan scr
tidak simultan
![Page 16: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/16.jpg)
Contoh: lihat Example 10
Dalam sebuah panitia, wakil dari suatu jurusan bisa dipilih dari dosen atau dari mahasiswa.
Jurusan Matematika punya 37 dosen
dan 83 mahasiswa.
n1 = 37, n2 = 83
Maka ada 37 + 83 = 120 calon yang dapat mewakili jurusan Matematika.
![Page 17: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/17.jpg)
Kahima dpt di pegang oleh angkatan 1997 atau 1998. Jika ada 45 angkatan 1997 dan 52 angkatan 1998, berapa cara memilih jabatan kahima
Jawab : Kahima dari angk. 1997 atau 1998 Kahima hanya satu, jadi caranya adalah
menggunakan + 45 + 52 = 97 cara
![Page 18: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/18.jpg)
Kaidah X dan + dpt diperluas menjadi lebih dari 2 percobaan
Sehingga hasil percobaan yang mungkin terjadi adalah : Perkalian p1 x p2 x p3 . . . pn Penjumlahan p1 + p2 + p3 . . . pn
![Page 19: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/19.jpg)
Ex : Perpustakaan memp:
6 buku bhs inggris 8 buku bhs perancis 10 buku bhs jerman Masing-masing buku berbeda judul Bagaimana cara memilih :
3 buah buku, masing-masing dari bhs yang berbeda 1 buah buku sembarang bahasa
![Page 20: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/20.jpg)
Jawaban : Jumlah cara memilih 3 buah buku, masing-
masing dari tiap bahasa adalah : 6 x 8 x 10 = 480 cara
Jumlah cara memilih satu buah buku dari sembarang bahasa 6 + 8 + 10 = 24 cara
![Page 21: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/21.jpg)
Password panjangya 6-8 digit. Boleh angka ataupun huruf. Tidak membedakan huruf besar dan kecil. Berapa banyak password yg dpt dibuat ?
Jawab : Banyak huruf 26 Banyak angka 10, jadi total 36 karakter
![Page 22: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/22.jpg)
Jawab : Untuk password panjang 6 digit , jumlah
kemungkinan password : 36 * 36 * 36 * 36 * 36 * 36 = 36 6
=2.176.782.336 Untuk password panjang 7 digit , jumlah
kemungkinan password : 36 * 36 * 36 * 36 * 36 * 36 * 36 = 36 7
=78.364.164.096
![Page 23: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/23.jpg)
Untuk password panjang 8 digit , jumlah kemungkinan password :
36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 = 36 8 =2.821.109.907.456
Sehingga jumlah total password adalah 2.901.650.833.888
![Page 24: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/24.jpg)
Diagram pohon:
Untuk visualisasi guna mempermudah penyelesaian.
Contoh: lihat Example 17
Berapa bit-string dengan panjang 4 tidak berisi substring “11” ?
Daftar bit-string dengan panjang 4
0000 0100 1000 1100
0001 0101 1001 1101
0010 0110 1010 1110
0011 0111 1011 1111
![Page 25: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/25.jpg)
0
1
1
10
0 0 0
0
111
00 0 001 111 01
![Page 26: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/26.jpg)
Soal 48 halaman 312:
Dengan diagram pohon, hitung berapa bit-string dengan panjang 4 tidak berisi substring “000”
0000 0100 1000 1100
0001 0101 1001 1101
0010 0110 1010 1110
0011 0111 1011 1111
Gambarkan tree-nya.
![Page 27: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/27.jpg)
Prinsip Rumah Merpati
(The Pigeonhole Principle)
sub-bab 4.2
![Page 28: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/28.jpg)
Prinsip rumah merpati (the pigeonhole principle):
Jika (k+1) obyek ditempatkan dalam k kotak, maka paling sedikit satu kotak berisi dua atau lebih obyek
Obyek merpati (pigeons)
Kotak rumah merpati (pigeonholes)
![Page 29: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/29.jpg)
Contoh: examples 1 – 3 halaman 313
1. Dari antara 367 orang, ada sedikitnya dua orang yang lahir pada tanggal yang sama.
367 orang merpati
366 hari rumah merpati
2. Dari 27 kata ada dua kata yang dimulai dengan huruf yang sama.
27 kata merpati
26 huruf rumah merpati
![Page 30: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/30.jpg)
3. Jika nilai ujian menggunakan skala 0 s/d. 100, berapa orang mahasiswa yang megikuti ujian tersebut supaya paling sedikit ada dua orang yang nilainya sama ?
102 mahasiswa merpati
101 nilai (0..100) rumah merpati
![Page 31: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/31.jpg)
Example 1: among any group of 367 people, there must be at least two people with the same birthday, because there are only 366 possible birthday
Example 2: If you have 6 classes from Monday to Friday, there must be at least one day on which you have at least two classes.
![Page 32: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/32.jpg)
Bentuk umum prinsip rumah merpati
(the Generalized Pigeonhole Principle)
Jika N obyek ditempatkan dalam k kotak, maka paling sedikit satu kotak berisi paling sedikit N/k obyek
Contoh :
10 buah jeruk ditempatkan dalam 6 keranjang
N = 10, k = 6
Kalau penempatannya “merata” dan tidak ada keranjang yang kosong, maka distribusinya sbb.:
1 1 2 2 2 2
![Page 33: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/33.jpg)
Bentuk umum prinsip rumah merpati
(the Generalized Pigeonhole Principle)Jika N obyek ditempatkan dalam k kotak, maka paling sedikit satu kotak berisi paling sedikit N/k obyek
Bukti (dengan kontradiksi)
Asumsi: tidak ada kotak yang berisi lebih dari N/k -1
maka total obyek tidak lebih dari k ( N/k -1)
k ( N/k – 1) < k ( ( N/k + 1) – 1) karena N/k < N/k + 1
k ( N/k – 1) < k (N/k) atau total obyek < N
Padahal total obyek = N
Maka paling sedikit satu kotak berisi paling sedikit N/k obyek (terbukti)
![Page 34: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/34.jpg)
Contoh 5 & 6 halaman 315:
5. Di antara 100 orang ada paling sedikit 100 / 12 = 9 orang yang lahir pada bulan yang sama.
6. Nilai huruf adalah A, B, C, D, E dan dalam suatu kelas ada paling sedikit 6 orang yang mendapat nilai sama. Banyaknya mahasiswa di kelas itu minimum 26 orang.
A : 5 B : 5 C : 5 D : 5 E : 5 25 + 1
Jawab : N/5 = 6, è N/5 adalah pembulatan keatas, jadi N = 5.5 + 1 = 26
![Page 35: Pertemuan 9](https://reader035.vdokumen.com/reader035/viewer/2022062222/56814f9d550346895dbd5adb/html5/thumbnails/35.jpg)
Soal 13 halaman 318
Lima angka dipilih dari { 1, 2, 3, 4, 5, 6, 7, 8 }
Maka pasti ada sepasang angka yang jumlahnya 9
Rumah merpati (1+8)
(2+7)
(3+6)
(4+5)
Merpati 5 angka yang dipilih
Jadi 5/4 = 2 (sepasang angka) menghasilkan jumlah 9