Prinsip Pigeonhole (Sarang Merpati)

ü  Ilustrasi

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:

Jika n + 1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.

ü  Penerapan:

ü  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 terambi.

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.

ü  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.