Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas prinsip pigeonhole dalam Matematika Diskrit, di mana jika k plus satu objek ditempatkan pada k kotak, maka minimal satu kotak akan berisi dua atau lebih objek. Prinsip ini dapat digunakan untuk membuktikan berbagai situasi, seperti ketika mencocokkan elemen himpunan A dan B, atau menemukan orang dengan tanggal lahir yang sama dalam sebuah pertemuan. Prinsip pigeonhole juga dapat digeneralisasi, misalnya untuk memastikan ada minimal 9 orang yang lahir pada bulan yang sama dari 100 orang. Dalam konteks kelas Matematika Diskrit, minimal 25 plus 1 mahasiswa diperlukan untuk memastikan ada paling tidak 6 mahasiswa yang menerima nilai yang sama.

Kali ini kita akan bahas mengenai prinsip pigeonhole.

Jadi prinsip pigeonhole atau prinsip kandang burung darah itu idenya memang dari kandang burung darah.

Zaman dahulu kala itu kandang burung darah itu kayak rumah-rumahan terdiri dari beberapa tingkat, ada beberapa lubang.

Yang menemukan ide itu memperhatikan bahwa kadang-kadang dalam satu tempat atau ada lubang tempat burung darah itu tinggal,

itu ada yang kadang-kadang kosong, kadang-kadang ada yang lebih dari satu burung darah berada di dalam satu kotak.

Nah prinsip itu kemudian diformalisasi jadilah teorema yang kita sebut sebagai prinsip pigeonhole.

Bunyinya adalah jika k plus satu atau lebih objek ditempatkan pada k kotak,

maka ada setidaknya satu kotak yang mengandung dua atau lebih objek.

Jadi kalau kita punya objek yang lebih banyak dari tempat yang disediakan,

maka dapat dipastikan bahwa paling tidak ada satu kotak yang mengandung lebih dari satu objek, gitu ya prinsipnya.

Sekarang kalau kita lihat dari idenya itu mungkin bisa kita bayangkan,

jadi kalau misalnya kita punya ada beberapa tempat,

itu kalau misalnya kita punya tiga tempat atau tiga kotak,

terus kita punya ada lima objek yang mau kita masukkan di kotak-kotak tersebut.

Tidak ada jaminan bahwa ada kotak yang kosong,

tapi sudah pasti ada jaminan karena yang mau ditempatkan objeknya lima, tempatnya itu ada tiga,

berarti ada satu kotak yang diisi lebih dari satu objek.

Buktinya itu kita buktikan dengan metode yang kita sebut sebagai kontrapositif,

jadi kita andaikan tidak ada satu pun kotak yang berisi dua atau lebih objek,

maka jumlah total objek paling banyak adalah k, karena kita cuma punya k kotak.

Padahal kita kan punya k plus satu, sehingga hal ini adalah atau mengakibatkan kontradiksi,

karena banyaknya objek itu k plus satu tidak mungkin ditaruh tepat di k kotak,

sehingga teorema pigeonhole itu terbukti.

Jadi ini ide yang sederhana, buktinya juga sederhana,

tapi nanti kita bisa lihat dari contoh-contohnya bisa dipakai untuk menjelaskan berbagai hal.

Misalnya kita bisa lihat salah satu akibatnya dari prinsip pigeonhole itu adalah

kalau kita punya fungsi dari himpunan k plus satu atau lebih elemen kehimpunan dengan elemen k,

jadi fungsi itu biasanya kan kita tulis dari himpunan A kehimpunan B.

Kalau himpunan A itu punya k plus satu elemen,

jadi kita punya A1, A2 sampai AK plus satu,

kemudian di B itu hanya punya k elemen, jadi kita punya B1, B2 sampai BK,

maka kita tidak mungkin mendefinisikan fungsi satu-satu dengan posisi atau kondisi A dan B yang seperti ini.

Jadi pasti ada dua elemen di A yang dipasangkan hanya ke satu B,

sehingga itu menyalahi atau tidak memenuhi fungsi satu-satu atau sifat satu-satu.

Nah kemudian contoh berikutnya lagi yang mungkin sederhana,

misalnya kita punya ada pertemuan yang hadir ada 367 orang.

Kalau kita iseng tanya tanggal lahirnya itu untuk masing-masing pesertanya itu,

paling tidak ada yang punya ulang tahun yang sama,

jadi tanggal lahir yang sama, karena kita dalam satu tahun hanya punya 365 hari,

dan di sini kita punya 367 orang, ini kecuali tahun kabisat,

sehingga pasti ada satu orang yang tanggal lahirnya sama dengan teman yang lain atau orang yang lain.

Contoh lainnya lagi, misalnya berapa banyak mahasiswa pada sebuah kelas,

untuk menjamin paling tidak ada dua orang yang menerima nilai yang sama pada ujian akhir,

jika skala nilai ujian akhir adalah 0 sampai 100.

Jadi kalau ini sebetulnya tidak ada gunanya secara praktis,

tapi ini hanya sebagai contoh kalau nilainya 0 sampai 100,

maka kalau dia ingin ada yang nilainya sama berapapun antara 0 sampai 100,

maka harus ada 102 mahasiswa paling tidak,

karena nilai yang tersedia adalah 101, jadi kalau ada yang sama berarti ada 102 mahasiswa.

Ada minimal dua orang yang mempunyai nilai yang sama,

misalnya dia dua-duanya dapat 100, kemudian ada nggak yang dapat 90?

Kita nggak ada jaminannya dengan prinsip pigeonhole,

tapi prinsip pigeonhole cuma mengatakan bahwa ada dua mahasiswa yang nilainya sama.

Tidak menjamin bahwa di setiap nilai itu pasti ada mahasiswa yang mendapatkan nilai tersebut,

jadi tidak ada jaminan bahwa mahasiswa tersebut ada yang nilainya 0,

ada yang nilainya 100, itu tidak bisa dijamin oleh prinsip pigeonhole.

Kemudian prinsip pigeonhole ini bisa digeneralisasi,

jadi kalau kita punya n objek yang akan ditempatkan pada k kotak,

maka paling tidak ada satu kotak berisi n per k pakai ceiling objek,

jadi supaya kan itu bilangannya harus bilangan bulat,

Jadi contohnya misalnya dari antara 100 orang,

paling tidak terdapat 9 orang yang lahir pada bulan yang sama.

Kita tahu bahwa bulan dalam satu tahun itu 12,

maka kita akan punya 100 bagi 12 itu pecahan,

artinya bilangan bulat yang lebih tinggi daripada pecahan tersebut,

jadi paling tidak ada 9 orang yang lahir pada bulan yang sama.

Bisa 10 enggak? Bisa, ada kemungkinan bisa,

tapi paling tidak, jadi minimal ada 9 orang yang lahir pada bulan yang sama,

contoh dari mahasiswa yang punya nilai 0 sampai 100,

itu berapa mahasiswa yang ada supaya dia bisa punya nilai yang sama,

di sini berapa jumlah mahasiswa yang diperlukan pada kelas matematik diskret,

untuk memastikan bahwa terdapat paling tidak 6 menerima nilai yang sama,

jadi tidak ada A- B+, seperti yang ada di beberapa universitas.

Untuk kasus ini, maka kita menghitung n per k dengan seling tadi,

kita dapat 6, dan k itu nanti sama dengan 5,

maka minimal kita harus punya n nya itu 25 plus 1,

maka nanti akan ada 5 mahasiswa yang mempunyai nilai yang sama,

pokoknya di sini minimalnya itu 25 tambah 1,