Prinsip Pigeonhole [PDF]

Citation preview

Prinsip Pigeonhole (Sarang Merpati) yang Dirampatkan (yang diperkuat) Jika M objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu 𝑚



kotak yang berisi minimal ⌈ 𝑛 ⌉ objek. 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 41



sedikit ⌈20⌉ = 3 merpati yang menempati 1 sarang merpati. Contoh 2 50



Di antara 50 orang mahasiswa, terdapat paling sedikit ⌈12⌉= 5 orang yang lahir pada bulan yang sama.



Contoh 3 Dalam matakuliah Kombinatorik 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 62



kelompoknya sebagai anggota daerah kawan Y . Karena |X| = 62, |Y | = 6 dan ⌈ 6 ⌉= 11. Maka dengan menggunakan Prinsip Generalized Pigeonhole, terdapat paling sedikit 11 anggota X yang dipasangkan dengan suatu anggota Y yang sama. Dengan demikian 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 ∈ X yang dipasangkan ke rumah merpati yang sama, yaitu f(x1) = f(x2) untuk beberapa x1, x2 ∈X, dimana x1 ≠ x2.



Generalisasi Prinsip Pigeonhole



Teorema [Generalisasi Prinsip Pigeonhole] Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y, dimana |X|=n, |Y|=m dan ⌈n/m⌉=k, maka terdapat paling sedikit k anggota x1, x2,...,xk ∈X sedemikian hingga f(x1) = f(x2) =... = f(xk)



Bukti: Andaikan kesimpulan salah, maka terdapat paling banyak ⌈n/m⌉ − 1= k −1 anggota x1, x2,...,xk – 1 ∈ X sedemikian hingga f(x1) = f(x2) =...= f(xk -1) Dengan asumsi ini, maka banyaknya anggota X paling banyak adalah: m(k−1) < m(k−1+1) = m×n/m=n yang merupakan sebuah kontradiksi. Oleh karena itu, terdapat paling sedikit k anggota x1, x2,...,xk ∈X sedemikian hingga f(x1) = f(x2) =...= f(xk)



Contoh 4 Diantara 100 orang sedikitnya ada ⌈100/12⌉=9 orang yang lahir pada bulan yang sama



Contoh 5 Dalam matakuliah Kombinatorika diberikan tugas kelompok yang akan dibagi menjadi enam kelompok. Jika terdapat 62 mahasiswa yang menempuh mata kuliah tersebut, tunjukkan bahwa terdapat palingsedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama! Jawab: Berdasarkan Teorema 1 jika kita misalkan



X



adalah himpunan 62 mahasiswa yang menempuh mata kuliah matematika diskrit, dan Y adalah himpunan 6 kelompok pada mata kuliah matematika diskrit, maka akan ada paling sedikit



⌈62/ 6⌉=11 mahasiswa yang menjadi anggota suatu kelompok yang sama.



Pertanyaan yang lazim ditanyakan sehubungan dengan Generallisasi Prinsip Pigeonhole adalah jumlah minimum objek sedemikian hingga sedikitnya ada salah satu



m



k objek yang berada dalam



box ketika objek - objek tersebut didistribusikan diantara box. Ketika kita



memiliki n objek, berdasarkan Teorema 1 seharusnya ada sedikitnya k objek dalam salah satu box selama ⌈n/m⌉ ≥ k. Nilai bilangan bulat terkecil n dengan n/m > k−1 yaitu n = m(k−1)+1 adalah nilai bilangan bulat terkecil yang memenuhi ketaksamaan ⌈n/m⌉



≥ k. Bisakah sebuah



nilai yang lebih kecil dari n mencukupi jumlah minimum objek? Jawabannya tidak, karena jika kita memiliki



m(k−1) objek, kita hanya dapat meletakkan k−1 dari objek - objek itu pada



masing - masing



m



box dan tidak ada box yang memilik sedikitnya



k



objek.



Ketika kita memikirkan permasalahan dengan tipe seperti ini, kita juga bisa mempertimbangkan bagaimana menghindari untuk memiliki sedikitnya k objek pada salah satu



m box saat menambahkan objek secara berturut - turut. Untuk menghindari penambahan pada objek ke-k pada sebarang box, kita harus berhenti saat ada



