The Pigeonhole Principle (Prinsip Sarang Merpati)

Pigeonhole Principle atau Prinsip Rumah Merpati pertama kali dinyatakan oleh ahli matematika dari Jerman yang bernama Johann Peter Gustav Lejeune Dirichlet pada tahun 1834, sehingga prinsip ini juga dikenal dengan istilah Prinsip Laci Dirichlet (Dirichlet drawer principle).

Prinsip Pigeonhole Bentuk Pertama


Jika (k + 1) atau lebih obyek ditematkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau lebih obyek tersebut.


Missal Jika n merpati ditempatkan pada m rumah merpati, dimana n > m, maka terdapat rumah merpati yang memuat paling sedikit dua merpati. Untuk membuktikan pernyataan Prinsip Pigeonhole ini, kita gunakan kontradiksi. Misalkan kesimpulan dari pernyataan tersebut salah, sehingga setiap rumah merpati memuat paling banyak satu merpati. Karena ada m rumah merpati, maka paling banyak m merpati yang bisa dimuat. Padahal ada n merpati yang tersedia dan n > m, sehingga kita dapatkan sebuah kontradiksi.

Contoh 1: Jika terdapat 11 pemain dalam sebuah tim sepakbola yang menang dengan angka 12-0, maka haruslah terdapat paling sedikit satu pemain dalam tim yang membuat gol paling sedikit dua kali.

Contoh 2: Jika anda menghadiri 6 kuliah dalam selang waktu Senin sampai Jumat, maka haruslah terdapat paling sedikit satu hari ketika anda menghadiri paling sedikit dua kelas.

Prinsip Pigeonhole Bentuk Kedua


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  anggota X, dimana x1 ≠ x2.


Untuk membuktikan Prinsip Pigeonhole Bentuk Kedua ini kita bisa 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 anggota X yang dipasangkan ke rumah merpati yang sama, yaitu f(x1) = f(x2) untuk beberapa x1, x2  anggota X, dimana x1 ≠ x2.

contoh :
Dalam membuat kode matakuliah untuk matakuliah-matakuliah bidang studi informatika adalah dengan cara menambahkan tiga angka pada huruf TIK. Terdapat 51 matakuliah yang harus diberi kode dan tiga angka yang harus ditambahkan pada huruf TIK harus berkisar antara 101 sampai dengan 200. Tunjukkan bahwa terdapat paling sedikit dua matakuliah yang diberi kode dengan angka berurutan.


Misalkan angka-angka yang dipilih adalah
a1, a2, …, a51.
Jika angka-angka diatas digunakan bersama-sama dengan
a1 + 1, a2 + 1, …, a51 + 1

maka terdapat 102 nomor yang merentang antara 101 sampai dengan 201.

Karena ada 100 nomor yang disediakan (yaitu 101 sampai dengan 200) dan ada 102 nomor yang akan digunakan, maka menurut Prinsip Pigeonhole Bentuk Kedua terdapat paling sedikit dua nomor yang sama.

Nomor a1, a2, …, a51 dan a1 + 1, a2 + 1, …, a51 + 1 semuanya berbeda. Sehingga kita mempunyai ai = aj + 1 Dengan demikian kode ai berurutan dengan kode aj .

The Generalized Pigeonhole Principle Theorem (Generalisasi Prinsip Sarang Merpati)


Jumlah dari objek melebihi dari jumlah kotak yang tersedia.

Jika N obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat sedikitnya [N/k] obyek.
Bukti?

Contoh 1: Di dalam kelas dengan 60 mahasiswa, terdapat paling sedikit 12 mahasiswa akan mendapat nilai yang sama (A, B, C, D, atau E).

Contoh 2: Di dalam kelas dengan 61 mahasiswa, paling sedikit 13 mahasiswa akan memperoleh nilai yang sama.

Contoh lain :
Dalam matakuliah Matematika Diskrit diberikan tugas kelompok yang akan dibagi menjadi enam kelompok. Jika terdapat 62 mahasiswa yang menempuh mata kuliah tersebut, tunjukkan bahwa terdapat paling sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama!


Kita asumsikan mahasiswa tersebut sebagai anggota dari himpunan daerah asal X dan kelompoknya sebagai anggota daerah kawan Y . Karena |X| = 62, |Y | = 6 dan [62/6] = 11. Maka dengan menggunakan Prinsip Generalized Pigeonhole, terdapat paling sedikit 11 anggota X yang dipasangkan dengan suatu anggota Y yang sama. Dengan demikian terdapat paling sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama.