Prinsip-Sarang-Merpati - Edit [PDF]

Citation preview

PRINSIP SARANG BURUNG MERPATI PIGEONHOLE PRINCIPLE



Suatu prinsip sederhana yang disebut prinsip rumah merpati (Pigeonhole principle atau disebut The Box Principle pada beberapa referensi) ditemukan pada tahun 1834 oleh seorang matematikawan Jerman bernama Johann Peter Gustav Lejeune Dirichlet. Prinsip ini merupakan salah satu alat kombinatorial yang berguna dalam menghitung objek dengan property tertentu. Prinsip pigeonhole mempunyai banyak pengaplikasian atau penerapan, diantaranya dalam sains komputer, permasalahan relasi, pembagian, permasalahan numerikal, permasalahan geometri umum, trik kartu kombinatorik, fungsi kuadrat, dan teori ramsey. Prinsip sarang merpati juga merupakan sebuah contoh dari argument menghitung yang bisa diaplikasikan kebanyak masalah formal, termasuk yang mengandung himpunan tak terhingga yang tidak bisa dinyatakan dalam fungsi korespodensi satu-satu.



PEMBAHASAN 2.1 Prinsip sarang Merpati Sebagai ilustrasi, kita misalkan terdapat 3 ekor burung merpati dan 2 sangkar burung merpati. Terdapat beberapa kemungkinan bagaimana burung-burung itu menempati sangkarnya. Berikut ini disajikan peristiwa bagaimana burung merpati menempati sangkar-sangkar itu.



Dari keempat peristiwa yang terjadi pada ilustrasi di atas, tampak bahwa di setiap peristiwa itu selalu ada satu sangkar burung atau lebih yang ditempati beberapa burung merpati. Lebih tepatnya kita katakan “paling sedikit ada satu sangkar burung yang ditempati oleh paling sedikit dua ekor burung merpati”.



1



Prinsip Sarang Merpati (Pigeonhole) Bentuk Pertama “Jika (n + 1) atau lebih obyek ditempatkan ke dalam n kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau lebih obyek tersebut.” Pembuktian: Missal Jika n merpati ditempatkan pada m rumah merpati, dimana n > m, maka terdapat rumah merpati yang memuat paling sedikit dua merpati. Untuk membuktikan pernyataan Prinsip Pigeonhole ini, kita gunakan kontradiksi. Misalkan kesimpulan dari pernyataan tersebut salah, sehingga setiap rumah merpati memuat paling banyak satu merpati. Karena ada m rumah merpati, maka paling banyak m merpati yang bisa dimuat. Padahal ada n merpati yang tersedia dan n > m, sehingga kita dapatkan sebuah kontradiksi. Contoh 1 Jika terdapat 11 pemain dalam sebuah tim sepakbola yang menang dengan angka 12-0, maka haruslah terdapat paling sedikit satu pemain dalam tim yang membuat gol paling sedikit dua kali. Contoh 2 Jika anda menghadiri 6 kuliah dalam selang waktu Senin sampai Jumat, maka haruslah terdapat paling sedikit satu hari ketika anda menghadiri paling sedikit dua kelas. Contoh 3 Dari 27 orang mahasiswa, paling sedikit terdapat dua orang yang namanya diawali dengan huruf yang sama, karena hanya ada 26 huruf dalam alfabet. Kita menganggap 27 huruf awal dari nama-nama mahasiswa sebagai merpati dan 26 huruf alfabet sebagai sarang merpati. Menurut prinsip pigeonhole, beberapa huruf awal alfabet dipasangkan dengan paling sedikit dua huruf awal nama mahasiswa. Contoh 4 Misalkan terdapat banyak bola merah, bola putih, dan bola biru di dalam sebuah kotak. Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat ke dalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil.



2



Penyelesaian Jika setiap warna dianggap sebagai sarang merpati, maka n =  3. Karena itu, jika orang mengambil paling sedikit n + 1 = 4 bola (merpati), maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil. Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain. Jadi 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama. Contoh 5 Misalkan sebuah turnamen basket diikuti oleh n buah tim yang dalam hal ini setiap tim bertanding dengan setiap tim lainnya dan setiap tim menang paling sedikit satu kali. Tunjukkan bahwa paling sedikit ada 2 tim yang mempunyai jumlah kemenangan yang sama. Penyelesaian Jumlah kemenangan setiap tim paling sedikit 1 kali dan paling banyak n-1 kali. Angka n-1 berkorespondensi dengan n-1 buah sarang merpati untuk menampung n ekor merpati (tim basket). Jadi, paling sedikit ada 2 tim basket yang mempunyai jumlah kemenangan sama. Contoh 6 Dalam sekumpulan n orang di mana setiap orang minimal kenal dengan satu orang di kelompok tersebut, terdapat dua orang yang memiliki banyaknya kenalan di kelompok tersebut yang sama. (Contoh: ada dua orang yang sama-sama memiliki 20 kenalan dalam kelompok tersebut) Penyelesaian Dalam kasus ini jelas bahwa banyaknya kenalan sebagai sarang merpati dan banyaknya orang sebagai merpati.  Sekarang kita buktikan bahwa sarang lebih sedikit daripada merpatinya. Setiap orang minimal kenal dengan satu orang, maka banyaknya kenalan yang mungkin adalah 1 kenalan, 2 kenalan, 3 kenalan, dan seterusnya sampai n-1 kenalan. Sehingga ada n-1 kemungkinan banyaknya kenalan pada orang di dalam kelompok tersebut. Karena ada n orang, maka jelas bahwa pasti terdapat dua orang yang memiliki banyak kenalan yang sama.



