Prinsip Eksistensi: Pigeonhole & Paritas

Dalam kombinatorika, kita sering kali tidak diminta untuk menghitung berapa banyak cara sesuatu terjadi, melainkan cukup membuktikan bahwa sesuatu pasti terjadi. Dua alat utama untuk ini adalah Prinsip Sarang Merpati (Pigeonhole Principle) dan Argumen Paritas.

1. The Pigeonhole Principle (Prinsip Sarang Merpati)

Prinsip ini secara intuitif menyatakan bahwa jika kita mencoba memasukkan terlalu banyak objek ke dalam wadah yang terlalu sedikit, maka setidaknya satu wadah akan berisi lebih dari satu objek.

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 dalam terminologi fungsi: Jika $f : A \to B$ adalah fungsi dari himpunan berhingga $A$ ke $B$ dengan $∣ A ∣ > ∣ B ∣$ , maka $f$ bukan fungsi injektif (terdapat $a_{1}, a_{2} \in A$ sehingga $f (a_{1}) = f (a_{2})$ ).

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.

2. Argumen Paritas dalam Kombinatorika

Paritas mengacu pada sifat keganjilan (oddness) atau kegenapan (evenness) dari suatu bilangan bulat. Dalam banyak masalah eksistensi, kita dapat menunjukkan bahwa suatu konfigurasi tidak mungkin dicapai dengan membuktikan bahwa paritas dari status awal dan status akhir tidak pernah bisa bersesuaian.

Aturan Dasar Paritas

Ganjil $\pm$ Ganjil $=$ Genap
Ganjil $\pm$ Genap $=$ Ganjil
Genap $\pm$ Genap $=$ Genap
(Ganjil) $\times$ (Ganjil) $=$ Ganjil
(Ganjil) $\times$ (Genap) $=$ Genap

Pewarnaan Papan Catur (Chessboard Coloring)

Banyak masalah paritas yang melibatkan papan catur atau kisi-kisi (grid) dapat diselesaikan dengan memberikan warna hitam dan putih secara berselang-seling sebagai bentuk visual argumen paritas.

Teorema (Pengubinan Papan Catur Terpotong)

Jika sebuah papan catur $8 \times 8$ dihilangkan dua kotak pojoknya yang berlawanan (misal kiri atas dan kanan bawah), maka papan tersebut tidak dapat ditutupi secara sempurna oleh 31 domino berukuran $2 \times 1$ .

Bukti

Setiap domino $2 \times 1$ akan selalu menutupi tepat satu kotak putih dan satu kotak hitam, terlepas dari bagaimana ia diletakkan. Papan catur standar memiliki 32 kotak putih dan 32 kotak hitam. Dua kotak pojok yang berlawanan memiliki warna yang sama (keduanya putih). Maka, papan yang dimodifikasi memiliki 30 kotak putih dan 32 kotak hitam. Karena 31 domino memerlukan 31 kotak putih dan 31 kotak hitam, maka pengubinan (tiling) tersebut tidak mungkin dilakukan. $■$

■

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.

Contoh (Invarian Papan Tulis)

Sebuah algoritma dimulai dengan menuliskan bilangan ${1, 2, 3, \dots, 10}$ di papan tulis. Setiap langkah, kita menghapus dua bilangan $a$ dan $b$ , lalu menuliskan $∣ a - b ∣$ sebagai gantinya. Proses ini berlanjut sampai hanya tersisa satu bilangan. Mungkinkah bilangan terakhir yang tersisa adalah 0?

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 di antara para tamu tersebut.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Banyaknya kenalan yang mungkin untuk setiap orang adalah dari ${0, 1, \dots, n - 1}$ .

Jika ada seseorang yang mengenal $0$ orang, maka tidak ada orang yang mengenal $n - 1$ orang. Jadi jumlah kenalan yang mungkin hanya ${0, 1, \dots, n - 2}$ (ada $n - 1$ nilai).
Jika tidak ada yang mengenal $0$ orang, maka jumlah kenalan yang mungkin adalah ${1, 2, \dots, n - 1}$ (ada $n - 1$ nilai). Dalam kedua kasus, ada $n$ orang (merpati) dan $n - 1$ kemungkinan nilai kenalan (sangkar). Berdasarkan Pigeonhole Principle, pasti ada 2 orang yang memiliki jumlah kenalan sama. $■$

✏️ Latihan Soal 2 (Jarak Titik dalam Persegi 2x2)

Diberikan 5 titik di dalam sebuah persegi berukuran $2 \times 2$ . Buktikan bahwa terdapat setidaknya dua titik yang jaraknya tidak lebih dari $2$ .

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Bagilah persegi $2 \times 2$ menjadi 4 buah sub-persegi berukuran $1 \times 1$ . Karena terdapat 5 titik dan 4 sub-persegi, berdasarkan Pigeonhole Principle, pasti terdapat sekurang-kurangnya 2 titik yang berada di dalam (atau pada batas) sub-persegi $1 \times 1$ yang sama. Jarak maksimum antara dua titik di dalam persegi $1 \times 1$ adalah panjang diagonalnya, yaitu $1^{2} + 1^{2} = 2$ . Maka terbukti jarak kedua titik tersebut $\leq 2$ . $■$

✏️ Latihan Soal 3 (Langkah Kuda Catur (Knight Tour))

Dapatkah sebuah kuda catur (knight) melompat dari kotak $a 1$ dan berakhir di kotak $h 8$ dalam tepat 63 langkah dengan mengunjungi setiap kotak di papan catur $8 \times 8$ tepat satu kali?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Setiap kali kuda melompat, ia selalu berpindah ke warna kotak yang berbeda.

Langkah 1: Pindah ke warna berbeda dari asal.
Langkah ke- $k$ : Jika $k$ ganjil, kuda berada di warna berbeda dari asal; jika $k$ genap, kuda berada di warna yang sama dengan asal. Kotak $a 1$ dan $h 8$ memiliki warna yang sama pada papan catur $8 \times 8$ . Maka untuk mencapai $h 8$ , diperlukan langkah genap. Karena 63 ganjil, perjalanan tersebut tidak mungkin dilakukan. $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Permutasi & Kombinasi
Sub-Topik Selanjutnya: Prinsip Inklusi-Eksklusi →

Prinsip Eksistensi: Pigeonhole & Paritas

1. The Pigeonhole Principle (Prinsip Sarang Merpati)

2. Argumen Paritas dalam Kombinatorika

Aturan Dasar Paritas

Pewarnaan Papan Catur (Chessboard Coloring)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

🏆 Soal ONMIPA Terkait (1 Soal)

Materi Terkait (Linked References) (2)

Prinsip Inklusi-Eksklusi, Derangement & Fungsi Onto

Naskah Soal & Pembahasan ONMIPA PT 2025 — Seleksi Wilayah

Diskusi & Tanya Jawab

Title