k−1 objek pada masing - masing



box. Hal ini karena tidak mungkin kita menambahkan objek selanjutnya tanpa meletakkan objek ke-k pada box. Contoh 6 Berapakah jumlah minimum mahasiswa yang dibutuhkan dalam kelas matematika diskrit sedemikian hingga sedikitnya ada 6 mahasiswa yang memiliki nilai grade yang sama jika ada lima kemungkinan nilai gradematematika diskrit yaitu A,B,C,D, dan E? Jawab: Jumlah minimum mahasiswa yang dibutuhkan dalam kelas matematika diskrit yang sedikitnya ada 6 mahasiswa yang memiliki nilai grade yang sama adalah nilai terkecil n sedemikian hingga ⌈n/5⌉=6. Nilai terkecil n



∈Z



∈ Z tersebut yaitu n = 5.5+1=26



. Jika kita hanya memiliki 25 mahasiswa maka sedikitnya hanya ada 5 mahasiswa yang memiliki nilai grade yang sama. Oleh karenanya, 26 adalah jumlah minimum mahasiswa sedemikian hingga sedikitnya ada 6 mahasiswa yang memiliki nilaigrade yang sama.



Contoh 7 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 ditambah 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 berbeda. Sehingga kita mempunyai ai = aj + 1 Dengan demikian kode ai berurutan dengan kode aj .



APLIKASI PRINSIP PIGEONHOLE Walaupun prinsip pigeonhole merupakan prinsip yang sangat sederhana, prinsip ini mempunyai banyak aplikasi antara lain : 1. Aplikasi Pada Sains Komputer Salah satu aplikasi prinsip pigeonhole pada sains komputer adalah pada hash collision. Sebagai informasi, algoritma hash mengubah suatu data apapun ke dalam bentuk data lain. Hal ini dilakukan dengan memproses data tersebut dalam suatu formula matematika kompleks untuk menghasilkan hash unik bagi setiap potongan data. Umumnya, hash yang dihasilkan memiliki bit yang sama untuk setiap algoritma hash yang sama. Jika data yang diproses lebih kecil dari bit minimal hash yang akan dihasilkan, maka algoritma hash yang bersangkutan akan menambahkan junk data untuk mengisi bit yang tidak terpakai. Hash collision terjadi apabila dua data atau lebih menghasilkan hash yang sama. Menggunakan prinsip pigeonhole, hash collision merupakan hal yang tidak terhindarkan, terlebih jika data yang di hash berukuran besar. Hal ini dikarenakan hash yang tersedia lebih sedikit daripada potongan data yang diproses. Anggap hash sebagai sarang burung merpati dan potongan data yang diproses sebagai burung merpati. Maka, pasti ada hash yang merepresentasikan lebih dari satu potongan data. Aplikasi yang kedua adalah pada kompresi data. Kompresi data adalah proses memampatkan suatu data apapun ke dalam bentuk dengan ukuran yang lebih kecil. Dengan prinsip pigeonhole, dapat dibuktikan tidak mungkin ada algoritma kompresi yang dapat selalu berhasil memampatkan data menjadi lebih kecil. Hal ini dikarenakan ukuran yang lebih kecil berarti bit yang lebih sedikit, sehingga jika hasil kompresi dianalogikan dengan sarang burung