3



Prinsip Sarang Merpati yang Diperumum Prinsip sangkar burung merpati menyatakan bahwa terdapat paling sedikit 2 obyek dalam kotak yang sama jika terdapat obyek yang lebih banyak dari kotaknya. Misalnya, di antara 31 angka desimal, pasti terdapat paling sedikit 4 angka yang sama. Ini karena jika ke 31 angka tadi didistribusikan pada 10 kotak, satu kotak tentu akan memiliki lebih dari 3 obyek. Secara umum situasi ini kita rumuskan sebagai berikut. “Jika M obyek ditempatkan ke dalam n kotak, maka terdapat paling sedikit satu kotak yang memuat sedikitnya [M/n] obyek.”



Contoh 1 Jika terdapat 20 sarang merpati dan 41 ekor merpati, maka terdapat satu buah sarang yang berisi lebih dari 2 ekor merpati. Atau dengan menggunakan rumus diperoleh paling sedikit [ 41 / 20 ] = 3 merpati yang menempati 1 sarang merpati. Contoh 2 Di antara 50 orang mahasiswa, terdapat paling sedikit  [ 50 / 12 ] = 5 orang yang lahir pada bulan yang sama. Contoh 3 Dalam matakuliah Matematika Diskrit diberikan tugas kelompok yang akan dibagi menjadi enam kelompok. Jika terdapat 62 mahasiswa yang menempuh mata kuliah tersebut, tunjukkan bahwa terdapat paling sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama! Penyelesaian Kita asumsikan mahasiswa tersebut sebagai anggota dari himpunan daerah asal X  dan kelompoknya sebagai anggota daerah kawan Y  . Karena |X| = 62, |Y | = 6 dan [62/6] = 11. Maka dengan menggunakan Prinsip Generalized Pigeonhole, terdapat paling sedikit 11 anggota Xyang dipasangkan dengan suatu anggota Y yang sama. Dengan demikian



4



terdapat paling sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama.



Prinsip Sarang Merpati (Pigeonhole) Bentuk Kedua “Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y dan |X| > |Y |, maka f(x1) = f(x2) untuk beberapa x1, x2  anggota X, dimana x1 ≠ x2.” Pembuktian: Untuk membuktikan Prinsip Pigeonhole Bentuk Kedua ini kita bisa mengasumsikan X sebagai himpunan merpati dan Y sebagai himpunan rumah merpati. Selanjutkan kita memasangkan merpati x ke rumah merpati f(x). Karena jumlah merpati lebih banyak dari rumahnya, maka terdapat paling sedikit dua merpati, x1, x2 anggota X yang dipasangkan ke rumah merpati yang sama, yaitu f(x1) = f(x2) untuk beberapa x1, x2  anggota X, dimana x1 ≠ x2. Contoh Dalam membuat kode matakuliah untuk matakuliah-matakuliah bidang studi informatika adalah dengan cara menambahkan tiga angka pada huruf TIK. Terdapat 51 matakuliah yang harus diberi kode dan tiga angka yang harus ditambahkan pada huruf TIK harus berkisar antara 101 sampai dengan 200. Tunjukkan bahwa terdapat paling sedikit dua matakuliah yang diberi kode dengan angka berurutan. Penyelesaian Misalkan angka-angka yang dipilih adalah a1, a2 ,…, a51. Jika angka-angka diatas digunakan bersama-sama dengan a1 + 1, a2 + 1, …, a51 + 1 maka terdapat 102 nomor yang merentang antara 101 sampai dengan 201. Karena ada 100 nomor yang disediakan (yaitu 101 sampai dengan 200) dan ada 102 nomor yang akan digunakan, maka menurut Prinsip Pigeonhole Bentuk Kedua terdapat paling sedikit dua nomor yang sama. Nomor a1, a2, …, a51 dan a1 + 1, a2 + 1, …, a51 + 1 semuanya 5



berbeda. Sehingga kita mempunyai ai = aj + 1 Dengan demikian kode ai berurutan dengan kode aj .



