PIGEON HOLE PRINCIPLE (PRINSIP SARANG BURUNG)

• materi 1

by Nikeasih Binatari
Pigeon hole principle...

     Perhatikan problem-problem berikut ini. 

    Diketahui ada sebanyak 13 mahasiswa dalam kelas. Buktikan bahwa setidaknya ada dua mahasiswa yang mempunyai bulan kelahiran yang sama.
     Ada sebanyak nn pasangan yang telah menikah. Dari 2n orang tersebut, minimal berapa orang harus dipilih agar menjamin bahwa terdapat satu pasang yang telah menikah.

     Sebanyak 36 mahasiswa matematika dinyatakan lulus pada semester genap tahun 2010. Jika ada 5 bidang yang tersedia di Jurusan Matematika, tunjukkan bahwa setidaknya ada 8 mahasiswa yang lulus dari bidang yang sama.

Ketika sejumlah objek dibagi menjadi sejumlah kelas dengan anggota lebih sedikit, setidaknya pasti ada satu kelas yang memuat suatu minimum jumlah objek. Misal diketahui ada sebanyak n+1 ekor burung merpati yang akan menempati n n buah sarang. Karena hanya ada tersedia n buah sarang, sementara banyaknya burung adalah n+1, maka setidaknya terdapat satu buah sangkar yang berisi 2 ekor burung merpati atau lebih.

Teorema : Pigeon Hole Principle (PHP)

Jika sebanyak nk+1 objek akan didistribusikan kedalam n buah kotak, maka setidaknya satu dari kotak-kotak tersebut akan memuat paling sedikit k+1 objek.