merpati, jumlah sarang burung merpati selalu lebih sedikit daripada merpatinya (yaitu data yang akan diproses dengan algoritma kompresi). 2. Aplikasi Pada Permasalahan Relasi Prinsip pigeonhole dapat diaplikasikan dalam berbagai permasalahan relasi. Misalkan ada pertemuan yang dihadiri oleh 50 orang. Dari 50 orang tersebut, ada beberapa yang kenal satu sama lain. Kita dapat membuktikan bahwa dalam ruangan tersebut pasti ada dua orang dengan jumlah kenalan yang sama menggunakan prinsip pigeonhole. Dengan mengasumsikan satu orang tidak mempunyai kenalan sama sekali, jumlah maksimum kenalan satu orang adalah 48. Maka, anggap jumlah kenalan dari 0 sampai 48 sebagai sarang burung merpati, dan anggap 50 orang yang hadir pada pertemuan tersebut sebagai merpatinya. Berdasarkan prinsip pigeonhole, setidak-tidaknya akan ada dua orang yang mempunyai jumlah kenalan yang sama. Begitu pula jika kita asumsikan masing-masing orang yang hadir pada pertemuan tersebut mempunyai setidaknya satu kenalan, sehingga maksimum jumlah kenalan dari seseorang adalah 49. Jika dianggap jumlah kenalan dari 1 sampai 49 sebagai sarang burung merpati dan 50 orang yang hadir pada pertemuan tersebut sebagai merpatinya, tetap setidak-tidaknya ada dua orang yang mempunyai jumlah kenalan yang sama. Aplikasi prinsip pigeonhole dalam relasi cukup berguna dalam mengaproksimasi kebutuhan minimal yang harus disiapkan dalam hal tertentu. Misalkan suatu perusahaan kereta api mempunyai statistik jumlah pengguna 500 setiap harinya. Jika ada 20 lintasan kereta api yang berbeda, maka berdasarkan prinsip pigeonhole minimal ada 25 pengguna dengan lintasan kereta api yang sama. Maka dari itu, minimalnya perusahaan kereta api tersebut menyediakan kereta api yang mempunyai daya tampung 25 pengguna untuk setiap jurusan untuk memenuhi kebutuhan minimal tiap lintasan.



3. Aplikasi Pada Permasalahan Numerikal Prinsip pigeonhole mampu menyelesaikan beberapa permasalahan numerikal. Contoh pertama adalah permasalahan divisibilitas. Dengan prinsip pigeonhole, kita mampu membuktikan bahwa pasti ada dua angka dalam n angka yang selisihnya habis dibagi angka n-1 dengan n bilangan bulat positif ≥ 2. Kita ambil contoh n = sepuluh, sehingga dalam sepuluh angka yang diberikan ada minimal dua angka dengan selisih habis dibagi sembilan. Sisa dari pembagian suatu angka dengan sembilan juga berjumlah sembilan, yaitu 0, 1, 2, 3, 4, 5, 6, 7, dan 8. Jika sisa dari pembagian suatu angka dengan sembilan tersebut kita analogikan sebagai



sarang burung merpati dan sepuluh angka yang diberikan kita analogikan sebagai merpati, maka dalam sepuluh angka tersebut minimal ada dua angka yang mempunyai sisa yang sama dari pembagian terhadap sembilan. Dua angka inilah yang bila diselisihkan selisihnya akan habis dibagi sembilan. 4.. Aplikasi Pada Trik Kartu Kombinatorik Prinsip pigeonhole dapat digunakan dalam trik kartu kombinatorik sebagai berikut: seorang asisten pesulap mengambil lima kartu secara acak dari sebuah set kartu bridge. Sebagai catatan, satu set kartu bridge terdiri dari empat lambang dengan masing-masing lambang terdiri dari 13 kartu. Kemudian, asisten tersebut memilih salah satu kartu sebagai kartu yang disembunyikan dan memperlihatkan sisanya kepada pesulap. Maka, pesulap yang melihat keempat kartu tersebut dapat menentukan lambang dan nilai dari kartu yang disembunyikan. Pada kelima kartu yang diambil seorang asisten pesulap, berdasarkan prinsip pigeonhole, ada dua atau lebih kartu dengan lambang yang sama. Hal ini dimanfaatkan asisten pesulap untuk memberi tahu pesulap lambang kartu yang disembunyikan. Hal itu dilakukan dengan menaruh kartu berlambang sama tersebut pada urutan pertama dari kartu yang diperlihatkan. Pemilihan kartu yang disembunyikan dengan kartu yang diperlihatkan juga mengambil peran penting. Aspek yang diperhatikan dalam pemilihan kartu yang disembunyikan dan kartu yang diperlihatkan adalah ‘jarak’ kedua kartu tersebut satu sama lain. Jarak kedua kartu didefinisikan sebagai perbedaan nilai yang harus ditambahkan kartu pertama untuk mencapai kartu kedua. Dalam jarak kedua kartu ini, jarak kartu A ke kartu B tidak sama dengan jarak kartu B ke kartu A karena nilai jarak bersifat sirkuler. Untuk memudahkan perhitungan jarak, kartu Jack, Queen, dan King dilambangkan sebagai angka 11, 12, dan 13. Contoh memperoleh jarak dari dua buah kartu adalah sebagai berikut: pada kartu bernilai 1 dan 2, jarak kartu 1 ke 2 adalah 1 sedangkan jarak kartu 2 ke 1 adalah 12. Jumlah jarak suatu kartu ke kartu lain dengan jarak kebalikannya selalu 13. Maka, berdasarkan prinsip pigeonhole, jarak antar dua buah kartu selalu ada yang ≤ 6. Kartu pertama pada jarak antar dua kartu yang ≤ 6 merupakan kartu yang diperlihatkan pada pesulap, sedangkan kartu kedua disembunyikan. Berikutnya, tiga kartu yang diperlihatkan lainnya digunakan untuk memberi nilai jarak yang harus ditambahkan pada kartu pertama (kartu yang berlambang sama dengan yang disembunyikan) sehingga pesulap mengetahui persis kartu apa yang disembunyikan. Cara menyusun tiga kartu dihitung dengan permutasi berjumlah 3! = 6. Hal inilah yang mendasari pemilihan kartu yang diperlihatkan harus kartu yang jaraknya ≤ 6 dengan kartu yang disembunyikan. Melalui urutan tiga kartu yang disusun asisten pesulap, pesulap dapat



