PHP

PHP (Pigeon Hole Principal)

Pada kesempatan kali ini kita akan membahas tentang salah satu teorema mendasar pada Kombinatorika yaitu prinsip sangkar merpati atau biasa dikenal dengan istilah Pigeon Hole Principal. Prinsip ini biasanya sering dipakai pada soal-soal lomba karena sudah dikenal oleh banyak orang.

PHP. Jika ada $n+1$ ekor burung merpati yang di masukkan kedalam $n$ buah sangkar, maka ada minimal sebuah sangkar yang berisi 2 ekor burung

Bukti. Kita akan membuktikan teorema ini dengan pembuktian kontradiksi. Asumsikan pernyataan salah: semua kotak berisi maksimal seekor burung. Dengan menggunakan ketaksamaan biasa kita mendapat banyak burung maksimal adalah banyak kotak dikali dengan banyak burung maksimal pada tiap kotak yaitu $n$, namun $n+1 < n$ bernilai salah jadi dapat disimpulkan asumsi salah dan pernyataan awal benar