Pigeon Hole (sarang merpati)

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

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.

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.

Misalkan ada laci yang berisi selusin kaus kaki coklat dan selusin kaus kaki hitam yang didistribusikan secara acak. Pada saat listrik padam, berapa kaus kaki yang harus anda ambil untuk memastikan bahwa di antaranya terdapat sepasang kaus yang sewarna?


Terdapat dua tipe kaus kaki, jadi jika anda memilih paling sedikit 3 kaus kaki, haruslah terdapat paling sedikit dua kaus kaki coklat atau paling sedikit dua kaus kaki hitam .

Generalisasi Prinsip Sarang Merpati : 3/2 = 2.