Prinsip Pigeon-Hole (Sarang Merpati) Dalam Matematika

Dalam kombinatorika sebagai salah satu bab ilmu matematika dikenal prinsip sarang/sangkar merpati. Atau secara luas ini dikenal dengan Prinsip Pigeonhole. Sebagai ilustrasi awal paling sederhana mengenai Prinsip Pigeonhole ini sebagai berikut,
Jika seseorang mempunyai 13 merpati dan mempunyai 12 sangkar merpati, maka niscaya akan ada satu minimal sangkar yang akan berisi 2 merpati. 

Selanjutnya, generalisasi dari ilustrasi di atas sanggup kita defenisikan,

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 sanggup perhatikan pola aplikasi prinsip pigeon hole di bawah ini,

Kasus 1. Diantara 367 orang, tunjukkan bahwa sedikitnya ada dua orang yang mempunyai 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 ketika pembentukan kiprah 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 sanggup 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 menurut 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 mempunyai nilai ujian yangsama, kalau nilai ujian ini berkisar dari 0 hingga 100?

Jawab: Karena nilai ujian berkisar dari 0 hingga 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 menciptakan isyarat matakuliah untuk matakuliah-matakuliah bidang studi  matematika dengan cara menambahkan tiga angka pada abjad KPM. Terdapat 51 matakuliah yang harus diberi isyarat dan tiga angka yang harus ditambahkan pada abjad KPM harus berkisar antara 101 hingga dengan 200. Tunjukkan bahwa terdapat paling sedikit dua matakuliah yang diberi isyarat dengan angka berurutan.

Solusi: Misalkan A ialah himpunan matakuliah yang akan diberi isyarat abjad KPM yang dilanjutkan dengan bilangan antara 101 hingga 200, |A|=51. Misalkan pula B ialah himpunan bilangan antara 101 hingga 200 yang memenuhi, setiap x,y∈B,|x−y|>1. 

Dalam hal ini B ialah himpunan bilangan antara 101 hingga 200 yang tidak berurutan sehingga maksimal |B|=49. Jika setiap elemen di A dipetakan ke B (ini akan sama dengan perjuangan untuk memberi isyarat mata kuliah sedemikian hingga diantara dua mata kuliah tidak ada isyarat yang berurutan) maka menurut Teorema 2 akan ada sedikitnya dua elemen katakanlah x1,x2∈A sedemikian hingga f(x1)=f(x2). 

Jika hasil ini dikaitkan kembali dengan perjuangan untuk memberi isyarat mata kuliah sedemikian hingga diantara dua mata kuliah tidak ada isyarat yang berurutan, maka akan ada mata kuliah yang diberi isyarat yang sama. Padahal dilarang ada dua mata kuliah dengan isyarat yang sama, maka salah satu mata kuliah dengan isyarat yang sama harus diberi isyarat bilangan antara x,y∈B,|x−y|=1. Akibatnya, akan ada sedikit dua matakuliah yang diberi isyarat 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 diharapkan dalam kelas matematika diskrit sedemikian hingga sedikitnya ada 6 mahasiswa yang mempunyai nilai grade yang sama kalau ada lima kemungkinan nilai gradematematika diskrit yaitu A,B,C,D, dan E?

Solusi:Jumlah minimum mahasiswa yang diharapkan dalam kelas matematika diskrit yang sedikitnya ada 6 mahasiswa yang mempunyai nilai grade yang sama ialah nilai terkecil n∈Z sedemikian hingga $\frac {n}{5}$=6. Nilai terkecil n∈Z tersebut yaitu n=5.5+1=26. Jika kita hanya mempunyai 25 mahasiswa maka sedikitnya hanya ada 5 mahasiswa yang mempunyai nilai grade yang sama. Oleh karenanya, 26 ialah jumlah minimum mahasiswa sedemikian hingga sedikitnya ada 6 mahasiswa yang mempunyai nilai grade yang sama.

Contoh Kasus 3:

Seorang kyai di sebuah desa yang selalu diminta untuk menawarkan 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 perkiraan bahwa kyai tersebut selalu menawarkan nama depan dan belakang!

Solusi:

Nama depan yang disiapkan kyai tersebut ialah Muhammad, Akhmad, dan Abdul sedangkan nama belakangnya ialah 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 menurut Prinsip Pigeonhole, akan ada sedikitnya dua orang anak yang mempunyai nama yang sama.

Sumber : http://emodul-matematika.fmipa.unej.ac.id

Sumber http://www.marthamatika.com/

Share this post