Prinsip Sarang Merpati

Pada postingan ini kita diskusikan suatu prinsip dasar dalam kombinatorika. Prinsip ini biasanya dipergunakan untuk memperlihatkan keberadaan dari suatu objek kombinatorika. Prinsip ini selain dikenal dengan nama prinsip sarang merpati (pigeonhole principle juga dikenal dengan nama Diriclech Principle.) Prinsip sarang merpati secara sederhana menyatakan bahwa bila terdapat $n + 1$ merpati yang terbang dan masuk dalam $n$ sarang, maka paling sedikit terdapat satu sarang yang berisi dua merpati atau lebih.

Prinsip Sarang Merpati: Bentuk Sederhana

Bentuk yang paling sederhana dari prinsip sarang burung merpati adalah sebagai berikut.

Teorema Sarang Merpati:
Jika $n + 1$ objek dimasukkan ke dalam $n$ kotak, maka paling sedikit terdapat satu kotak yang berisi dua objek atau lebih.

Bukti. Jika masing-masing kotak dari $n$ kotak memuat paling banyak satu objek, maka total banyaknya objek adalah paling banyak $n$ objek. Karena pada awalnya terdapat $n + 1$ objek, maka beberapa kotak memuat paling sedikit dua dari objek-objek tersebut.
Perhatikan bahwa baik pernyataan dari prinsip sarang merpati maupun buktinya tidak mengindikasikan kotak mana yang berisi dua objek atau lebih. Prinsip sarang merpati dan buktinya hanya men jamin bila seseorang memeriksa setiap kotak, maka beliau akan me nemukan paling sedikit satu kotak yang berisi dua objek atau lebih. Sehingga prinsip sarang merpati hanya menjamin keberadaan kotak dengan dua objek atau lebih, tanpa menspesifikasi lebih jauh kotak mana yang berisi dua objek atau lebih. Hal ini mengindikasikan bahwa biasanya prinsip sarang merpati digunakan untuk memperli hatkan keberadaan dari suatu skenario tertentu. Satu hal lagi perlu dicatat bahwa bila hanya terdapat $n$ objek, maka kesimpulan dari teorema sarang merpati mungkin saja tidak benar. Den gan pengertian, sangatlah memungkinkan bahwa setelah seseorang memeriksa semua kotak beliau tidak menemukan satu kotakpun yang memuat dua objek atau lebih. Sebagai contoh perhatikan skenario terburuk dimana setiap kotak memuat tepat satu objek. Karena hanya terdapat $n$ objek, maka tidak terdapat kotak dengan dua ob jek atau lebih. Jadi untuk menjamin keberadaan kotak dengan dua objek atau lebih diperlukan sedikitnya $n + 1$ objek. Dalam usaha mengaplikasikan prinsip sarang merpati kesulitan biasanya muncul ketika kita menentukan siapa yang bertindak seba gai objek dan siapa yang bertindak sebagai kotak.

Contoh-1:
Di antara sedkitinya 8 orang, pasti terdapat dua orang yang lahir pada hari yang sama. Pada contoh ini orang kita anggap sebagai objek dan banyak hari kita anggap sebagai kotak. Karena terdapat sedikitnya 8 orang dan hanya ada 7 hari, maka prinsip sarang merpati menjamin bahwa terdapat sedikitnya dua orang yang lahir pada hari yang sama.

Contoh-2:
Terdapat $n$ pasutri. Berapa orangkah harus dipilih dari $2n$ orang tersebut untuk menjamin terdapat dua orang yang merupakan pasutri?
Solusi. Untuk menjawab persoalan ini kita anggap terdapat $n$ kotak yang masing-masing berisi satu orang dari setiap pasutri. Bila kita memilih $n + 1$ orang dan masukkan setiap orang ke kotak dimana pasangannya berada, maka kita mendapatkan paling sedikit satu kotak yang berisi dua orang. Perhatikan bahwa pemilihan $n$ orang tidak menjamin bahwa selalu terdapat dua orang yang merupakan pasutri. Kasus seperti memilih $n$ orang laki-laki atau $n$ orang perempuan sama sekali tidak menjamin ditemukannya pasutri. Sehingga sedikitnya harus dipilih $n + 1$ orang agar terjamin bahwa di antara $n + 1$ orang terpilih terdapat pasutri.

