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.
