Prinsip Sarang Merpati
Prinsip sarang merpati merupakan salah satu konsep yang sangat intuitif dalam matematika. Prinsip ini menyatakan bahwa jika ada lebih banyak merpati daripada jumlah sarang, maka setidaknya ada satu sarang yang ditempati oleh lebih dari satu merpati. Prinsip sederhana ini banyak digunakan dalam matematika untuk membuktikan berbagai pernyataan dalam kombinatorika dan teori bilangan.
Selain itu, prinsip ini sering muncul dalam soal-soal kompetisi matematika, baik di tingkat sekolah seperti KSN dan KSM, maupun di tingkat perguruan tinggi seperti ONMIPA-PT Matematika.
Meskipun prinsip ini tampak sangat intuitif, dalam beberapa soal, penerapannya sering kali tidak bisa langsung dilakukan. Terkadang kita perlu mengontruksi objek-objek yang dapat dipandang sebagai "sarang" dan "merpati". Ini menjadi tantangan tersendiri saat menyelesaikan soal-soal terkait.
Daftar Isi
Mengenal Prinsip Sarang Merpati
Sebagaimana dijelaskan pada awal pembahasan, prinsip sarang merpati merupakan prinsip yang sangat intuitif, yang menyatakan bahwa jika ada lebih banyak merpati dibanding sarang yang tersedia, maka setidaknya ada satu sarang yang ditempati oleh lebih dari satu merpati.
Tentu saja, prinsip ini tidak hanya berlaku pada merpati dan sarang, namun secara umum berlaku untuk objek-objek lainnya. Selain dikenal sebagai Prinsip Sarang Merpati, beberapa literatur menyebutnya sebagai Prinsip Sangkar Burung, dan keduanya merujuk pada konsep yang sama.
Prinsip Sarang Merpati
Jika $k$ merupakan bilangan bulat positif dan $k+1$ atau lebih objek ditempatkan ke dalam $k$ kotak, maka setidaknya ada satu kotak yang memuat dua atau lebih objek.
Prinsip di atas bisa dibuktikan dengan metode kontradiksi. Andaikan tidak ada kotak yang memuat dua atau lebih objek. Dengan kata lain, setiap kotak memuat paling banyak satu objek. Karena ada sebanyak $k$ kotak, maka total objek yang ada maksimum sebanyak $k$. Hal ini merupakan kontradiksi, karena diketahui bahwa terdapat setidaknya $k+1$ objek.
Prinsip sarang merpati dapat diterapkan pada berbagai kasus sederhana. Misalnya, di antara tiga orang bersaudara, pasti ada dua orang yang memiliki jenis kelamin yang sama. Contoh lain, dalam sebuah kelas yang terdiri dari $32$ siswa, pasti ada dua orang yang lahir di tanggal yang sama. Lebih lanjut, di antara $32$ siswa tersebut, ada pula setidaknya dua orang yang namanya diawali dengan huruf yang sama.
Dalam kasus-kasus yang disajikan sebelumnya, objek-objek yang dipandang sebagai merpati dan sarang terlihat dengan jelas. Namun, dalam berbagai situasi lainnya, hal ini tidak selalu langsung tampak. Misalnya, dalam sebuah pesta yang dihadiri oleh dua orang atau lebih, pasti ada dua orang yang memiliki jumlah kenalan yang sama di pesta tersebut.
Contoh lain, untuk setiap bilangan bulat positif $n$, ada kelipatan $n$ yang hanya memuat digit $0$ dan $1$ dalam representasi desimalnya. Kedua masalah ini menggunakan prinsip sarang merpati, tetapi kita perlu mengonstruksi objek yang berperan sebagai merpati dan sarang terlebih dahulu. Inilah tantangan yang sering kita hadapi saat menerapkan prinsip ini.
Prinsip Sarang Merpati yang Diperumum
Prinsip sarang merpati menyatakan bahwa jika terdapat lebih banyak objek daripada kotak yang tersedia, maka setidaknya ada dua objek yang menempati kotak yang sama. Lebih lanjut, kita bisa memperoleh informasi tambahan ketika jumlah objek yang ada jauh melebihi jumlah kotak.
Misalnya, di antara $7$ orang di sebuah ruangan, pasti ada setidaknya $4$ orang yang berjenis kelamin sama. Hal ini terjadi karena ketika $7$ objek didistribusikan ke dalam $2$ kotak, salah satu kotak pasti memuat lebih dari $3$ objek.
Prinsip Sarang Merpati yang Diperumum
Jika $N$ objek ditempatkan ke dalam $k$ kotak, maka setidaknya ada satu kotak yang memuat setidaknya $\lceil N/k \rceil$ objek.
Salah satu masalah sering melibatkan penerapan prinsip sarang merpati yang diperumum adalah menentukan jumlah minimum objek yang diperlukan agar setidaknya $r$ objek berada dalam kotak yang sama. Misalkan banyak objeknya adalah $N$ dan banyak kotaknya adalah $k$.
Prinsip sarang merpati yang diperumum menjamin bahwa akan ada setidaknya $r$ objek yang menempati kotak yang sama, dengan syarat $\lceil N/k \rceil \geq r$. Hal ini berakibat $N/k > r-1$, sehingga bilangan bulat terkecil yang memenuhi adalah $N = k(r-1) + 1$.
Untuk menyelesaikan masalah-masalah semacam ini, sering kali lebih mudah dengan mempertimbangkan kemungkinan terburuk saat mendistribusikan objek. Tersedia sebanyak $k$ kotak dan kita ingin setidaknya $r$ objek berada dalam kotak yang sama. Kemungkinan terburuknya adalah kita mendistribusikan objek sedemikian sehingga syarat setidaknya $r$ objek dalam satu kotak tidak terpenuhi.
Dalam hal ini, setiap kotak akan berisi tepat $r-1$ objek. Ketika kita mendistribusikan satu objek lagi, di kotak manapun objek itu ditempatkan, pasti akan ada $r$ objek dalam kotak tersebut. Dengan demikian, jumlah minimum objek agar kondisi yang diinginkan terpenuhi adalah sebanyak $N = k(r-1) + 1$ objek.
Sebagai contoh, misalkan kita mengambil sejumlah kartu dari sebuah dek bridge. Kita ingin memastikan bahwa ada setidaknya $6$ kartu dari jenis yang sama (sekop, hati, wajik, atau keriting). Kemungkinan terburuknya adalah terambil tepat $5$ kartu dari setiap jenis, yang berarti sudah ada $4 \times 5 = 20$ kartu yang terambil.
Apa pun jenis kartu ke-$21$ yang kita ambil, pasti akan ada $6$ kartu dari jenis yang sama. Dengan demikian, untuk memastikan kondisi ini terpenuhi, banyak kartu yang harus diambil minimal sebanyak $21$ kartu.
Soal dan Pembahasan
Buktikan bahwa di antara enam kelas, yang masing-masing mengadakan pertemuan sekali seminggu pada hari tertentu, pasti ada dua kelas yang bertemu pada hari yang sama, dengan asumsi tidak ada kelas yang diadakan pada akhir pekan.
Berdasarkan asumsi, tidak ada kelas yang diadakan pada akhir pekan, sehingga pertemuan hanya bisa diadakan pada hari senin, selasa, rabu, kamis, atau jum'at. Pandang $5$ hari tersebut sebagai sarang dan $6$ kelas yang akan mengadakan pertemuan sebagai merpati. Berdasarkan Prinsip Sarang Merpati, pasti ada dua kelas yang bertemu pada hari yang sama.
Buktikan bahwa jika suatu kelas terdiri dari $30$ siswa, maka setidaknya ada dua orang yang namanya dimulai dengan huruf yang sama.
Alfabet latin yang kita gunakan, terdiri dari $26$ huruf (A sampai Z). Pandang $26$ huruf ini sebagai sarang dan $30$ nama siswa dalam kelas tersebut sebagai merpati. Berdasarkan Prinsip Sarang Merpati, terdapat setidaknya dua orang yang namanya dimulai dengan huruf yang sama.
Sebuah laci berisi selusin kaus kaki cokelat dan selusin kaus kaki hitam, yang semuanya tidak berpasangan. Seorang pria mengambil kaus kaki secara acak dalam gelap.
- Berapa banyak kaus kaki yang harus ia ambil untuk memastikan bahwa ia memiliki setidaknya dua kaus kaki dengan warna yang sama?
- Berapa banyak kaus kaki yang harus ia ambil untuk memastikan bahwa ia memiliki setidaknya dua kaus kaki hitam?
Bagian a. Karena terdapat dua warna kaus kaki (cokelat dan hitam), kemungkinan terburuknya adalah terambil satu kaus kaki untuk masing-masing warna. Jika pria tersebut mengambil satu kaus kaki lagi, maka apapun warna dari kaus kaki ketiga, baik itu cokelat ataupun hitam, pasti ia akan memiliki dua kaus kaki dengan warna yang sama. Jadi, pria tersebut harus mengambil sebanyak $2+1$ kaus kaki untuk memastikan bahwa terdapat setidaknya dua kaus kaki dengan warna yang sama.
Bagian b. Kemungkinan terburuknya adalah terambil $12$ kaus kaki warna putih, sehingga dua pengambilan berikutnya pasti berwarna hitam. Jadi, pria tersebut harus mengambil sebanyak $12+2=14$ kaus kaki untuk memastikan bahwa terdapat setidaknya dua kaus kaki berwarna hitam.
Sebuah kotak berisi $10$ bola merah dan $10$ bola biru. Seorang wanita mengambil bola secara acak tanpa melihatnya.
- Berapa banyak bola yang harus ia ambil untuk memastikan bahwa ia memiliki setidaknya tiga bola dengan warna yang sama?
- Berapa banyak bola yang harus ia ambil untuk memastikan bahwa ia memiliki setidaknya tiga bola biru?
Bagian a. Karena terdapat dua warna bola, kemungkinan terburuknya adalah terambil dua bola untuk masing-masing warna. Jika wanita tersebut mengambil satu bola lagi, maka apapun warna bola tersebut, baik itu merah ataupun biru, pasti ia akan memiliki tiga bola dengan warna yang sama. Jadi, wanita tersebut harus mengambil sebanyak $4+1=5$ bola untuk memastikan bahwa terdapat setidaknya tiga bola dengan warna yang sama.
Bagian b. Kemungkinan terburuknya adalah terambil sebanyak $10$ bola merah, sehingga tiga pengambilan berikutnya pasti berwarna biru. Jadi, pria tersebut harus mengambil sebanyak $10+3=13$ bola untuk memastikan bahwa terdapat setidaknya tiga bola biru.
Buktikan bahwa di antara sembarang lima bilangan bulat (tidak mesti berurutan), ada dua bilangan yang memiliki sisaan yang sama ketika dibagi $4$.
Berdasarkan Algoritma Pembagian, sisaan yang mungkin diperoleh ketika membagi bilangan bulat dengan $4$ adalah $0$, $1$, $2$, atau $3$. Pandang $4$ kemungkinan sisaan tersebut sebagai sarang dan sembarang $5$ bilangan bulat sebagai merpati. Berdasarkan Prinsip Sarang Merpati, pasti ada dua bilangan bulat yang memiliki sisaan yang sama ketika dibagi $4$. Terbukti.
Misalkan $d$ adalah bilangan bulat positif. Buktikan bahwa di antara sembarang $d+1$ bilangan bulat (tidak mesti berurutan), terdapat dua bilangan dengan sisaan yang sama ketika dibagi dengan $d$.
Berdasarkan Algoritma Pembagian, sisaan yang mungkin diperoleh ketika membagi bilangan bulat dengan $d$ adalah anggota dari himpunan $\{ 0,1,\ldots,d-1 \}$. Himpunan ini beranggotakan sebanyak $d$ elemen. Pandang $d$ sisaan yang mungkin ini sebagai sarang dan sembarang $d+1$ bilangan bulat sebagai merpati. Berdasarkan Prinsip Sarang Merpati, terdapat dua bilangan bulat dengan sisaan yang sama ketika dibagi dengan $d$. Terbukti.
Misalkan $n$ adalah bilangan bulat positif. Buktikan bahwa di antara sembarang $n$ bilangan bulat berurutan, ada tepat satu bilangan yang habis dibagi $n$.
Misalkan $k$ adalah bilangan bulat dan $n$ adalah bilangan bulat positif, sehingga $k,k+1,\ldots,k+n-1$ merupakan $n$ bilangan bulat berurutan. Ada sebanyak $n$ sisaan yang mungkin ketika suatu bilangan dibagi $n$, yaitu anggota himpunan $S=\{0,1,\ldots,n-1\}$.
Ada dua kemungkinan. Pertama, setiap anggota $S$ muncul sebagai sisaan dari $n$ bilangan berurutan yang ada. Akibatnya, di antara $n$ bilangan bulat berurutan tersebut, ada tepat satu bilangan dengan sisaan $0$. Dengan kata lain, bilangan ini habis dibagi $n$.
Kemungkinan kedua, ada anggota $S$ yang tidak muncul sebagai sisaan. Hal ini berakibat jumlah sisaan yang tersedia kurang dari $n$. Karena terdapat $n$ bilangan bulat, maka berdasarkan Prinsip Sarang Merpati, ada dua bilangan bulat yang mempunyai sisaan yang sama.
Misalkan bilangan tersebut adalah $x+i$ dan $x+j$ dengan sisaan $k$, sehingga terdapat bilangan bulat $a$ dan $b$ yang memenuhi $x+i=an+k$ dan $x+j=bn+k$. Dengan mengurangkan kedua persamaan, diperoleh $i-j=(a-b)n$. Artinya $n | i-j$, yang berakibat $\textcolor{blue}{n \leq i-j}$.
Perhatikan bahwa $0\leq i < n$ dan $0 \leq j < n$, sehingga diperoleh $\textcolor{red}{i-j < n}$. Terjadi kontradiksi dengan $\textcolor{blue}{n \leq i-j}$. Artinya, kemungkinan kedua ini mustahil terjadi. Dengan demikian, haruslah kemungkinan pertama, yang berarti di antara sembarang $n$ bilangan bulat berurutan, ada tepat satu bilangan yang habis dibagi $n$.
Misalkan $S$ dan $T$ adalah himpunan berhingga, dengan $|S|>|T|$. Buktikan bahwa jika $f$ adalah fungsi dari $S$ ke $T$, maka terdapat elemen $s_1$ dan $s_2$ di himpunan $S$ sedemikian sehingga $f(s_1)=f(s_2)$, dengan kata lain, $f$ bukan fungsi satu-satu.
Misalkan $S$ dan $T$ adalah himpunan berhingga, dengan $|S|>|T|$, serta $f$ adalah fungsi dari $S$ ke $T$. Berdasarkan definisi fungsi, setiap anggota $S$ harus dipetakan ke suatu elemen di $T$. Pandang elemen-elemen $S$ sebagai merpati dan elemen-elemen $T$ sebagai sarang. Karena $|S|>|T|$, berdasarkan Prinsip Sarang Merpati, terdapat dua elemen $S$ yang dipetakan ke elemen yang sama di $T$. Dengan kata lain, terdapat $s_1$ dan $s_2$ di himpunan $S$ sedemikian sehingga $f(s_1)=f(s_2)$. Hal ini juga berarti, $f$ bukan fungsi satu-satu. Terbukti.
Saat ini, terdapat sebanyak $38$ provinsi di Indonesia. Berapa jumlah minimum mahasiswa yang terdaftar di sebuah kampus, untuk menjamin bahwa terdapat setidaknya $100$ mahasiswa yang berasal dari provinsi yang sama?
Kemungkinan terburuknya, terdapat $99$ mahasiswa yang berasal dari setiap provinsi. Jika ada satu orang mahasiswa lagi, maka pasti akan satu provinsi yang merupakan asal dari $100$ mahasiswa. Dengan demikian, jumlah minimum mahasiswa yang terdaftar di sebuah kampus, untuk menjamin bahwa terdapat setidaknya $100$ mahasiswa yang berasal dari provinsi yang sama adalah $38\times 99+1=3763$.
Misalkan $(x_i,y_i)$ dengan $i=1,2,3,4,5$, merupakan lima titik berbeda dengan koordinat bilangan bulat dalam bidang $xy$. Buktikan bahwa terdapat dua titik yang mempunyai titik tengah dengan koordinat bilangan bulat.
Misalkan $(x_i,y_i)$ dengan $i=1,2,3,4,5$, merupakan lima titik berbeda dengan koordinat bilangan bulat dalam bidang $xy$. Definisikan bahwa titik $(a,b)$ mempunyai komposisi $mn$, jika $a$ memenuhi sifat $m$ dan $b$ memenuhi sifat $n$. Dengan meninjau sifat ganjil (odd, disimbolkan $o$) dan genap (even, disimbolkan $e$) dari komponen titik $(a,b)$, diperoleh empat komposisi yang mungkin, yaitu $oo$, $oe$, $eo$, dan $ee$.
Pandang empat komposisi tersebut sebagai sarang dan lima titik berbeda dengan koordinat bulat sebagai merpati. Berdasarkan Prinsip Sarang Merpati, terdapat dua titik dengan komposisi yang sama. Misalkan $(x_j,y_j)$ dan $(x_k,y_k)$ adalah titik yang dimaksud. Titik tengah dari keduanya adalah $$\left( \frac{x_j+x_k}{2},\frac{y_j+y_k}{2} \right)$$
Karena $(x_j,y_j)$ dan $(x_k,y_k)$ mempunyai komposisi yang sama, diperoleh $x_j$ dan $x_k$ keduanya genap, atau keduanya ganjil. Hal ini berakibat $x_j+x_k$ genap. Dengan argumen serupa, diperoleh $y_j+y_k$ genap. Misalkan $x_j+x_k=2p$ dan $y_j+y_k=2q$, untuk suatu bilangan bulat $p$ dan $q$. Akibatnya $$\left( \frac{x_j+x_k}{2},\frac{y_j+y_k}{2} \right)=\left( \frac{2p}{2},\frac{2q}{2} \right) = (p,q)$$
Dengan demikian, kedua titik tersebut mempunyai titik tengah dengan koordinat bilangan bulat. Terbukti.
Misalkan $(x_i,y_i,z_i)$ dengan $i=1,2,\ldots,9$, merupakan sembilan titik berbeda dengan koordinat bilangan bulat dalam ruang $xyz$. Buktikan bahwa terdapat dua titik yang mempunyai titik tengah dengan koordinat bilangan bulat.
Misalkan $(x_i,y_i,z_i)$ dengan $i=1,2,3,4,5,6,7,8,9$, merupakan sembilan titik berbeda dengan koordinat bilangan bulat dalam ruang $xyz$. Definisikan bahwa titik $(a,b,c)$ mempunyai komposisi $lmn$, jika $a$ memenuhi sifat $l$, $b$ memenuhi sifat $m$, dan $c$ memenuhi sifat $n$. Dengan meninjau sifat ganjil (odd, disimbolkan $o$) dan genap (even, disimbolkan $e$) dari komponen titik $(a,b,c)$, diperoleh delapan komposisi yang mungkin, yaitu $ooo$, $ooe$, $oeo$, $oee$, $eoo$, $eoe$, $eeo$, dan $eee$.
Pandang delapan komposisi tersebut sebagai sarang dan lima titik berbeda dengan koordinat bulat sebagai merpati. Berdasarkan Prinsip Sarang Merpati, terdapat dua titik dengan komposisi yang sama. Misalkan $(x_j,y_j,z_j)$ dan $(x_k,y_k,z_k)$ adalah titik yang dimaksud. Titik tengah dari keduanya adalah $$\left( \frac{x_j+x_k}{2},\frac{y_j+y_k}{2},\frac{z_j+z_k}{2} \right)$$
Karena $(x_j,y_j,z_j)$ dan $(x_k,y_k,z_k)$ mempunyai komposisi yang sama, diperoleh $x_j$ dan $x_k$ keduanya genap, atau keduanya ganjil. Hal ini berakibat $x_j+x_k$ genap. Dengan argumen serupa, diperoleh $y_j+y_k$ genap dan $z_j+z_k$ genap. Misalkan $x_j+x_k=2p$, $y_j+y_k=2q$, $z_j+z_k=2r$, untuk suatu bilangan bulat $p$, $q$, dan $r$. Akibatnya $$\left( \frac{x_j+x_k}{2},\frac{y_j+y_k}{2},\frac{z_j+z_k}{2} \right)=\left( \frac{2p}{2},\frac{2q}{2},\frac{2r}{2} \right) = (p,q,r)$$
Dengan demikian, kedua titik tersebut mempunyai titik tengah dengan koordinat bilangan bulat. Terbukti.
Berapa banyak pasangan bilangan bulat terurut $(a,b)$ yang dibutuhkan untuk memastikan bahwa terdapat dua pasangan terurut $(a,b)$ sedemikian sehingga $a_1 \bmod 5=a_2 \bmod 5$ dan $b_1 \bmod 5=b_2\bmod 5$?
Setiap bilangan bulat kongruen modulo $5$ dengan tepat satu anggota dari himpunan $\{0,1,2,3,4\}$. Karena itu, himpunan bilangan bulat dapat dipartisi menjadi $5$ himpunan, yaitu $N_k$ yang berisikan bilangan-bilangan bulat yang bersisa $k$ jika dibagi $5$, dengan $k=0,1,2,3,4$.
Karena terdapat dua komponen pada $(a,b)$, maka akan ada sebanyak $5\times 5=25$ kombinasi yang mungkin. Berdasarkan Prinsip Sarang Merpati, jika terdapat $26$ pasangan terurut maka akan ada dua pasangan terurut, sebutlah $(a_1,b_1)$ dan $(a_2,b_2)$, sedemikian sehingga $a_1$ dan $a_2$ berasal dari himpunan yang sama, begitupun dengan $b_1$ dan $b_2$.
Misal $a_1$ dan $a_2$ merupakan anggota $N_i$, dengan $0\leq i<5$, sehingga diperoleh $a_1 \equiv i \bmod 5$ dan $a_2 \equiv i \bmod 5$. Akibatnya, $a_1 \bmod 5=a_2 \bmod 5$. Dengan argumen serupa, dapat ditunjukkan bahwa $b_1 \bmod 5=b_2 \bmod 5$.
Dengan demikian, banyaknya pasangan bilangan bulat terurut yang dibutuhkan adalah minimal $26$ pasangan.
Buktikan bahwa jika lima bilangan bulat dipilih dari delapan bilangan bulat positif pertama, maka pasti ada sepasang bilangan bulat dengan jumlah $9$.
Diberikan delapan bilangan bulat, yaitu $1,2,\ldots,8$. Kelompokkan bilangan-bilangan ini ke dalam $4$ himpunan, yaitu $$\begin{aligned} \{1,8\},\;\{2,7\},\;\{3,6\},\;\{4,5\} \end{aligned}$$
Perhatikan bahwa setiap himpunan di atas beranggotakan dua bilangan bulat dengan jumlah $9$. Pandang empat himpunan ini sebagai sarang dan lima bilangan bulat yang dipilih sebagai merpati. Berdasarkan Prinsip Sangkar Merpati, terdapat dua bilangan bulat yang berasal dari himpunan yang sama. Kedua bilangan bulat ini memiliki jumlah $9$. Terbukti.
Buktikan bahwa jika tujuh bilangan bulat dipilih dari sepuluh bilangan bulat positif pertama, maka pasti ada sepasang bilangan bulat dengan jumlah $11$.
Diberikan sepuluh bilangan bulat, yaitu $1,2,\ldots,10$. Kelompokkan bilangan-bilangan ini ke dalam $5$ himpunan, yaitu $$\begin{aligned} \{1,10\},\;\{2,9\},\;\{3,8\},\;\{4,7\},\;\{5,6\} \end{aligned}$$
Perhatikan bahwa setiap himpunan di atas beranggotakan dua bilangan bulat dengan jumlah $11$. Pandang lima himpunan ini sebagai sarang dan tujuh bilangan bulat yang dipilih sebagai merpati. Berdasarkan Prinsip Sarang Merpati, terdapat dua bilangan bulat yang berasal dari himpunan yang sama. Kedua bilangan bulat ini memiliki jumlah $11$. Terbukti.
Berapa banyak bilangan yang harus dipilih dari himpunan $\{1,2,3,4,5,6\}$ untuk memastikan bahwa terdapat setidaknya sepasang bilangan yang jumlahnya $7$?
Partisi himpunan $\{1,2,3,4,5,6\}$ menjadi $3$ himpunan, yang masing-masing beranggotakan dua bilangan yang berjumlah $7$, yaitu $$\{1,6\},\;\{2,5\},\;\{3,4\}$$
Berdasarkan Prinsip Sarang Merpati, jika dipiih sebanyak $4$ bilangan maka akan ada dua bilangan yang berasal dari himpunan yang sama. Kedua bilangan tersebut berjumlah $7$.
Jadi, untuk memastikan bahwa terdapat setidaknya sepasang bilangan yang jumlahnya $7$, harus dipilih minimal $4$ bilangan.
Berapa banyak bilangan yang harus dipilih dari himpunan $\{1,3,5,7,9,11,13,15\}$ untuk memastikan bahwa terdapat setidaknya sepasang bilangan yang jumlahnya $16$?
Partisi himpunan $\{1,3,5,7,9,11,13,15\}$ menjadi $4$ himpunan, yang masing-masing beranggotakan dua bilangan yang berjumlah $16$, yaitu $$\{1,15\},\;\{3,13\},\;\{5,11\},\;\{7,9\}$$
Berdasarkan Prinsip Sarang Merpati, jika dipiih sebanyak $5$ bilangan maka akan ada dua bilangan yang berasal dari himpunan yang sama. Kedua bilangan tersebut berjumlah $16$.
Jadi, untuk memastikan bahwa terdapat setidaknya sepasang bilangan yang jumlahnya $16$, harus dipilih minimal $5$ bilangan.
Sebuah perusahaan menyimpan produk di dalam gudang. Tempat penyimpanan di gudang ini ditentukan berdasarkan lorong, lokasi horizontal di lorong, dan rak. Terdapat $50$ lorong, $85$ lokasi horizontal di tiap lorong, dan $5$ rak di tiap lokasi tersebut. Berapa jumlah minimum produk yang harus dimiliki perusahaan agar setidaknya dua produk harus disimpan di tempat penyimpanan yang sama?
Berdasarkan Aturan Perkalian, terdapat sebanyak $50\times85\times5=21250$ tempat penyimpanan di dalam gudang tersebut. Berdasarkan Prinsip Sarang Merpati, jika terdapat $21251$ produk maka akan ada setidaknya dua produk yang disimpan di tempat yang sama.
Jadi, jumlah minimum produk yang harus dimiliki perusahaan agar setidaknya dua produk disimpan di tempat penyimpanan yang sama adalah sebanyak $21251$ produk.
Misalkan ada sembilan mahasiswa dalam kelas Matematika Diskrit di sebuah perguruan tinggi kecil.
- Tunjukkan bahwa kelas tersebut harus memiliki setidaknya lima mahasiswa laki-laki atau setidaknya lima mahasiswa perempuan.
- Tunjukkan bahwa kelas tersebut harus memiliki setidaknya tiga mahasiswa laki-laki atau setidaknya tujuh mahasiswa perempuan.
Bagian a. Kemungkinan terburuknya adalah terdapat sebanyak $4$ mahasiswa laki-laki dan $4$ mahasiswa perempuan, sehingga tidak satupun syarat dalam soal terpenuhi. Apapun jenis kelamin dari mahasiswa ke-$9$, pasti akan ada $5$ mahasiswa laki-laki atau $5$ mahasiswa perempuan. Terbukti.
Bagian b. Kemungkinan terburuknya adalah terdapat sebanyak $2$ mahasiswa laki-laki dan $6$ mahasiswa perempuan, sehingga tidak satupun syarat dalam soal terpenuhi. Apapun jenis kelamin dari mahasiswa ke-$9$, pasti akan ada $3$ mahasiswa laki-laki atau $7$ mahasiswa perempuan. Terbukti.
Misalkan setiap siswa dalam kelas matematika diskrit yang berjumlah 25 siswa adalah mahasiswa tingkat pertama, kedua, atau ketiga. Tunjukkan bahwa harus ada setidaknya sembilan mahasiswa tingkat pertama, setidaknya sembilan mahasiswa tingkat kedua, atau setidaknya sembilan mahasiswa tingkat ketiga dalam kelas tersebut.
- Tunjukkan bahwa harus ada setidaknya $9$ mahasiswa tingkat pertama, setidaknya $9$ mahasiswa tingkat kedua, atau setidaknya $9$ mahasiswa tingkat ketiga dalam kelas tersebut.
- Tunjukkan bahwa harus ada setidaknya $3$ mahasiswa tingkat pertama, setidaknya $19$ mahasiswa tingkat kedua, atau setidaknya $5$ mahasiswa tingkat ketiga dalam kelas tersebut.
Bagian a. Kemungkinan terburuknya adalah terdapat sebanyak $8$ mahasiswa tingkat pertama, $8$ mahasiswa tingkat kedua, dan $8$ mahasiswa tingkat ketiga, sehingga tidak satupun syarat dalam soal terpenuhi. Apapun kategori dari mahasiswa ke-$25$, pasti akan ada setidaknya $9$ mahasiswa tingkat pertama, setidaknya $9$ mahasiswa tingkat kedua, atau setidaknya $9$ mahasiswa tingkat ketiga dalam kelas tersebut. Terbukti.
Bagian a. Kemungkinan terburuknya adalah terdapat sebanyak $2$ mahasiswa tingkat pertama, $18$ mahasiswa tingkat kedua, dan $4$ mahasiswa tingkat ketiga, sehingga tidak satupun syarat dalam soal terpenuhi. Apapun kategori dari mahasiswa ke-$25$, pasti akan ada setidaknya $3$ mahasiswa tingkat pertama, setidaknya $19$ mahasiswa tingkat kedua, atau setidaknya $5$ mahasiswa tingkat ketiga dalam kelas tersebut. Terbukti.
Buktikan bahwa jika $25$ pria dan $25$ wanita duduk mengelilingi meja bundar, maka selalu ada seseorang yang bersebelahan dengan dua orang pria (di sebelah kiri dan kanannya).
Beri label pada setiap kursi di sekeliling meja bundar tersebut dengan $1$ sampai dengan $50$. Karena kursi tersebut berada di sekeliling meja bundar, kursi berlabel $1$ bersebelahan dengan kursi berlabel $50$.
Terdapat $25$ kursi berlabel genap dan $25$ kursi berlabel ganjil. Pandang $2$ jenis kursi ini sebagai sarang dan $25$ pria sebagai merpati. Berdasarkan Prinsip Sangkar Burung yang diperumum, ada setidaknya $\lceil 25/2 \rceil=13$ pria yang duduk pada salah satu jenis kursi.
Tanpa mengurangi keumuman, misalkan jenis kursi tersebut berlabel ganjil. Akan ditunjukkan bahwa setidaknya dua orang pria duduk pada kursi berlabel ganjil yang berurutan (misalnya $3$ dan $5$ atau $15$ dan $17$).
Andaikan tidak ada dua orang pria yang duduk pada kursi berlabel ganjil berurutan. Karena terdapat $25$ kursi berlabel ganjil yang disusun melingkar, maka setelah menempatkan $13$ pria, akan ada sebanyak $13$ kursi kosong berlabel ganjil di antara mereka. Akibatnya, terdapat sebanyak $13+13=26$ kursi berlabel ganjil. Kontradiksi.
Dengan demikian, setidaknya ada dua orang pria yang duduk pada kursi berlabel ganjil berurutan. Seseorang yang duduk di antara mereka akan bersebelahan dengan dua orang pria (di sebelah kiri dan kanannya). Terbukti.
Di sebuah kota dengan populasi sebesar dua juta jiwa, terdapat aturan yang mengharuskan seseorang mempunyai nama yang terdiri dari dua kata, sehingga inisial dari seseorang selalu terdiri dari dua huruf. Buktikan bahwa terdapat sedikitnya sembilan orang yang mempunyai inisial dan tanggal lahir yang sama (tidak mesti di tahun yang sama).
Inisial dari seseorang di kota itu terdiri dari $26$ huruf, sehingga terdapat sebanyak $26 \times 26$ kemungkinan inisial. Karena terdapat $366$ kemungkinan tanggal lahir, secara keseluruhan terdapat sebanyak $26 \times 26 \times 366$ kombinasi inisial-tanggal lahir.
Berdasarkan Prinsip Sarang Merpati yang diperumum, terdapat sedikitnya $$\left\lceil \frac{2000000}{26 \times 26 \times 366} \right\rceil=9$$ orang di kota tersebut yang mempunyai inisial dan tanggal lahir yang sama. Terbukti.
Pada abad ke-17, terdapat lebih dari $800.000$ penduduk di Paris. Pada masa itu, diyakini bahwa tidak ada orang yang memiliki lebih dari $200.000$ helai rambut di kepala mareka. Dengan asumsi bahwa angka-angka ini benar dan setiap orang memiliki setidaknya satu helai rambut di kepala mereka (tidak ada yang sepenuhnya botak), buktikan bahwa pasti ada dua orang Paris yang memiliki jumlah helai rambut yang sama di kepala mereka. Tunjukkan pula bahwa pasti ada setidaknya lima orang Paris pada waktu itu dengan jumlah helai rambut yang sama di kepala mereka.
Terdapat $200.000$ kemungkinan banyaknya helai rambut dan setidaknya $800.001$ penduduk di paris pada waktu itu. Pandang banyak helai rambut yang mungkin sebagai sangkar dan penduduk sebagai burung. Berdasarkan Prinsip Sangkar Burung, terdapat setidaknya dua orang Paris yang memiliki jumlah rambut yang sama di kepala mereka.
Lebih lanjut, berdasarkan Prinsip Sarang Merpati yang diperumum, terdapat setidaknya $$\left\lceil \frac{800001}{200000} \right\rceil = 5$$ orang Paris yang memiliki jumlah rambut yang sama di kepala mereka.
Terdapat $38$ periode waktu berbeda di mana kelas di sebuah kampus dapat dijadwalkan. Jika terdapat $677$ kelas yang berbeda, berapa banyak ruangan yang dibutuhkan?
Pandang $38$ periode waktu yang tersedia sebagai sarang dan $677$ kelas yang berbeda sebagai merpati. Berdasarkan Prinsip Sarang Merpati yang diperumum, terdapat setidaknya $\lceil 677/38 \rceil = 18$ kelas yang berlangsung pada periode waktu yang sama. Dengan demikian, banyak ruang kelas yang dibutuhkan minimal sebanyak $18$ ruangan.
Sebuah jaringan komputer terdiri dari enam komputer. Setiap komputer terhubung langsung ke setidaknya satu komputer lainnya. Tunjukkan bahwa terdapat setidaknya dua komputer dalam jaringan yang terhubung langsung ke komputer lain dengan jumlah yang sama.
Karena terdapat enam komputer dan setiap komputer terhubung ke setidaknya satu komputer lainnya, maka jumlah komputer yang mungkin terhubung ke suatu komputer adalah $1$, $2$, $3$, $4$, atau $5$.
Pandang lima kemungkinan tersebut sebagai sarang dan enam komputer dalam jaringan sebagai merpati. Berdasarkan Prinsip Sarang Merpati, terdapat setidaknya dua komputer dalam jaringan yang terhubung langsung ke komputer lain dengan jumlah yang sama. Terbukti.
Sebuah jaringan komputer terdiri dari sepuluh komputer. Setiap komputer terhubung langsung ke nol atau lebih komputer lainnya. Tunjukkan bahwa terdapat setidaknya dua komputer dalam jaringan yang terhubung langsung ke komputer lain dengan jumlah yang sama.
Karena terdapat sepuluh komputer, jumlah komputer yang mungkin terhubung ke suatu komputer adalah anggota dari himpunan $\{0,1,2,\ldots,9\}$. Karena kardinalitas himpunan ini sama dengan banyaknya komputer yang ada, Prinsip Sangkar Burung belum bisa diterapkan.
Perhatikan bahwa $0$ dan $9$ tidak mungkin muncul secara bersamaan dalam sebuah jaringan komputer. Jika sebuah komputer terhubung langsung ke $9$ komputer, maka komputer lainnya akan terhubung ke setidaknya $1$ komputer. Sedangkan, jika sebuah komputer terhubung dengan $0$ komputer lainnya, maka komputer lain akan terhubung ke paling banyak $8$ komputer.
Akibatnya, jumlah komputer yang mungkin terhubung ke suatu komputer adalah anggota dari himpunan $\{0,1,\ldots,8\}$ atau $\{1,2,\ldots,9\}$. Keduanya terdiri dari $9$ elemen. Pandang kesembilan elemen ini sebagai sarang dan sepuluh komputer yang ada sebagai merpati. Berdasarkan Prinsip Sarang Merpati, terdapat setidaknya dua komputer dalam jaringan yang terhubung langsung ke komputer lain dengan jumlah yang sama. Terbukti.