Lompat ke isi

Prinsip rumah burung

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Prinsip rumah burung menyatakan bahwa untuk dua bilangan asli dan , , jika burung ditaruh di dalam 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 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 . Jika tidak ada orang yang mengenal jumlah orang yang sama, maka setiap orang memiliki teman 0, 1, 2, ..., . Tetapi yang memiliki teman itu berteman dengan semuanya, sehingga tidak ada yang memiliki 0 teman.