6 7 Prinsip Berhitung [PDF]

Citation preview

Prinsip Berhitung Matematika Informatika 3 Onggo Wiryawan @OnggoWr



Pigeonhole Principle* Teorema 1 • Jika sebanyak (n+1) objek dimasukkan ke dalam n buah kotak, maka setidaknya ada sebuah kotak yang berisi 2 objek atau lebih.



*Prinsip Sarang Merpati



Pigeonhole Principle Ilustrasi 1. Jika 4 bola dimasukkan ke dalam 3 kotak, maka pasti ada satu kotak yang berisi 2 bola atau lebih. 2. Dalam sebuah kelas berisi 28 mahasiswa, pasti ada setidaknya 3 mahasiswa yang bulan lahirnya sama.



Pigeonhole Principle* Teorema 2 • Jika sebanyak N objek dimasukkan ke dalam k buah kotak, maka setidaknya ada sebuah kotak yang berisi 𝑟 =



𝑁 𝑘



objek atau lebih.



Pigeonhole Principle Ilustrasi 100 12



1. Dalam 100 orang, akan ada = 9 orang yang lahir pada bulan yang sama.



Pigeonhole Principle Ilustrasi 1. Pada kelas berisi 30 mahasiswa, setidaknya ada berapa mahasiswa yang: a) Berhari lahir sama?



b) Berbulan lahir sama? c) Berjenis kelamin sama?



Pigeonhole Principle Hitung Terbalik • Berapa banyak objek minimum yang harus dipilih agar setidaknya sebanyak 𝑟 objek ini ada di dalam satu dari 𝑘 kotak, saat objekobjek ini disebar ke setiap kotak?



Pigeonhole Principle Hitung Terbalik • Untuk 𝑁 objek, akan ada setidaknya 𝑟 objek di salah satu kotak, untuk 𝑁 dimana 𝑘



bulat terkecil 𝑁 𝑁 = 𝑘 𝑟 − 1 + 1.



𝑁 𝑘



≥ 𝑟. Bilangan



≥ 𝑟 − 1 adalah



Pigeonhole Principle Ilustrasi 1. Harus ada berapa orang setidaknya yang harus ada dalam satu kelompok, agar dipastikan ada 3 orang yang lahir dalam bulan yang sama? Jawab: 𝑁 =𝑘 𝑟−1 +1 𝑁 = 12 3 − 1 + 1 = 25 Jadi harus ada 25 orang dalam kelompok itu.



Pigeonhole Principle Ilustrasi 1. Berapa setidaknya banyaknya mahasiswa yang harus hadir di suatu kelas agar terdapat setidaknya terdapat: a) 2 orang yang berhari lahir sama? b) 2 orang yang berbulan lahir sama? c) 3 orang yang berjenis kelamin sama?



Pigeonhole Principle Masalah 1. Dari sepaket kartu remi (52 kartu), berapa kartu yang harus diambil agar dipastikan ada: a) 2 kartu yang berlogo sama? b) 2 kartu yang berwarna sama? c) 3 kartu as? d) 2 kartu berwarna hitam? e) 2 kartu berwarna berbeda? f) 2 kartu berlogo berbeda? g) 2 kartu yang bukan as? h) 3 kartu yang berlogo berbeda?



Permutasi Definisi • Banyaknya cara untuk menyusun sebagian atau seluruh anggota dari suatu himpunan, dengan memperhatikan urutan/posisi. Formula •



𝑃𝑘𝑛



=



𝑛! 𝑛−𝑘 !



Permutasi & Kombinasi Latihan 1. Seseorang diminta mengerjakan 20 soal dari keseluruhan 25 soal. Jika Soal no.1 sampai dengan no.5 harus dikerjakan, maka tentukan banyak cara untuk mengerjakan soal-soal tersebut. 2. Sebuah keluarga yang terdiri atas ayah, ibu dan empat orang anak, makan malam di suatu tempat dengan posisi duduk melingkar. Tentukan banyaknya posisi yang mungkin jika Ayah dan Ibu selalu bedampingan.



Kombinasi Definisi • Banyaknya cara untuk menyusun sebagian atau seluruh anggota dari suatu himpunan, tanpa memperhatikan urutan/posisi. Formula •



𝐶𝑘𝑛



=



𝑛! 𝑛−𝑘 !𝑘!