Latihan: Buatlah 5 soal dan jawaban terkait materi prinsip sarang merpati.



Tugas terstruktur dan mandiri Dari soal ini, pilih dan kerjakanlah 5 soal sebagai tugas terstruktur, dan sisanya kerjakan sebagai tugas mandiri (jumlah terserah). Tulis jawaban dikertas doble Folio, lalu fotokan, kirim melalui Google Clasroom. 1. Misalkan terdapat sebuah himpunan bilangan bulat. Maka terdapat dua bilangan bulat yang sama memiliki sisa yang sama jika keduanya dibagi 4. 5. 2. Misalkan a adalah bilangan asli. Tunjukkan bahwa di antara senbarang grup dari a+1 bilangan asli (tak perlu berurutan) terdapat 2 bilangan asli yang memiliki sisa yang sama jika keduanya dibagi bilangan a. 3. Misalkan di sebuah pertemuan terdapat 28 orang. Maka paling sedikit terdapat 2 orang yang namanya diawali dengan huruf yang sama. 4. Sebuah laci lemari diisi selusin kaus kaki berwarna biru dan selusin kaus kaki berwarna coklat yang bercampur tidak berpasangan. Seorang anak mengambil beberapa kaus kaki tersebut dalam kegelapan malam. a. Berapa kaus kaki harus diambil agar dia yakin bahwa paling sedikit dia memperoleh dua kaus kaki yang berwarna sama? b. Berapa kaus kaki harus dia ambil agar paling sedikit diperoleh dua kaus kaki berwarna biru? 5. Di awal tahun terdapat calon mahasiswa dari 40 provinsi yang mendaftar ke perguruan tinggi. Jika kita ingin agar paling sedikit terdapat 60 calon mahasiswa berasal dari provinsi yang sama, berapa banyaknya calon paling sedikit yang harus mendaftar? 6. Tunjukkan bahwa jika 5 bilangan asli dipilih dari 8 bilangan asli pertama, maka pasti terdapat sepasang bilangan asli yang jumlahnya adalah 9.



6



7. Misalkan dari 8 bilangan bulat positif pertama diambil 4 bilangan. Apakah pasti terdapat sepasang bilangan bulat positif yang jumlahnya 9? 8. Perlihatkan bahwa jika 7 bilangan dipilih dari 10 bilangan asli pertama, maka pasti terdapat paling sedikit dua pasang bilangan yang jumlahnya 11. 9. Misalkan 6 bilangan dipilih dari 10 bilangan asli pertama. Apakah pasti terdapat paling sedikit dua pasang bilangan yang jumlahnya 11? 10. Berapa banyaknya bilangan yang harus dipilih dari himpunan {1,2,3,4,5} untuk memastikan bahwa paling sedikit sepasang bilangan dari bilangan-bilangan dalam himpunan ini jumlahnya 6. 11. Berapa banyaknya bilangan yang harus dipilih dari himpunan {1,2,3,4,5,6} untuk memastikan bahwa paling sedikit sepasang bilangan dari bilangan-bilangan dalam himpunan ini jumlahnya 7. 12. Di sebuah perkuliahan matematika kombinatorik terdapat sembilan mahasiswa. Perlihatkan bahwa di perkuliahan tersebut paling sedikit terdapat paling sedikit lima mahasiswa pria atau paling sedikit lima mahasiswa wanita. Tunjukkan pula bahwa di perkuliahan tersebut terdapat paling sedikit tiga mahasiswa pria atau paling sedikit tujuh mahasiswa wanita. 13. Misalkan bahwa tiap-tiap mahasiswa yang mengontrak mata kuliah persamaan diferensial yang jumlahnya mencapai dua puluh lima orang adalah mahasiswa asal Pulau Jawa, Pulau Sumatra, atau Pulau Kalimantan. Perlihatkan bahwa terdapat paling sedikit sembilan mahasiswa asal Pulau Jawa, paling sedikit sembilan mahasiswa asal Pulau Sumatra, atau paling sedikit sembilan mahasiswa asal Pulau Kalimantan. Tunjukkan pula bahwa terdapat paling sedikit tiga mahasiswa asal Pulau Jawa, paling sedikit sembilan belas mahasiswa asal Pulau Sumatra, atau paling sedikit lima mahasiswa asal Pulau Kalimantan. 14. Susunlah sebuah barisan yang terdiri atas enam belas bilangan asli yang mengandung barisan bagian dengan lima suku, demikian sehingga barisan bagian tersebut termasuk barisan naik atau barisan turun. 15. Perlihatkan bahwa di antara 101 peserta seminar yang tinggi badannya semuanya berbeda, terdapat sebelas orang yang dapat diminta berdiri dalam satu barisan dengan tinggi badan dari terkecil ke terbesar atau sebaliknya.



.



7



8