The pigeone princile (prinsip sarang merpati)
The Pigeonhole Principle
(Prinsip Sarang Merpati)
Pigeonhole Principle atau Prinsip Rumah Merpati pertama kali dinyatakan oleh ahli matematika dari Jerman yang bernama Johann Peter Gustav Lejeune Dirichlet pada tahun 1834, sehingga prinsip ini juga dikenal dengan istilah Prinsip Laci Dirichlet (Dirichlet drawer principle).
Jika (k + 1) atau lebih obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau lebih obyek tersebut.
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-
contoh soal :
1)
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?
a.
4
b.
5
c.
3
d.
2
e. 1
e. 1
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.
2)
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 terambi?
a.
1
b.
2
c.
4
d.
3
e. 5
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.
3)
Jika terdapat 20 sarang
merpati dan 41 ekor merpati,Berapakah banyak sarang yang ditempati 2 ekor
merpati?
a.
4
b.
3
c.
2
d.
1
e. 5
e. 5
Penyelesaian
Maka akan terdapat satu
buah sarang yang berisi lebih dari 2 ekor merpati. Atau dengan menggunakan
rumus diperoleh paling sedikit [ 41 / 20 ] =
1 sisa bagi. Maka aka nada merpati yang menempati 1 sarang yang sudah
ditempati merpati lain.
4)
Dalam matakuliah
Matematika Diskrit diberikan tugas kelompok yang akan dibagi menjadi enam
kelompok. Jika terdapat 62 mahasiswa yang menempuh mata kuliah tersebut, berapakan
jumlah mahasiswa yang menjadi anggota suatu kelompok yang sama?
a.
10
b.
11
c.
12
d.
13
e. 14
e. 14
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 X yang dipasangkan dengan suatu anggota Y yang sama.
Dengan demikian terdapat paling sedikit ada 11 mahasiswa yang menjadi anggota
suatu kelompok yang sama.
5) Jika anda menghadiri 6 kuliah dalam selang waktu Senin sampai Jumat, Berapakah
maksimal anda mengambil pelajaran dalam sehari?
a. 2
b.
3
c.
4
d.
5
e. 1
e. 1
Penyelesaian:
Senen – Jumat = 5 hari.
Karena ada 6 mata pelajaran [ 6/5 ] = 2 maka haruslah
terdapat paling sedikit satu hari ketika anda menghadiri paling sedikit dua
kelas.
6)
Di dalam kelas dengan 60
mahasiswa,Berapakan banyak mahasiswa yang akan mendapat nilai yang sama?
a.
10
b. 12
c.
14
d.
16
e. 15
e. 15
Penyelesaian:
Nilai ( A,B, C, D, dan E)
Karena terdapat 60 mahasiswa [ 60/ 5] = 12 terdapat paling sedikit 12 mahasiswa akan
mendapat nilai yang sama (A, B, C, D, atau E).
TUGAS KEDUA :
1.
Sebutkan dan jelaskan aplikasi dari
Pigeon Hole?
Ø Prinsip pigeon hole bisa diterapkan dalam membuktikan bahwa ada paling tidak dua orang
penduduk di Bandung yang banyaknya rambut di kepala sama?
Jawab:
Jawab:
Sekilas, mungkin akan berusaha memanggil satu
demi satu penduduk di Bandung.. Kemudian, menyuruh mereka mencabuti setiap
rambut mereka untuk dihitung.. Namun, untuk membuktikannya, kamu tidak perlu
melakukan hal seperti itu. Gunakan prinsip rumah merpati di atas.
Perkirakan kemungkinan terburuk bahwa jumlah
rambut terlebat adalah 1000 helai rambut per inchi persegi. Kemudian asumsikan
kemungkinan terburuk bahwa rambut itu menutupi luas 1000 inchi persegi, maka
jumlah helai rambut terlebat manusia ada sekitar 1000.000 helai.. (Ini sudah
terburuk sekali).
Membandingkannya dengan jumlah penduduk
Bandung, yaitu sekitar 2.500.000 juta jiwa (tahun 2005, dan pasti
akan terus bertambah), maka jumlah 1000.000 sekitar 2.5 kali lebih kceil
dibandingkan jumlah penduduknya. Di kasus ini, kita dapat menganalogikan
2.500.000 sebagai jumlah merpati, dan 1000.000 sebagai jumlah rumah yang ada.
Maka, akan ada paling tidak 2 orang yang memiliki jumlah rambut yang sama.
Ø
Prinsip pigeon hole
bisa diterapkan dalam permainan kartu dengan 2 trik yaitu trik permainan kartu
kombinatorial. Contoh cara kerjanya adalah Pesulap akan menanyakan kepada
salah satu pengunjung untuk memilih secara acak lima kartu dari satu dek
kartu permainan. Pengunjung tidak menunjukkan kelima kartu ini pada pesulap ,
tapi menunjukkannya pada khalayak ramai lainnya.
Pengunjung-pengunjung yang lain akan memilih
empat kartu dan menunjukkannya pada sang pesulap. Maka pesulap itu akan dengan
cepat bisa menentukan kartu kelima kartu pertama yang ditunjukkan ke
pesulap adalah satu dai dua kartu yang sama ini. Kartu-kartu yang lain dengan
lambang yang sama yaitu kartu misteri tersebut yang harus ditebak oleh sang
pesulap. Lalu pengunjung-pengunjung lainnya menunjukkan bahwa kartu yang
disembunyikan tersebut mempunyai lambang yang sama dengan kartu pertama yang
ditunjukkan. Sedangkan nilai dari kartu misteri tersebut akan bisa didapatkan
dengan sedikit trik yaitu dengan ‘perhitungan lingkaran’ kecil.
2. Adakah keterkaitan antara Permutasi, Kombinasi, dan Pigeon
Hole. Jelaskan!
Metode permutasi dan
kombinasi sering digunakan dalam teori peluang (Probabilitas). Metode permutasi
dan kombinasi juga berperan dalam kombinatorika. Metode permutasi dan kombinasi
dapat digunakan untuk mencari bentuk umum dari permutasi dan kombinasi serta
metode kombinasi dapat diterapkan dalam teori binomial. Selain itu pada
matematika diskrit juga terdapat pokok bahasan tentang Prinsip Pigeonhole.
Prinsip ini seringkali memudahkan dalam membuktikan keberadaan suatu objek
dengan karakteristik tertentu dalam suatu tempat. dalam matematika diskrit yang
menginginkan jawaban keberadaaan suatu objek dalam tempat.
Berdasarkan Prinsip Pigeonhole
Jika terdapat m burung merpati menempati n kotak sarangnya, dan m>n, maka
sedikitnya satu kotak sarangnya akan dihuni dua atau lebih burung merpati,
dimana m dan n bilangan bulat positif Salah satu perhitungan dalam matematika
diskrit adalah permutasi dan kombinasi. Metode ini dapat menunjukkan banyaknya
suatu susunan yang dapat dibentuk dari suatu kumpulan objek yang berbeda dalam
suatu tempat, baik yang dipilih seluruhnya atau sebagian. Selain itu dapat
menunjukkan susunan objek yang identik. Dengan demikian, metode ini dapat
mencari objek dalam suatu tempat dan dapat menentukan banyaknya objek tersebut.
Metode perhitungan ini berguna dalam menyelesaikan masalah yang berhubungan
dengan Prinsip Pigeonhole.
Daftar pustaka
:
Dll.
Komentar
Posting Komentar