Prinsip rumah burung

Prinsip rumah burung menyatakan bahwa untuk dua bilangan asli $m$ dan $n$, $n>m$, jika $n$ burung ditaruh di dalam $m$ rumah atau kotak, maka paling sedikit satu kotak berisi lebih dari satu burung. Secara lebih formal, dapat dikatakan bahwa tidak ada fungsi satu-satu pada himpunan terhingga yang memiliki kodomain lebih kecil daripada domain.

Prinsip ini pertama kali dinyatakan oleh Dirichlet pada 1834 dan diberi nama Schubfachprinzip (prinsip rak). Dalam beberapa bahasa, prinsip ini disebut prinsip Dirichlet.

Contoh

Contoh yang sederhana adalah di antara tiga belas orang, maka paling sedikit dua di antaranya lahir di bulan yang sama. Dalam hal ini dua belas bulan adalah sebagai rumah burung, dan tiga belas orang sebagai burung.

Sebuah contoh lagi yang lebih rumit adalah: Di Jakarta pasti terdapat paling sedikit dua orang yang memiliki jumlah teman yang sama. Misalkan jumlah penduduk Jakarta adalah $n$. Jika tidak ada orang yang mengenal jumlah orang yang sama, maka setiap orang memiliki teman 0, 1, 2, ..., $n-1$. Tetapi yang memiliki $n-1$ teman itu berteman dengan semuanya, sehingga tidak ada yang memiliki 0 teman.