Hallo teman-teman… Apa kabar? Semoga hidup kalian hebat selalu. Kali ini saya akan menjelaskan tentang prinsip pigeonhole atau juga disebut prinsip sangkar merpati. Mungkin diantara kalian ada yang punya peliharaan merpati?? So, kalian udah mudah donk mempelajari sifat-sifat merpati. hehehe. Pigeonhole Principle atau Prinsip Sangkar 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).
Misalkan kita mempunyai kandang burung merpati (pigeon) yang memiliki pintu masuk berupa lubang-lubang (hole). Satu lubang berarti satu sarang. Setiap sarang biasanya ditempati oleh seekor burung merpati. Misalkan ada 16 ekor merpati dan hanya ada 14 buah sarang. Prinsip sarang merpati (pigeonhole principle) menyatakan bahwa paling sedikit terdapat satu sarang yang ditempati oleh dua ekor merpati.
Prinsip Pigeonhole
Bentuk Pertama:
Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Contoh 1
Dari 27 orang mahasiswa, paling sedikit terdapat dua orang yang namanya diawali dengan huruf yang sama, karena hanya ada 26 huruf dalam alfabet. Kita menganggap 27 huruf awal dari nama-nama mahasiswa sebagai merpati dan 26 huruf alfabet sebagai sarang merpati. Menurut prinsip pigeonhole, beberapa huruf awal alfabet dipasangkan dengan paling sedikit dua huruf awal nama mahasiswa.
Contoh 2
Misalkan terdapat banyak bola merah, bola putih, dan bola biru di dalam sebuah kotak. Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat ke dalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil.
Penyelesaian:
Jika setiap warna dianggap sebagai sarang merpati, maka n = 3. Karena itu, jika orang mengambil paling sedikit n + 1 = 4 bola (merpati), maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil. Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain. Jadi 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.
Contoh 3
Misalkan sebuah turnamen basket diikuti oleh n buah tim yang dalam hal ini setiap tim bertanding dengan setiap tim lainnya dan setiap tim menang paling sedikit satu kali. Tunjukkan bahwa paling sedikit ada 2 tim yang mempunyai jumlah kemenangan yang sama.
Penyelesaian:
Jumlah kemenangan setiap tim paling sedikit 1 kali dan paling banyak n-1 kali. Angka n-1 berkorespondensi dengan n-1 buah sarang merpati untuk menampung n ekor merpati (tim basket). Jadi, paling sedikit ada 2 tim basket yang mempunyai jumlah kemenangan sama.
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.
Prinsip Pigeonhole (Sarang Merpati) yang Dirampatkan
Jika M objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi minimal [ M / n ] objek.
Contoh 1
Jika terdapat 20 sarang merpati dan 41 ekor merpati, maka terdapat satu buah sarang yang berisi lebih dari 2 ekor merpati. Atau dengan menggunakan rumus diperoleh paling sedikit [ 41 / 20 ] = 3
merpati yang menempati 1 sarang merpati.
Contoh 2
Di antara 50 orang mahasiswa, terdapat paling sedikit [ 50 / 12 ] = 5 orang yang lahir pada bulan yang sama.
Gimana menarikkah? mudah-mudah tulisan ini membuat kalian semakin bersemangat dan menambah wawasan bermatematik. hehehe.
Salam M Khahfi Zuhanda
Mathematics Laboratory 