PIGEON HOLE PRINCIPLE / PRINSIP SARANG MERPATI 1

Apa itu Prinsip Sarang Merpati?

Prinsip Sarang Merpati, atau dalam bahasa Inggris disebut Pigeon Hole Principle, menyatakan bahwa jika ada n sarang dan n+1 merpati, maka paling tidak ada 1 sarang yang ditempati lebih dari 1 merpati.

Walaupun kelihatan sederhana, prinsip ini terbukti sangat berguna dalam menyelesaikan masalah kombinatorial.

Contoh:

Dalam kemasan permen dengan 5 pilihan rasa, kita hanya perlu mengambil 6 permen untuk memastikan ada paling tidak dua permen dengan rasa sama.
Ini salah satu contoh paling sederhana dari penerapan prinsip sarang merpati. Misalkan kelima pilihan rasa adalah stroberi,jeruk,apel,anggur,dan kiwi. Setelah mengambil lima permen dari dalam kemasan, ternyata semua rasanya berbeda. Karena hanya ada lima pilihan rasa, permen keenam yang kita ambil pasti rasanya sama dengan salah satu permen yang sudah kita ambil sebelumnya. Disini rasa berperan sebagai sarang dan permen yang kita ambil sebagai merpatinya.

Di Jakarta, paling tidak ada 10 orang dengan jumlah helai rambut yang sama di kepalanya.
Rata-rata manusia memiliki 150.000 helai rambut di kepalanya. Dengan begitu sangat aman mengasumsikan rambut di kepala manusia paling banyak berjumlah satu juta helai. Sementara itu penduduk Jakarta berjumlah lebih dari 9 juta ( sekitar 9,5 juta lebih tepatnya). Dengan begitu, andaikan ada 9 orang penduduk Jakarta tanpa rambut, 9 orang berikutnya hanya punya 1 helai rambut, 9 orang berikutnya lagi hanya punya 2 helai, dan seterusnya sampai 9 orang penduduk Jakarta yang punya satu juta helai rambut di kepalanya, karena penduduk Jakarta berjumlah lebih dari 9 juta, orang ke 9.000.010 akan memiliki jumlah rambut antara 0 sampai sejuta. Dengan demikian memastikan ada paling tidak 10 orang dengan jumlah helai rambut yang sama di kepala.

Contoh yang sedikit lebih susah.

6 bilangan bulat berbeda antara 1 dan 2012 dipilih secara acak. Berapa peluang terpilihnya dua bilangan sedemikian hingga selisih keduanya kelipatan lima?
Jawaban dari soal diatas adalah 1, alias dapat dipastikan pasti ada dua bilangan yang terpilih sedemikian hingga selisih keduanya kelipatan lima. Perhatikan bahwa seluruh bilangan bulat bisa dikelompokkan menjadi lima, yaitu bilangan berbentuk 5k, 5k+1, 5k+2, 5k+3 dan 5k+4 dengan k sebarang bilangan bulat.
Dengan kata lain setiap bilangan bulat ketika dibagi 5 akan terbagi menjadi lima kelompok. Bilangan yang bersisa 0, bersisa 1, bersisa 2, bersisa 3 atau bersisa 4. Syarat selisih dua bilangan habis dibagi lima adalah kedua bilangan tersebut harus meninggalkan sisa yang sama ketika dibagi lima. Karena dipilih 6 bilangan secara acak, dengan prinsip sarang burung dapat dipastikan minimal ada dua bilangan yang meninggalkan sisa yang sama ketika dibagi dengan lima, sehingga bisa dipastikan juga bahwa peluang terpilihnya dua bilangan sedemikian hingga selisih keduanya kelipatan lima adalah satu.

Kelihatannya teorema ini memang sederhana. Akan tetapi, tidak jarang pula permasalahan yang harus diselesaikan adalah permasalahan yang cukup rumit. Kunci dari penggunaan teorema PHP ini adalah menemukan mana “sarang” dan “merpati”-nya. Tentu saja nantinya harus ditunjukkan bahwa jumlah merpati lebih banyak daripada sarangnya.

Berikut ini contoh lebih lanjut:

Dalam sekumpulan n orang di mana setiap orang minimal kenal dengan satu orang di kelompok tersebut, terdapat dua orang yang memiliki banyaknya kenalan di kelompok tersebut yang sama. (Contoh: ada dua orang yang sama-sama memiliki 20 kenalan dalam kelompok tersebut)

Dalam kasus ini jelas bahwa

Sarang = banyaknya kenalan

Merpati = banyaknya orang

Sekarang kita buktikan bahwa sarang lebih sedikit daripada merpatinya. Setiap orang minimal kenal dengan satu orang, maka banyaknya kenalan yang mungkin adalah 1 kenalan, 2 kenalan, 3 kenalan, dan seterusnya sampai n-1 kenalan. Sehingga ada n-1 kemungkinan banyaknya kenalan pada orang di dalam kelompok tersebut. Karena ada n orang, maka jelas bahwa pasti terdapat dua orang yang memiliki banyak kenalan yang sama.

Terdapat sembarang 5 bilangan yang hanya memiliki faktor prima 2 dan 5. Maka, setidaknya terdapat dua bilangan di antaranya yang hasil kalinya merupakan bilangan kuadrat

Perhatikan bahwa untuk suatu bilangan kuadrat n, pangkat dari setiap faktor primanya adalah genap. Sehingga, harus dibuktikan bahwa terdapat dua bilangan yang jumlah tiap pangkat pada faktor prima yang bersesuaian adalah genap.

Karena kelima bilangan tersebut hanya memiliki faktor prima 2 dan 5, bentuk faktorisasi prima dari setiap bilangan tersebut adalah 2a5b. Supaya jumlah pangkat dua bilangan pada faktor prima yang bersesuaian adalah genap, masing-masing harus memiliki paritas yang sama (sama-sama genap atau sama-sama ganjil). Sehingga, harus terdapat dua bilangan yang memiliki kombinasi paritas a dan b-nya sama. Maka, di sini:

Sarang = kombinasi paritas a dan b

Merpati = jumlah bilangan yang tersedia

Sekarang kita buktikan bahwa sarang lebih sedikit daripada merpatinya. Perhatikan bahwa hanya ada empat kombinasi paritas a dan b, yaitu : (a genap, b genap), (a genap, b ganjil), (a ganjil, b genap), dan (a ganjil, b ganjil). Karena terdapat 5 bilangan, dapat dipastikan ada dua bilangan yang memiliki kombinasi paritas a dan b sama. Sehingga, jika kedua bilangan tersebut dikalikan, akan menghasilkan bilangan yang pangkat dari setiap faktor primanya adalah genap, yang artinya bilangan hasil perkalian tersebut adalah bilangan kuadrat.