Jika seseorang memiliki 13 merpati dan memiliki 12 kandang merpati, maka pasti akan ada satu minimal kandang yang akan berisi 2 merpati.
Teorema 1 [Prinsip Pigeonhole]
Jika n merpati ditempatkan pada m rumah merpati, dimana n>m, maka terdapat rumah merpati yang memuat paling sedikit dua merpati.Pembuktian dari teorema 1 ini sebagai berikut, pembuktian secara kontradiktif.
Misal kesimpulan dari pernyataan di atas tidak benar,bisa diasumsikan bahwa 1 rumah merpati memuat paling banyak satu merpati.
Prinsip rumah merpati disebut juga dengan Dirichlet drawer principle. Anda bisa perhatikan contoh aplikasi prinsip pigeon hole di bawah ini,
Kasus 1. Diantara 367 orang, tunjukkan bahwa sedikitnya ada dua orang yang memiliki hari ulang tahun yang sama.
Jawab: Karena dalam setahun hanya ada 366 kemungkinan hari ulang tahun, maka akan ada sedikitnya dua orang yang punya hari ulang tahun yangsama.
Kasus 2
Pada saat pembentukan tugas kelompok yang dibagi menjadi enam kelompok, tujuh mahasiswa tidak masuk kuliah sehingga mereka belum terdaftar dalam kelompok yang sudah dibagi. Tunjukkan bahwa palingsedikit ada dua mahasiswa yang bergabung dalam satu kelompok!
Jawab: Untuk menjawab pertanyaan ini kita bisa mengunakan Teorema 1. Asumsikan bahwa tujuh mahasiswa yang tidak masuk kuliah sebagai banyaknya merpati dan banyaknya kelompok pada tugas
kuliah tersebut sebagai rumah merpati. Sehingga berdasarkan Teorema 1 akan ada satu kelompok yang memuat paling sedikit dua mahasiswa yang tidak masuk kuliah.
Kasus 3
Berapa banyak pelajar yang harus berada dalam kelas untuk menjamin bahwa sedikitnya ada dua pelajar yang memiliki nilai ujian yangsama, jika nilai ujian ini berkisar dari 0 sampai 100?
Jawab: Karena nilai ujian berkisar dari 0 sampai 100 maka ada 101 kemungkinan nilai pada ujian. Berdasarkan prinsip rumah merpati, maka diantara 102 pelajar seharusnya ada paling sedikit 2 pelajar dengan nilai ujian yang sama.
Teorema 2 Pigeon-Hole
Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y dan |X|>|Y|,maka f(x1)=f(x2) untuk beberapa x1,x2∈X, dimana x1≠x2.
Bukti: Menggunakan Prinsip Pigeonhole Bentuk Pertama dengan mengasumsikan X sebagai himpunan merpati dan Y sebagai himpunan rumah merpati. Selanjutkan kita memasangkan merpati x ke rumah merpati f(x). Karena jumlah merpati lebih banyak dari rumahnya, maka terdapat paling sedikit dua merpati, x1,x2∈X yang dipasangkan ke rumah merpati yang sama, yaitu f(x1)=f(x2) untuk beberapa x1,x2∈X, dimana x1≠x2.
Contoh Kasus : Ketua Program Studi Matematika akan membuat kode matakuliah untuk matakuliah-matakuliah bidang studi matematika dengan cara menambahkan tiga angka pada huruf KPM. Terdapat 51 matakuliah yang harus diberi kode dan tiga angka yang harus ditambahkan pada huruf KPM harus berkisar antara 101 sampai dengan 200. Tunjukkan bahwa terdapat paling sedikit dua matakuliah yang diberi kode dengan angka berurutan.
Solusi: Misalkan A adalah himpunan matakuliah yang akan diberi kode huruf KPM yang dilanjutkan dengan bilangan antara 101 sampai 200, |A|=51. Misalkan pula B adalah himpunan bilangan antara 101 sampai 200 yang memenuhi, setiap x,y∈B,|x−y|>1.
Dalam hal ini B adalah himpunan bilangan antara 101 sampai 200 yang tidak berurutan sehingga maksimal |B|=49. Jika setiap elemen di A dipetakan ke B (ini akan sama dengan usaha untuk memberi kode mata kuliah sedemikian hingga diantara dua mata kuliah tidak ada kode yang berurutan) maka berdasarkan Teorema 2 akan ada sedikitnya dua elemen katakanlah x1,x2∈A sedemikian hingga f(x1)=f(x2).
Jika hasil ini dikaitkan kembali dengan usaha untuk memberi kode mata kuliah sedemikian hingga diantara dua mata kuliah tidak ada kode yang berurutan, maka akan ada mata kuliah yang diberi kode yang sama. Padahal tidak boleh ada dua mata kuliah dengan kode yang sama, maka salah satu mata kuliah dengan kode yang sama harus diberi kode bilangan antara x,y∈B,|x−y|=1. Akibatnya, akan ada sedikit dua matakuliah yang diberi kode dengan bilanganberurutan.
Teorema 3 [Generalisasi Prinsip Pigeonhole]
Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y, dimana |X|=n, |Y|=m dan $ \frac {n}{m}=k$, maka terdapat paling sedikit k anggota x1,x2,...,xk∈X sedemikian hingga
f(x1)=f(x2)=...=f(xk)
Contoh Kasus 1:
Diantara 100 orang sedikitnya ada $\frac {100}{12}$=9 orang yang lahir pada bulan yang sama.
Contoh Kasus 2:
Berapakah jumlah minimum mahasiswa yang dibutuhkan dalam kelas matematika diskrit sedemikian hingga sedikitnya ada 6 mahasiswa yang memiliki nilai grade yang sama jika ada lima kemungkinan nilai gradematematika diskrit yaitu A,B,C,D, dan E?
Solusi:Jumlah minimum mahasiswa yang dibutuhkan dalam kelas matematika diskrit yang sedikitnya ada 6 mahasiswa yang memiliki nilai grade yang sama adalah nilai terkecil n∈Z sedemikian hingga $\frac {n}{5}$=6. Nilai terkecil n∈Z tersebut yaitu n=5.5+1=26. Jika kita hanya memiliki 25 mahasiswa maka sedikitnya hanya ada 5 mahasiswa yang memiliki nilai grade yang sama. Oleh karenanya, 26 adalah jumlah minimum mahasiswa sedemikian hingga sedikitnya ada 6 mahasiswa yang memiliki nilai grade yang sama.
Contoh Kasus 3:
Seorang kyai di sebuah desa yang selalu diminta untuk memberikan nama bayi yang lahir, menyiapkan nama depan Muhammad, Ahmad, Abdul dan nama belakang Hadi, Akbar, Gofur bagi bayi yang lahir dalam suatu bulan tertentu. Pada bulan tersebut terdapat sebelas bayi yang lahir di desa itu. Tunjukkan bahwa paling sedikit ada dua bayi yang mempunyai nama yang sama dengan asumsi bahwa kyai tersebut selalu memberikan nama depan dan belakang!
Solusi:
Nama depan yang disiapkan kyai tersebut adalah Muhammad, Akhmad, dan Abdul sedangkan nama belakangnya adalah Hadi, Akbar, dan Gofur. Berdasarkan prinsip perkalian, kombinasi nama bayi yang dipersiapkan ada 9 nama yaitu Muhammad Hadi, Muhammad Akbar, Muhammad Gofur, Akhmad Hadi, Akhmad Akbar, Akhmad Gofur, Abdul Hadi, Abdul Akbar, dan Abdul Gofur. Jika kita misalkan banyaknya bayi yang lahir bulan itu sebagai banyaknya merpati dan banyaknya kombinasi nama bayi yang disediakan sebagai banyaknya rumah merpati, maka berdasarkan Prinsip Pigeonhole, akan ada sedikitnya dua orang anak yang memiliki nama yang sama.
Sumber : http://emodul-matematika.fmipa.unej.ac.id
Jadilah Komentator Pertama untuk "Prinsip Pigeon-Hole (sarang merpati) dalam Matematika"
Post a Comment