Prinsip Sarang Merpati atau Pigeon Hole Principle (PHP) adalah salah satu teorema yang menarik dalam Matematika. Teorema ini berlandaskan pada sebuah logika sederhana, namun penerapannya sangat impactfull. Teorema ini pertama kali dinyatakan oleh Matematikawan berkebangsaan Jerman, Peter Gustav Lejeune Dirichlet (1805–1859) sehingga dikenal juga dengan Dirichlet’s drawer principle atau Dirichlet’s box principle.

Prinsip Pigeon Hole berawal dari permasalahan merpati dan sarangnya. Pada hakikatnya jika terdapat lebih banyak burung merpati daripada banyak sarangnya, maka pastilah ada paling sedikit satu sarang yang diisi oleh dua merpati. Bisa dilihat dari gambar di bawah ini, dari 9 sarang merpati terdapat 1 sarang yang berisi 2 ekor merpati karena adanya 10 merpati.

Teorema Pigeon Hole :

1. Jika k+1 atau lebih objek ditempatkan dalam k buah wadah dengan k ∈N, maka paling sedikit terdapat satu wadah yang berisi dua atau lebih objek.

2. Jika n objek diletakkan dalam m buah kotak dan n>m, maka paling sedikit ada satu kotak berisi dua atau lebih objek

 

Dalam menyelesaikan masalah Pigeon Hole, kita harus memiliki intuisi untuk mengasumsikan secara tepat mana yang objek (merpati) dan mana yang kotak (sarang) sehingga kita bisa menyelesaikan dengan tepat. Namun perlu diketahui, prinsip Pigeon Hole tidak memberitahu sarang mana yang terisi 2 merpati. Penerapan prinsip ini juga hanya memberitahu objek yang ada, bukan bagaimana mencari objek tersebut ataupun berapa banyak objek tersebut.

 

Contoh Soal 1

Berapa jumlah siswa minimal dalam satu kelas agar didapat 2 siswa dengan zodiak yang sama?

Jawaban

Seperti yang kita kenal ada 12 zodiak. Artinya ada 12 kotak (n=12)

Sehingga agar terdapat minimal 2 siswa dengan zodiac yang sama, maka jumlah siswa harus n+ 1 yaitu (12 + 1) = 13 siswa

 

Contoh Soal 2

Sebanyak 1.000 orang mengikuti survei dan mereka diminta untuk mengisi rumpang berupa hari lahir mereka (Senin, Selasa, Rabu, Kamis, Jumat, Sabtu, dan Minggu). Paling sedikit ada berapa orang yang memiliki hari lahir yang sama?

Jawaban

Dari masalah ini dapat kita asumsikan “hari” sebagai kotak (sarang) dan “orang” sebagai objek (merpati).

Dengan kata lain n = 1000 dan m = 7, dimana n /m = 1000 / 7 = 142 bersisa 6. Artinya disini sudah ada 142 orang yang memiliki hari lahir yang sama. Dan sisanya 6 orang ini bisa diasumsikan beda hari lahir, akibatnya akan ada paling sedikit 142 + 1 = 143 orang yang memiliki hari lahir yang sama.  

 

Masih banyak lagi pastinya masalah dalam kehidupan sehari-hari yang bisa diselesaikan dengan teorema ini. Sehingga teorema ini banyak digunakan dalam

• Aplikasi pada Sains Komputer

• Aplikasi pada permasalahan relasi

• Aplikasi pada permasalahan numerical

• Aplikasi pada permasalahan geometri

• Aplikasi pada trik kartu kombinatorik

Menarik bukan? Selamat belajar dan bereksplorasi dengan Pigeon Hole Principle. ~Suci Utari