mengetahui pertambahan yang harus dilakukan terhadap kartu pertama sehingga pesulap tersebut dapat menebak kartu yang disembunyikan. Urutan tiga kartu yang disusun merepresentasikan salah satu angka dari 1-6 tergantung kesepakatan asisten pesulap dengan pesulap. Misalkan, ABC bernilai 1, ACB bernilai 2, BAC bernilai 3, BCA bernilai 4, CAB bernilai 5, dan CBA bernilai 6 dengan A kartu bernilai terbesar dan C kartu bernilai terkecil. Jika ada dua buah kartu dengan nilai yang sama, maka yang diperhatikan adalah lambangnya. Misalkan asisten pesulap mendapat kartu 10♠, 5♣, K♥, 7♦, dan 10♦. Maka, yang kartu yang disembunyikan pasti salah satu dari 7♦ dan 10♦. Karena jarak dari 7 ke 10 adalah 3 sedangkan jarak dari 10 ke 7 adalah 10, maka 10♦ disembunyikan. Selanjutnya, dari 3 kartu 10♠, 5♣, dan K♥, harus dibuat suatu urutan sehingga pesulap menginterpretasikan urutan tersebut sebagai angka 3. Maka sesuai kesepakatan sebelumnya urutan yang merepresentasikan nilai 3 adalah BAC dengan A kartu terbesar dan C kartu terkecil, sehingga urutan kartu yang diperlihatkan asisten pesulap kepada pesulap adalah 7♦ (untuk memberi tahu lambang dan nilai inisial), 10♠, K♥, dan 5♣.



5. Aplikasi Pada Teori Ramsey Secara umum, teori Ramsey membahas distribusi subset elemen dalam suatu set elemen. Teori Ramsey merupakan extremal combinatorics yang memberikan jumlah objek jika kumpulan objek tersebut harus memenuhi kondisi tertentu. Berikut adalah permasalahan yang dapat memberikan gambaran mengenai teori Ramsey: dalam suatu grup yang terdiri dari enam orang, hubungan antara sepasang orang dapat berupa pertemanan ataupun permusuhan; buktikan bahwa ada setidaknya tiga orang yang saling berteman atau tiga orang yang saling bermusuhan. Misalkan A merupakan salah satu dari keenam orang tersebut, maka setidaknya tiga orang dari lima orang selain A bermusuhan atau berteman dengan A (sesuai prinsip pigeonhole). Anggap B, C, D berteman dengan A. Maka, jika dua dari B, C, D berteman, akan terbentuk tiga orang yang saling berteman. Sebaliknya, jika tidak, maka akan terbentuk tiga orang yang saling bermusuhan. Bila dikaitkan dengan permasalahan tersebut, bilangan Ramsey dengan notasi R(m,n) merupakan jumlah minimum orang yang diperlukan untuk menghasilkan m orang yang saling berteman atau n orang yang saling bermusuhan. Berdasarkan solusi dari permasalahan tersebut, R(3,3) = 6.