Pendahuluan
Prinsip sarang merpati adalah sebuah konsep dasar dalam matematika yang mungkin terdengar sederhana, namun memiliki implikasi yang luas dalam berbagai bidang, termasuk ilmu komputer. Pigeonhole Principle atau Prinsip Laci Dirichlet adalah prinsip dasar dalam kombinatorika yang menyatakan bahwa jika n objek ditempatkan ke dalam m wadah, dan n > m, maka setidaknya ada satu wadah yang akan berisi lebih dari satu objek.
Konsep Dasar
Bayangkan Anda memiliki sejumlah merpati yang ingin dimasukkan ke dalam beberapa sarang. Jika jumlah merpati lebih banyak daripada jumlah sarang, maka pasti ada setidaknya satu sarang yang berisi lebih dari satu merpati. Prinsip inilah yang disebut dengan prinsip sarang merpati.
Secara matematis, prinsip sarang merpati dapat dinyatakan sebagai berikut:
Jika terdapat $n+1$ objek yang ditempatkan ke dalam $n$ kotak, maka setidaknya ada satu kotak yang berisi dua objek atau lebih.
Jika $n$ objek ditempatkan ke dalam $m$ wadah, dan $n > m$, maka setidaknya ada satu wadah yang berisi minimal $⌈n/m⌉$ objek.
Contoh Sederhana
- Kaus Kaki: Jika Anda memiliki 13 pasang kaus kaki dengan warna yang berbeda-beda, dan Anda mengambil 13 kaus kaki secara acak, maka pasti ada setidaknya sepasang kaus kaki yang memiliki warna yang sama.
- Ulang Tahun: Dalam sebuah ruangan dengan 23 orang, kemungkinan besar ada dua orang yang memiliki tanggal lahir yang sama. Ini mungkin terdengar mengejutkan, tetapi jika kita hitung, ada 365 hari dalam setahun (tidak memperhitungkan tahun kabisat), dan 23 orang adalah lebih dari setengah dari 365.
- Misalnya ada 100 siswa dan 12 bulan dalam satu tahun. Maka, menurut Pigeonhole Principle, setidaknya ada satu bulan di mana lebih dari 8 siswa lahir. Hal ini terjadi karena: $⌈100/12⌉ = 9 siswa\text{⌈100/12⌉ = 9 siswa}⌈100/12⌉ = 9$ siswa. Jadi, minimal satu bulan akan memiliki 9 siswa yang lahir di bulan tersebut.
Penerapan dalam Ilmu Komputer
Prinsip sarang merpati memiliki banyak aplikasi dalam ilmu komputer, di antaranya:
- Analisis Algoritma:
- Membuktikan batas bawah kompleksitas waktu suatu algoritma.
- Menganalisis kinerja algoritma hashing.
- Teori Graf:
- Membuktikan keberadaan suatu jenis graf tertentu.
- Kriptografi:
- Menganalisis kekuatan suatu kriptografi.
- Kompresi Data:
- Menganalisis efisiensi algoritma kompresi.
Contoh Penerapan dalam Ilmu Komputer
- Hashing: Jika kita memiliki 1000 data yang ingin kita simpan dalam tabel hash dengan ukuran 999, maka pasti ada setidaknya satu slot dalam tabel hash yang berisi lebih dari satu data.
- Pengujian Software: Jika kita memiliki 1000 baris kode dan hanya menjalankan 999 tes kasus, maka ada kemungkinan bahwa beberapa baris kode tidak pernah diuji.
Pembuktian Formal
Bukti:
Misalkan kita memiliki $n+1$ objek dan $n$ kotak. Asumsikan bahwa setiap kotak berisi paling banyak satu objek. Maka, total jumlah objek yang dapat ditempatkan adalah $n$. Namun, kita memiliki $n+1$ objek. Ini adalah kontradiksi. Oleh karena itu, asumsi awal kita salah, dan setidaknya ada satu kotak yang berisi dua objek atau lebih.
Latihan Soal
- Terdapat 12 orang dalam sebuah ruangan. Buktikan bahwa setidaknya ada dua orang yang lahir di bulan yang sama.
Jawaban: Jumlah bulan dalam satu tahun adalah 12, sedangkan jumlah orang di ruangan juga 12. Jika setiap orang lahir di bulan yang berbeda, maka mereka akan mengisi semua bulan yang ada. Namun, menurut Pigeonhole Principle, jika ada lebih dari 12 orang (misal 13 orang), setidaknya ada dua orang yang lahir di bulan yang sama. Dalam hal ini, karena jumlah orang sama dengan jumlah bulan, minimal ada satu bulan yang memiliki dua orang lahir di bulan yang sama. - Dalam sebuah array yang berisi 10 bilangan bulat positif dengan nilai di antara 1 sampai 100, buktikan bahwa selalu ada dua bilangan yang memiliki selisih kurang dari atau sama dengan 9.
Jawaban: Kita bisa membagi rentang bilangan dari 1 hingga 100 menjadi 10 interval, masing-masing interval dengan panjang 10 (misalnya 1-10, 11-20, dst.). Jika kita memiliki 10 angka, menurut Pigeonhole Principle, minimal ada dua angka yang berada dalam interval yang sama. Karena dua angka dalam interval yang sama memiliki selisih maksimal 9, maka kesimpulannya ada dua bilangan dalam array yang memiliki selisih kurang dari atau sama dengan 9. - Dalam sebuah kelas yang terdiri dari 30 mahasiswa, setiap mahasiswa memiliki setidaknya satu buku. Jika terdapat 25 judul buku yang berbeda, buktikan bahwa setidaknya ada dua mahasiswa yang memiliki buku yang sama. (Latihan)
- Sebuah aplikasi mobile memiliki 1 juta pengguna aktif. Setiap pengguna dapat memilih dari 5 tema warna yang tersedia. Buktikan bahwa setidaknya ada 200.000 pengguna yang memilih tema warna yang sama. (Latihan)
- Dalam sebuah turnamen catur, terdapat 10 peserta. Setiap peserta bermain satu kali dengan setiap peserta lainnya. Buktikan bahwa ada dua peserta yang bermain dengan jumlah pertandingan yang sama. (Latihan)
Kesimpulan
Prinsip sarang merpati adalah alat yang sederhana namun sangat kuat dalam memecahkan berbagai masalah dalam ilmu komputer dan bidang lainnya. Prinsip ini memungkinkan kita untuk membuat kesimpulan yang kuat bahkan ketika kita tidak memiliki informasi lengkap tentang suatu sistem.
Nama : adelia marsa
nim : (isi sesuai dengan nim yang dimiliki)
saya akan menjawab soal no (pilih no soal 3, 4 atau 5).
Dalam kasus ini, kita anggap sarang merpati adalah apa. yang memiliki berapa sarang merpati. sedangkan apa sebagai merpati, maka dapat dinyatakan bahwa jika kita memiliki lebih banyak merpati daripada lubang merpati, maka setidaknya satu lubang merpati harus menampung lebih dari satu merpati. (anda dapat menjelaskan dengan kalimat lain)
3. Dalam sebuah kelas yang terdiri dari 30 mahasiswa, setiap mahasiswa memiliki setidaknya satu buku. Jika terdapat 25 judul buku yang berbeda, buktikan bahwa setidaknya ada dua mahasiswa yang memiliki buku yang sama
jawaban : Jumlah mahasiswa 30 (merpati), sedang jumlah judul buku 25 (sarang), setiap mahasiswa memiliki 1 judul buku , karena jumlah mahasiswa lebih banyak dari judul buku ( 30>25) , kita bisa menyimpulkan setidaknya ada 2 mahasiswa atau lebih yang memiliki judul buku sama.
4. Sebuah aplikasi mobile memiliki 1 juta pengguna aktif. Setiap pengguna dapat memilih dari 5 tema warna yang tersedia. Buktikan bahwa setidaknya ada 200.000 pengguna yang memilih tema warna yang sama.
jawaban : Bayangkan kita memiliki 5 sarang yang masing-masing mewakili satu tema warna. Kita kemudian memasukkan nama pengguna (merpati) ke dalam sarang yang sesuai dengan tema warna pilihannya. Karena ada 1 juta pengguna (merpati) dan hanya 5 tema warna (sarang), pasti ada setidaknya satu tema warna yang dipilih lebih dari 200.000 nama pengguna. Artinya, ada setidaknya 200.000 pengguna yang memilih tema warna yang sama
5.Dalam sebuah turnamen catur, terdapat 10 peserta. Setiap peserta bermain satu kali dengan setiap peserta lainnya. Buktikan bahwa ada dua peserta yang bermain dengan jumlah pertandingan yang sama
Jawaban : 10 Peserta (merpati), setiap peserta bermain satu kali dengan setiap peserta lainnya berarti ada 9 pertandingan (sarang) karena setiap peserta akan bermain melawan 9 peserta lainnya), 10 peserta lebih banyak dari 9 pertandingan pasti ada 2 peserta (merpati) yang bermain dengan jumlah pertandingan (sarang) yang sama
1.Dalam sebuah kelas yang terdiri dari 30 mahasiswa, setiap mahasiswa memiliki setidaknya satu buku. Jika terdapat 25 judul buku yang berbeda, buktikan bahwa setidaknya ada dua mahasiswa yang memiliki buku yang sama. (Latihan)
Jawaban: Di sini, mahasiswa bisa dianggap sebagai benda (jumlahnya 30), dan judul buku sebagai kotak (jumlahnya 25).
Menurut prinsip pigeonhole, jika kita memiliki lebih banyak benda (mahasiswa) daripada kotak (judul buku), yaitu
30>25, maka setidaknya ada dua mahasiswa yang harus berada di “kotak” yang sama, yaitu memiliki judul buku yang sama.
Jadi, pasti ada setidaknya dua mahasiswa yang memiliki buku yang sama.
2.Sebuah aplikasi mobile memiliki 1 juta pengguna aktif. Setiap pengguna dapat memilih dari 5 tema warna yang tersedia. Buktikan bahwa setidaknya ada 200.000 pengguna yang memilih tema warna yang sama. (Latihan)
Jawaban: Di sini, pengguna dianggap sebagai benda (jumlahnya 1 juta), dan tema warna sebagai kotak (jumlahnya 5).
Jika kita membagi 1 juta pengguna secara merata ke 5 tema warna, maka setiap tema warna akan dipilih oleh
1.000.000
5
=
200.000
5
1.000.000
=200.000 pengguna.
Namun, ini adalah distribusi rata-rata, dan berdasarkan prinsip pigeonhole, jika ada lebih dari 1 juta pengguna yang memilih dari hanya 5 tema warna, setidaknya satu tema akan dipilih oleh setidaknya 200.000 pengguna.
Jadi, pasti ada setidaknya satu tema warna yang dipilih oleh 200.000 atau lebih pengguna.
3.Dalam sebuah turnamen catur, terdapat 10 peserta. Setiap peserta bermain satu kali dengan setiap peserta lainnya. Buktikan bahwa ada dua peserta yang bermain dengan jumlah pertandingan yang sama. (Latihan)
Jawaban:Setiap peserta bermain dengan peserta lainnya, sehingga setiap peserta dapat bermain antara 0 hingga 9 pertandingan (karena dia tidak bermain melawan dirinya sendiri).
Ada 10 peserta, tetapi kemungkinan jumlah pertandingan yang bisa dimainkan hanya berkisar dari 0 hingga 9 (yaitu 10 kemungkinan).Namun, jika setiap peserta bermain satu kali dengan setiap peserta lainnya, setiap peserta akan memainkan minimal 1 pertandingan. Oleh karena itu, kemungkinan jumlah pertandingan berkisar dari 1 hingga 9 (hanya 9 kemungkinan).
Menurut prinsip pigeonhole, jika kita memiliki lebih banyak peserta (10) daripada jumlah kemungkinan pertandingan (9), maka pasti ada dua peserta yang memiliki jumlah pertandingan yang sama.
Jadi, pasti ada dua peserta yang bermain dengan jumlah pertandingan yang sama.
Nama : Joko Sulistio
NIM : 202401002352
Prodi : D3 Managemen Informatika
Matkul : Matematika Diskrit
Jawaban latihan soal.
(1.) Jumlah bulan dalam 1 tahun 12 bulan, diruangan ada 12 orang. Jika mereka lahir dibulan yang berbeda, maka mereka akan mengisi semua bulan yang ada. Namun jika lebih dr 12 orang ( misal 13 orang ), setidaknya ada 2 orang yg lahir dibulan hang sama. Namun karna orang dan bulannya sama jumlahnya, minimal ada 2 orang yg lahir dibulan yang sama.
(2.) Misal dibuat rentang bilangan 1 sampai 100 menjadi 10 interval. Masing-masing interval 10 digit ( 1-10, 11-20 ) . Minimal ada 2 angka yg berada di interval yg sama. Naka kesimpulannya ada 2 bilangan dalan array yang memiliki selisih kurang dari/ sama dengan 9.
(3.) Diasumsikan bahwa ada 30 mahasiwa dan 25 judul buku yang berbeda. Karena jumlah mahasiwa lebih banyak daripada bukunya, maka setidaknya ada 2 mahasiswa yang memiliki buku dengan judul yang sama .
(4.) Menentukan merpati = 1 juta pengguna , sarang = 5 tema. Dapat dibagi jumlah pengguna dengan warna tema ( 1.000.000 : 5 = 200.000 ). Artinya bahwa setidaknya ada 200.000 pengguna yang memilih tema warna yang sama.
(5.) Pertama, ada 10 peserta , setiap perserta bermain dengan 9 peserta lainya, maka total pertandingan 9 x 10 = 90 pertandingan. Namun setiap pertandingan melibatkan 2 peserta maka jumlah pertandingan yang sebenarnya adalah setengah dari jumlah pertandingan ( 9×10 = 90 , lalu 90 : 2 = 45 pertandingan ) . Karena ada 10 peserta, setiap peserta dapat bermain dengan jumlah pertandingan yang berbeda, maka dpt disimpulkan bahwa ada 2 peserta yang bermain dengan jumlah yang sama.
3. Ada 30 siswa dan 25 buku
30 siswa mengabil masing² dari 25 buku
jadi 30-25=5 ada 5 orang yang
mengambil buku yang sama
4. Ada 1jt penguna aktif apk mobile, apk mobile tersebut memiliki 5 tema jadi 1.000.000/5= 200.000 penguna yang mengunakan tema sama
5. 10 pemain catur dan terdapat 9 cara untuk menentukan jumlah 2 pertandingan yang sama
10*9 =90 90/2=45 jadi terdapat 45 cara untuk menentukan 2 pertandingan sama
Nama : Muharromah Raihana Swaherobika
NIM : 202401002355
Matkul : Matematika Diskrit
Jawaban soal nomor 3 :
Penerapan Prinsip Sarang Merpati:
• Merpati: Mahasiswa
• Sarang: Judul Buku
Dalam kasus kita:
• Kita punya 30 mahasiswa (merpati).
• Kita punya 25 judul buku (sarang).
Karena jumlah mahasiswa (merpati) lebih banyak daripada jumlah judul buku (sarang), maka berdasarkan prinsip sarang merpati, setidaknya ada dua mahasiswa (merpati) yang harus menempati sarang yang sama, yaitu memiliki judul buku yang sama.
Kesimpulan:
Dengan demikian, kita telah membuktikan bahwa dalam kelas yang terdiri dari 30 mahasiswa dengan 25 judul buku yang berbeda, pasti ada minimal dua mahasiswa yang memiliki buku yang sama.
Jawaban no 4 :
Penerapan Prinsip Sarang Merpati:
• Kita punya 1.000.000 pengguna (merpati).
• Kita punya 5 tema warna (sarang).
Jika kita bagi jumlah pengguna dengan jumlah tema warna, kita dapatkan:
• 1.000.000 pengguna / 5 tema warna = 200.000 pengguna/tema
Artinya:
Agar setiap tema warna dipilih oleh jumlah pengguna yang sama persis (yaitu 200.000 pengguna), maka setiap pengguna harus memilih tema yang berbeda. Namun, ini tidak mungkin karena jumlah pengguna jauh lebih banyak daripada jumlah tema warna yang tersedia.
Kesimpulan:
Karena jumlah pengguna jauh lebih banyak daripada jumlah tema warna, maka berdasarkan prinsip sarang merpati, setidaknya ada satu tema warna yang dipilih oleh lebih dari 200.000 pengguna. Dengan kata lain, pasti ada minimal 200.000 pengguna yang memilih tema warna yang sama.
Jawaban nomor 5 :
Penerapan Prinsip Sarang Merpati:
• Kita punya 45 pertandingan (merpati).
• Jumlah maksimum sarang (jumlah pertandingan yang mungkin dimainkan oleh seorang peserta) adalah 9.
Karena jumlah pertandingan (merpati) lebih banyak daripada jumlah maksimum sarang, maka berdasarkan prinsip sarang merpati, setidaknya ada dua pertandingan (merpati) yang harus menempati sarang yang sama, yaitu dimainkan oleh dua peserta yang berbeda namun dengan jumlah pertandingan yang sama.
Kesimpulan:
Dengan demikian, kita telah membuktikan bahwa dalam turnamen catur dengan 10 peserta, pasti ada minimal dua peserta yang bermain dengan jumlah pertandingan yang sama.