The Pigeonhole Principle (Prinsip Sarang Merpati)

Dalam kombinatorika, kita sering kali tidak diminta untuk menghitung berapa banyak cara sesuatu terjadi, melainkan cukup membuktikan bahwa sesuatu pasti terjadi. Prinsip Sarang Merpati (Pigeonhole Principle) adalah salah satu alat paling fundamental untuk hal ini.

1. Bentuk Lemah (Weak Form)

Teorema (Prinsip Sarang Merpati (Bentuk Lemah))

Jika $n + 1$ ekor burung merpati dimasukkan ke dalam $n$ buah sangkar, maka setidaknya ada satu sangkar yang berisi dua ekor merpati atau lebih.

Secara formal: Jika $f : A \to B$ dengan $∣ A ∣ > ∣ B ∣$ , maka $f$ bukan fungsi injektif (terdapat $a_{1}, a_{2} \in A$ sehingga $f (a_{1}) = f (a_{2})$ ).

2. Bentuk Kuat (Strong Form)

Teorema (Prinsip Sarang Merpati (Bentuk Kuat))

Jika $n$ buah objek dimasukkan ke dalam $k$ buah wadah, maka setidaknya ada satu wadah yang berisi sekurang-kurangnya:

$⌈ \frac{n}{k} ⌉ objek$

di mana $⌈ \cdot ⌉$ adalah fungsi ceiling.

Contoh Soal & Pembahasan

Contoh (Bulan Kelahiran)

Buktikan bahwa di antara 13 orang, setidaknya ada dua orang yang lahir di bulan yang sama.

Contoh (Pembagian Bilangan dalam 2n)

Diberikan himpunan $S = {1, 2, 3, \dots, 2 n}$ . Jika kita memilih $n + 1$ bilangan dari $S$ , buktikan bahwa selalu ada dua bilangan yang dipilih sedemikian sehingga salah satunya membagi bilangan yang lain.

Latihan Soal

✏️ Latihan Soal 1 (Jumlah Kenalan di Pesta)

Buktikan bahwa di dalam sebuah pesta yang dihadiri oleh $n$ orang ( $n \geq 2$ ), selalu terdapat setidaknya dua orang yang memiliki jumlah kenalan yang sama.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Terdapat $n$ orang (merpati) dan $n - 1$ kemungkinan jumlah kenalan (sangkar). Berdasarkan Pigeonhole Principle, pasti ada 2 orang yang memiliki jumlah kenalan yang sama. $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Teorema Binomial dan Identitas Pascal
Sub-Topik Selanjutnya: Argumen Paritas dan Pewarnaan Papan Catur →

The Pigeonhole Principle (Prinsip Sarang Merpati)

1. Bentuk Lemah (Weak Form)

2. Bentuk Kuat (Strong Form)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Argumen Paritas dan Pewarnaan Papan Catur

Teorema Binomial dan Identitas Pascal

Diskusi & Tanya Jawab

Title