Contoh-3:
Diberikan lima titik $P_1$, $P_2$, $P_3$, $P_4$, $P_5$ pada bidang dengan koordinat bilangan bulat. Buktikan bahwa sedikitnya terdapat sepasang titik $P_i$ dan $P_j$ dengan $i \ne j$, sehingga ruas garis $P_iP_j$ memuat sebuah titik $Q$(yang berbeda dengan $P_i$ dan $P_j$) dengan koordinat bilangan bulat.
Solusi. Perhatikan bahwa titik-titik dengan koordinat bilangan bulat dapat dikelompokkan dalam 4 partisi, yakni kelompok dengan koordinat (genap, genap), (genap, ganjil), (ganjil, ganjil), (ganjil, genap). Karena terdapat lima titik, maka oleh prinsip sarang merpati terdapat sedikitnya dua titik $P_i = (x_i,~y_i)$ dan $P_j = (x_j ,~y_j )$ yang berbeda sehingga koordinat mereka berada dalam partisi yang sama. Tanpa kehilangan keumuman pembuktian, misalkan keduanya berada dalam partisi (ganjil, genap). Perhatikan bahwa titik $\displaystyle P=\left(\frac{x_i+x_j}{2},~\frac{y_i+y_j}{2}\right)$ mempunyai koordinat bilangan bulat dan terletak pada garis $P_iP_j$.

Contoh-4:
Andaikan 51 bilangan dipilih dari 1, 2, 3, . . . , 99, 100. Perlihatkan bahwa terdapat dua bilangan terpilih sehingga keduanya tidak mempunyai pembagi sekutu prima.
Solusi. Kita partisi himpunan {1, 2, . . . , 99, 100} ke dalam 50 partisi {1, 2}, {2, 3}, . . . , {98, 99}, {99, 100}. Karena kita memilih 51 bilangan dan terdapat 50 partisi, maka prinsip sarang merpati menjamin bahwa di antara bilangan terpilih terdapat paling sedikit dua bilangan yang berada dalam partisi yang sama. Katakan partisi tersebut adalah {$k,~k + 1$} untuk suatu $k=$ 1, 2, . . . , 99. Bila terdapat bilangan prima $p$ yang membagi $k$ dan $k + 1$, maka $p$ membagi habis $(k + 1) − k = 1$. Sebuah kontradiksi. Jadi $k$ dan $k + 1$ tidak mempunyai faktor sekutu prima.

Contoh-5:
Perlihatkan bahwa di antara 5 bilangan bulat kita dapat memilih 3 di antaranya sehingga jumlahnya habis dibagi oleh 3.
Solusi:
Kita partisi semua himpunan bilangan bulat atas sisa bila dibagi oleh 3. Bila sebuah bilangan $x$ dibagi oleh 3, maka bilangan tersebut masuk dalam satu dari tiga kelompok, yakni $x \equiv$ 0 mod 3, $x \equiv$ 1 mod 3 atau $x \equiv$ 2 mod 3.
- Bila tiga bilangan terpilih $x_1$, $x_2$, $x_3$ berada dalam partisi yang sama, maka $x_1 + x_2 + x_3$ habis dibagi 3.
- Bila $x_1$, $x_2$ dan $x_3$ berada dalam tiga partisi yang berbeda maka $x_1 + x_2 + x_3$ habis dibagi 3.
- Andaikan $x_1$, $x_2$ dan $x_3$ berada dalam dua partisi yang berbeda. Karena terdapat 5 bilangan dan hanya ada 2 partisi, maka oleh prinsip sarang merpati terdapat 3 bilangan yang berada di partisi yang sama. Karena ketiga bilangan berada pada partisi yang sama, maka penjumlahan dari ketiga bilangan ini habis dibagi oleh 3.

Demikianlah postingan tentang prinsip sarang merpati. Sampai jumpa dan semoga bermanfaat.