TUGAS MAKALAH
MATEMATIKA DISKRIT
“PRINSIP SARANG MERPATI
DAN PELUANG DISKRIT”
DISUSUN
OLEH :
KELAS
A
NAMA NPM
1.
IRSAN
(14
221
003)
2.
SUKMA
DAMAYANTI (14
221
010)
3.
NASIA (14
221
015)
4.
KIKNAWATI (14
221
021)
5.
WA
ODE IRMA RAHMAWATI (14
221
027)
6.
MUHAMMAD ALIFUDI AKIB (14
221
037)
PROGRAM STUDI
PENDIDIKAN MATEMATIKA
UNIVERSITAS
DAYANU IKHSANUDDIN BAUBAU
2016
KATA
PENGANTAR
Puji
dan syukur senantiasa penyusun panjatkan atas kehadirat Allah SWT sebagai
pencipta dan pemelihara alam semesta, karena atas limpahan rahmat dan
hidayah-Nya penyusun dapat menyelesaikan penulisan makalah mata kuliah Matematika
Diskrit yang berjudul “Prinsip Sarang
Merpati dan Peluang Diskrit” yang dimaksudkan agar para pembaca lebih memahami
dan memperluas ilmu tentang kombinatorial dan peluang.
Penyusun juga mengucapkan terima kasih kepada dosen
pembimbing Ibu Artati Iriana,S.Si.,M.Si yang telah membimbing dan membantu
dalam penyelesaian makalah ini. Harapan penyusun, semoga makalah ini dapat
bermanfaat dengan baik, memberi konstribusi sebagaimana mestinya di masa
mendatang.
Dalam penulisan makalah ini, penyusun menyadari masih
banyak kekurangan dan kelemahan, baik mengenai materi maupun sistematika
penulisan. Oleh karena itu dengan segala kerendahan hati, penyusun mengharapkan
kritik dan saran yang membangun demi kesempurnaan pengetahuan di masa depan.
Baubau, 02 Mei 2016
Penyusun
DAFTAR
ISI
KATA PENGANTAR.......................................................................................................... ii
DAFTAR ISI........................................................................................................................ .. iii
BAB I PENDAHULUAN
1. Latar
Belakang.................................................................................................................. .. 1
2. Rumusan
Masalah............................................................................................................. .. 1
3. Tujuan
.............................................................................................................................. .. 1
BAB II PEMBAHASAN
1. Prinsip
Sarang Merpati...................................................................................................... .. 2
2. Peluang
Diskrit.................................................................................................................... 16
BAB III PENUTUP
1. Kesimpulan.......................................................................................................................... 37
2. Saran.................................................................................................................................... 37
DAFTAR ISI........................................................................................................................ .. 38
BAB
I
PENDAHULUAN
1.
Latar
Belakang
Matematika diskrit
adalah salah satu ilmu yang memiliki banyak kegunaan dalam berbagai bidang ilmu
lainnya. Matematika diskrit merupakan cabang matematika yang mempelajari
tentang obyek-obyek diskrit. Diskrit itu sendiri adalah sejumlah berhingga
elemen yang berbeda atau elemen-elemen yang tidak bersambungan. Dimana data
diskrit merupakan data yang satuannya selalu bulat dalam bilangan asli dan
tidak berbentuk pecahan. Contoh dari data diskrit misalnya manusia, pohon, bola
dan lain-lain. Berikut ini adalah beberapa alasan pentingnya mempelajari matematika
diskrit antara lain :
1. Landasan
berbagai bidang ilmu matematika : logika, teori bilangan, aljabar linier dan abstrak,kombinatorial,
teori graft, teori peluang (diskrit).
2. Landasan
ilmu komputer : struktur data, algoritma, teori database, bahasa formal, teori
automata, teori compiler, sistem operasi, dan pengamanan komputer (computer
security).
3. Mempelajari
latar belakang matematis yang diperlukan untuk memecahkan masalah dalam riset
operasi (optimasi diskrit), kimia, ilmu-ilmu teknik, biologi, telekomunikasi,
dan sebagainya.
Dari
alasan-alasan di atas, jelaslah bahwa matematika diskrit memiliki jangkauan
yang luas dalam berbagai bidang ilmu. Dalam makalah ini akan dibahas secara
terperinci mengenai prinsip sarang merpati dan peluang diskrit. Pada umumnya prinsip Pigeonhole merupakan salah satu teknik pembuktian yang sederhana dan efektif. Selain
itu, prinsip ini merupakan salah satu alat kombinatorial yang berguna dalam menghitung
objek dengan properti tertentu. Sedangkan
antara kombinatorial dan teori peluang sebenarnya terkait erat. Peluang
didasarkan pada suatu percobaan seperti pelemparan uang logam, pelemparan dadu,
penarikan kartu dan lain-lain.
2.
Rumusan
Masalah
1.
Bagaimanakah prinsip
sarang merpati ?
2.
Bagaimanakah peluang
diskrit ?
3.
Tujuan
1.
Untuk mengetahui
prinsip sarang burung merpati.
2.
Untuk mengetahui
peluang diskrit.
BAB
II
PEMBAHASAN
PEMBAHASAN
1.
PRINSIP
SARANG MERPATI
Pigeonhole
Principle atau Prinsip Sarang Merpati pertama kali dinyatakan oleh seorang ahli
matematika dari Jerman yang bernama Johann Peter Gustav Lejeune Dirichlet pada
tahun 1834, sehingga prinsip ini juga dikenal dengan istilah Prinsip Kotak
Dirichlet (Dirichlet Drawer Principle), karena Dirichlet sering menggunakan
prinsip ini dalam pekerjaannya.
Misalkan
kita mempunyai kandang burung merpati (pigeon) yang memiliki pintu masuk berupa
lubang-lubang (hole). Satu lubang berarti satu sarang. Setiap sarang biasanya
ditempati oleh seekor burung merpati. Misalkan merpati ada 16 ekor sedangkan
kandang hanya 14 buah sarang. Prinsip sarang merpati (pigeonhole principle)
menyatakan bahwa paling sedikit terdapat satu sarang yang ditempati oleh dua
ekor merpati.
Teorema I (Prinsip
Pigeonhole Bentuk Pertama) :
Prinsip Sarang Merpati (Pigeon Hole
Principle) menyatakan jika (n + 1) atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit
terdapat satu kotak yang berisi dua atau lebih objek. Atau jika
ada n sarang dan (n + 1) merpati, maka paling tidak ada 1 sarang yang ditempati
lebih dari 1 merpati.
Bukti
:
Misalkan
tidak ada kotak yang berisi lebih dari dua objek. Maka, total jumlah objek
paling banyak adalah n. Ini
kontradiksi, karena jumlah objek paling sedikit n + 1. Atau
Misal
jika n merpati ditempatkan pada m sarang merpati, dimana n > m, maka
terdapat sarang merpati yang memuat paling sedikit dua merpati. Untuk
membuktikan pernyataan Prinsip Pigeonhole ini, kita gunakan kontradiksi.
Misalkan kesimpulan dari pernyataan tersebut salah, sehingga setiap sarang
merpati memuat paling banyak satu merpati. Karena ada m sarang 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 :
Pada saat pembentukan tugas kelompok yang dibagi
menjadi enam kelompok, tujuh mahasiswa tidak masuk kuliah sehingga mereka belum
terdaftar dalam kelompok yang sudah dibagi. Tunjukkan bahwa paling sedikit ada
dua mahasiswa yang bergabung dalam satu kelompok !
Penyelesaian
:
Kita
asumsikan tujuh mahasiswa tersebut dengan merpati dan enam kelompok sebagai rsarang
merpati. Berdasarkan prinsip pigeonhole bentuk pertama terdapat sarang merpati
yang memuat paling sedikit dua merpati. Dengan demikian terdapat suatu kelompok
yang memuat paling sedikit dua mahasiswa.
Contoh 2
:
Seorang kyai di sebuah desa yang selalu diminta
untuk memberikan nama bayi yang lahir, menyiapkan nama depan Muhammad, Akhmad,
Abdul dan nama belakang Hadi, Akbar, Gofur bagi bayi yang lahir dalam suatu
bulan tertentu. Pada bulan tersebut terdapat sebelas bayi yang lahir di desa
itu. Tunjukkan bahwa paling sedikit ada dua bayi yang mempunyai nama yang sama
dengan asumsi bahwa kyai tersebut selalu memberikan nama depan dan belakang !
Penyelesaian :
Terdapat
sembilan kombinasi nama depan dan belakang yang mungkin untuk sebelas bayi yang
lahir pada bulan tersebut. Kita asumsikan sebelas bayi tersebut dengan merpati
dan sembilan nama sebagai sarang merpati. Berdasarkan prinsip pigeonhole bentuk
pertama terdapat sarang merpati yang
memuat paling sedikit dua merpati. Dengan demikian terdapat kombinasi nama yang
dipakai paling sedikit dua bayi.
Contoh 3 :
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 4 :
Buktikan bahwa di Jakarta paling tidak ada 10 orang dengan jumlah helai
rambut yang sama di kepalanya !
Penyelesaian :
Rata-rata
manusia memiliki 150.000 helai rambut di kepalanya. Dengan begitu sangat aman
mengasumsikan rambut di kepala manusia paling banyak berjumlah satu juta helai.
Sementara itu, penduduk Jakarta
berjumlah lebih dari 9 juta ( sekitar 9,5 juta lebih tepatnya). Dengan begitu,
andaikan ada 9 orang penduduk Jakarta tanpa rambut, 9 orang berikutnya hanya
punya 1 helai rambut, 9 orang berikutnya lagi hanya punya 2 helai, dan
seterusnya sampai 9 orang penduduk Jakarta yang punya satu juta helai rambut di
kepalanya, karena penduduk Jakarta berjumlah lebih dari 9 juta, orang ke
9.000.010 akan memiliki jumlah rambut antara 0 sampai sejuta. Dengan demikian
memastikan ada paling tidak 10 orang dengan jumlah helai rambut yang sama di
kepala.
Contoh 5 :
Dalam kemasan permen dengan
5 pilihan rasa, kita hanya perlu mengambil 6 permen. Tunjukkan bahwa paling
tidak ada dua permen dengan rasa yang sama !
Penyelesaian :
Ini salah
satu contoh paling sederhana dari penerapan prinsip sarang merpati. Misalkan kelima
pilihan rasa permen tersebut adalah stroberi, jeruk, apel, anggur, dan kiwi.
Setelah mengambil lima permen dari dalam kemasan, ternyata semua rasanya
berbeda. Karena hanya ada lima pilihan rasa, permen keenam yang kita ambil
pasti rasanya sama dengan salah satu permen yang sudah kita ambil sebelumnya.
Disini rasa berperan sebagai sarang dan permen yang kita ambil sebagai
merpatinya.
Contoh 6
:
Buktikan
bahwa pada setiap 13 orang terdapat setidaknya 2 orang yang memiliki bulan
lahir yang sama !
Penyelesaian
:
Satu
tahun pasti ada 12 bulan, dengan menggunakan prinsip sarang burung, asumsikan
sarang burung adalah bulan-bulan itu (Januari-Desember), dan orang-orang itu
adalah burungnya, pasti ada setidaknya satu sarang yang bermuatan lebih dari
satu burung. Sehingga terbukti bahwa pada setiap 13 orang terdapat setidaknya 2
orang yang memiliki bulan lahir sama.
Contoh
7 :
Dari
27 orang mahasiswa, buktikan bahwa paling sedikit terdapat 2 orang yang namanya
diawali dengan huruf yang sama !
Penyelesaian
:
Dari 27 orang mahasiswa,
paling sedikit terdapat dua orang yang namanya diawali dengan huruf yang sama,
karena hanya ada 26 huruf dalam alfhabet. Jika kita menganggap 27 huruf awal
dari nama-nama mahasiswa sebagai merpati dan 26 huruf alphabet sebagai 26 buah sarang
merpati, kita bisa menetapkan pemasangan
27 huruf awal nama ke 26 huruf alphabet seperti halnya pemasangan merpati ke
sarang merpati. Menurut prinsip sarang merpati, beberapa huruf awal alphabet
dipasangkan dengan paling sedikit dua huruf awal nama mahasiswa.
Contoh 9 :
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 !
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
10 :
Buktikan
bahwa jika terdapat 11 kali jabat tangan antara 2 orang pada 5 orang, terdapat
jabat tangan antara 2 orang yang sama dan dilakukan dua kali !
Penyelesaian
:
Ada
5 orang kita misalkan anggap a, b, c, d, dan e.
a
dapat berjabat dengan b, c, d, e. Kemudian b berjabat dengan c, d, e. Lalu c
dapat berjabat dengan d, e. Dan terakhir d dapat berjabat dengan e. Total
terjadi jabatan tangan adalah 10, karena telah terjadi 11 jabatan tangan
tentunya terbukti ada salah seorang yang melakukan jabatan dengan orang yang sama
sebanyak 2 kali.
Contoh
11 :
Di
dalam sebuah kotak terdapat 4 pasang kaos kaki berwarna hitam, putih, biru, dan
merah. Berapa banyak kaos kaki yang harus diambil dari dalam kotak tanpa
melihat terlebih dahulu, agar dapat dipastikan akan didapat sepasang kaos kaki
yang berwarna sama.
Penyelesaian
:
Agar didapat sepasang kaos kaki yang berwarna sama dari 4 warna kaos
kaki, maka kita harus mengambil minimal 5 buah kaos kaki, sehingga dapat
dipastikan akan didapat sepasang kaos kaki yang berwarna sama, sesuai dengan
pigeonhole principle. Seandainya kita hanya mengambil 4 buah kaos kaki, ada
kemungkinan yang kita dapat masing-masing 1 kaos kaki berwarna hitam, putih,
biru, dan merah, sehingga kita tidak mendapatkan sepasang kaos kaki yang
berwarna sama.
Prinsip
Pigeonhole ini bisa kita nyatakan dalam bentuk lain seperti berikut ini.
Teorema II (Prinsip Pigeonhole Bentuk
Kedua) :
Jika f merupakan sebuah fungsi dari suatu himpunan
terhingga X ke suatu himpunan terhingga Y dan |X| > |Y |, maka f(
) = f(
) untuk beberapa
,
X, dimana
.
Bukti :
Untuk
membuktikan Prinsip Pigeonhole bentuk kedua ini kita bisa menggunakan Prinsip
Pigeonhole bentuk pertama dengan mengasumsikan X sebagai himpunan
merpati dan Y sebagai himpunan sarang merpati. Selanjutkan kita
memasangkan merpati x ke sarang merpati f(x). Karena
jumlah merpati lebih banyak dari sarangnya, maka terdapat paling sedikit dua merpati,
dimana
,
X yang dipasangkan
ke sarang merpati yang sama, yaitu f(
) = f(
) untuk beberapa
,
X, dimana
.
Prinsip ini dapat
diilustrasikan oleh gambar di bawah ini, misalkan untuk X = 5 dan Y = 4.
Ilustrasi
(a) menunjukkan beberapa burung yang hinggap di sangkarnya, sedangkan ilustrasi
(b) menunjukkan korespondensi antara burung dengan sangkarnya. Dari gambar (b)
di atas, kita dapat menyatakan prinsip sarang burung dengan bahasa yang lebih
matematis, seperti berikut : Suatu fungsi dari himpunan berhingga ke himpunan
berhingga yang lebih kecil, tidak dapat satu-satu : Paling sedikit ada dua
anggota domain yang memiliki bayangan yang sama di kodomain. Sehingga, diagram
panah yang menggambarkan fungsi dari himpunan berhingga ke himpunan berhingga
yang lebih kecil harus memiliki paling sedikit dua anak panah dari domain yang
menunjuk anggota yang sama di kodomain. Pada ilustrasi di atas, kita dapat
melihat bahwa anak panah dari burung 4 dan 5 menunjuk sangkar burung 4.
Contoh
1 :
Ketua Program Studi Pendidikan Matematika akan
membuat kode matakuliah untuk matakuliah-matakuliah bidang studi matematika
dengan cara menambahkan tiga angka pada huruf KPM. Terdapat 51 matakuliah yang
harus diberi kode dan tiga angka yang harus ditambahkan pada huruf KPM 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 :
,
, ...,
Jika
angka-angka diatas digunakan bersama-sama dengan :
+1,
, ...,
+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
,
, ...,
dan
+1,
, ...,
+1 semuanya
berbeda. Sehingga kita mempunyai :
=
+ 1
Dengan
demikian kode
berurutan dengan
kode
.
Contoh 2 :
Dari seluruh penduduk DKI Jakarta tahun 2013, apakah paling sedikit ada
dua orang yang memiliki jumlah rambut yang sama di kepala mereka?
Pembahasan :
Jawabannya adalah iya. Pada contoh ini, yang menjadi burung adalah
penduduk DKI Jakarta dan yang menjadi sarang burung adalah semua kemungkinan
dari jumlah rambut pada setiap kepala penduduk Jakarta. Misalkan populasi dari
penduduk DKI Jakarta adalah P.
Berdasarkan data dari Bappeda Jakarta tahun 2013, jumlah penduduk Jakarta adalah sekitar 9 juta jiwa. Selain itu, seperti kita ketahui
jumlah rambut yang dapat tumbuh di kepala manusia paling banyak adalah 300.000.
Didefinisikan suatu fungsi H
dari himpunan semua penduduk DKI Jakarta {x1, x2,
x3, …, xp} ke himpunan {0, 1, 2, 3,
…, 300.000}, seperti berikut :
Karena jumlah penduduk DKI
Jakarta lebih banyak daripada kemungkinan jumlah rambut pada kepala manusia,
maka H bukan merupakan fungsi
satu-satu. Sehingga, paling sedikit ada dua anak panah yang menunjuk pada
bilangan yang sama. Atau dengan kata lain, paling sedikit ada dua penduduk DKI
Jakarta yang memiliki jumlah rambut yang sama.
Contoh 3 :
Misalkan A = {1, 2, 3,
4, 5, 6, 7, 8}. Jika lima bilangan bulat diambil dari A, apakah paling sedikit ada sepasang bilangan bulat yang
jumlahnya 9?
Pembahasan :
Jawabannya adalah iya. Kita partisi himpunan A menjadi 4 himpunan yang saling lepas, yaitu {1, 8}, {2, 7},
{3, 6}, dan {4, 5}. Perhatikan bahwa setiap bilangan bulat di A muncul tepat satu kali di empat
himpunan bagian tersebut dan jumlah bilangan bulat pada masing-masing himpunan
bagian tersebut adalah 9. Sehingga, jika 5 bilangan bulat diambil dari himpunan
A maka, dengan menggunakan prinsip sangkar burung, dua diantaranya berasal dari
himpunan bagian yang sama. Hal tersebut menyebabkan jumlah dua bilangan bulat
tersebut adalah 9. Untuk melihat dengan cermat bagaimana penerapan prinsip
sangkar burung pada soal ini, kita misalkan lima bilangan bulat yang diambil
(sebut saja a1, a2, a3, a4, dan a5) sebagai burung dan
himpunan-himpunan bagian sebagai sangkarnya. Fungsi P dari himpunan burung ke himpunan sarang burung didefinisikan
dengan memisalkan P(ai) adalah himpunan bagian
yang memuat ai.
Fungsi P terdefinisi
dengan baik karena setiap bilangan bulat ai
di domain, ai
termuat oleh satu himpunan bagian (karena gabungan himpunan-himpunan bagian
tersebut adalah A) dan ai tidak termuat oleh
lebih dari satu himpunan bagian A
(karena himpunan-himpunan bagian tersebut saling lepas).
Karena jumlah burung lebih banyak daripada sangkarnya, maka paling
sedikit ada dua burung yang singgah di satu sangkar. Sehingga dua bilangan
bulat yang berbeda akan dipasangkan kepada himpunan bagian yang sama. Hal ini
akan menyebabkan bahwa dua bilangan bulat tersebut adalah dua anggota yang
berbeda dari himpunan bagian, sehingga jumlahnya adalah 9. Secara lebih formal,
dengan menggunakan prinsip sangkar burung, karena P bukan fungsi satu-satu, maka ada bilangan bulat ai dan aj sedemikian sehingga,
Tetapi
kemudian, berdasarkan definisi P,
ai dan aj dimiliki oleh himpunan
bagian yang sama. Karena jumlah semua anggota dari masing-masing himpunan
bagian adalah 9, maka ai + aj = 9.
Prinsip Pigeonhole Bentuk Kedua ini
dapat dinyatakan ke dalam bentuk yang lebih umum seperti penyataan berikut ini.
Prinsip sarang merpati dapat dirampatkan (generalized) sedemikian sehingga
jumlah objek dapat merupakan kelipatan jumlah kotak. Misalkan jika terdapat 20
sarang merpati dan 41 ekor merpati, maka terdapat satu buah sarang merpati ynag
berisi lebih dari 2 ekor merpati. Atau dengan kata lain jumlah dari objek yang
melebihi dari jumlah kotak yang tersedia dapat dinyatakan sebagai berikut.
Teorema III (Prinsip Pigeonhole Bentuk
Ketiga) :
Jika M objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang
berisi minimal [M/n] objek.
Bukti
:
Pernyataan
di atas menyatakan bahwa jika n buah kotak akan diisi dengan M = nk + 1 objek, yang dalam hal ini
k adalah bilangan bulat positif
maka paling sedikit terdapat 1 kotak yang berisi minimal k + 1 objek.
Contoh 1 :
Terdapat
banyak bola merah, bola putih, dan bola hijau di dalam sebuah kotak . Berapa
paling sedikit jumlah bola yang harus diambil dari dalam kotak sehingga 3
pasang bola yang setiap pasangnya berwarna sama terambil ?
Penyelesaian :
Tiga pasang bola yang setiap pasang
berwarna sama = jumlah 6 buah bola. N = 3 (jumlah warna). Kita perlu mengambil
paling sedikit M buah bola untuk memastikan bahwa [M/3] = 6 (bola
mengandung setiap pasang bola yang berwarna sama). M = 3 . 5 + 1 = 16. Jika
kita hanya mengambil 15 bola, maka kemungkinan hanya terambil 2 macam bola yang
berwarna sama. Jadi jumlah 16 buah bola adalah jumlah minimal yang perlu kita
ambil dari kotak untuk memastikan bahwa ada 3 pasang bola yang setiap pasang
berwarna sama terambil.
Contoh 2
:
Jika terdapat 20 sarang merpati dan 41 ekor merpati.
Berapakah banyak sarang yang ditempati 2 ekor merpati
?
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 akan
ada merpati yang menempati 1 sarang yang sudah
ditempati merpati lain.
Contoh 3
:
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?
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.
Contoh 4
:
Jika anda menghadiri 6 kuliah dalam
selang waktu Senin sampai Jumat. Berapakah maksimal anda mengambil pelajaran dalam
sehari?
Penyelesaian
:
Senin – 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.
Contoh 5
:
Di dalam kelas
dengan 60 mahasiswa. Berapakan banyak mahasiswa yang akan mendapat nilai yang sama?
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).
Prinsip sarang merpati, jika diterapkan
dengan baik, akan memberikan hanya objek-objek yang ada, dan bukan
memberitahukan bagaimana mencari objek tersebut dan berapa banyak. Pada masalah
sarang burung merpati, prinsip ini tidak memberitahukan di sarang merpati mana
yang berisi lebih dari dua ekor merpati. Walaupun kelihatan sederhana,
prinsip ini terbukti sangat berguna dalam menyelesaikan masalah kombinatorial.
§
APLIKASI PRINSIP PIGEONHOLE
Walaupun prinsip pigeonhole merupakan
prinsip yang sangat sederhana, prinsip ini mempunyai banyak aplikasi antara
lain :
A. 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).
B. 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.
C. 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.
D. Aplikasi Pada Permasalahan Geometri
Prinsip
pigeonhole dapat digunakan
dalam pembuktian masalah-masalah geometri. Contoh permasalahan yang diberikan
adalah sebagai berikut: buktikan bahwa dua dari enam titik dalam persegi
panjang 3x4 berjarak tidak lebih dari
. Solusinya adalah dengan membuat pembagian
dari persegi panjang 3x4 tersebut seperti gambar berikut :
Gambar Pembagian
persegi panjang sebagai solusi dari permasalahan geometri.
Kita
dapat melihat bahwa pembagian persegi panjang 3x4 dengan garis merah membuat
persegi panjang terbagi menjadi lima bagian. Berdasarkan prinsip pigeonhole, bila enam titik
ditempatkan pada persegi panjang tersebut, maka ada satu bagian yang setidaknya
memuat dua titik. Maka dari itu, terbukti bahwa dua dari enam titik dalam
persegi panjang 3x4 berjarak tidak lebih dari
, karena jarak maksimum dalam satu bagian pada
persegi panjang tersebut adalah
.
Aplikasi prinsip pigeonhole pada permasalahan geometri sangat banyak, salah
satunya dengan menggunakan perluasan prinsip pigeonhole dengan jumlah burung merpati tak hingga. Namun
demikian, makalah ini tidak membahas lebih lanjut mengenai aplikasi dari
perluasan prinsip pigeonhole tersebut.
D. 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♣.
E. 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.
2.
PELUANG DISKRIT
§
SEJARAH PELUANG
Peluang dikenal juga dengan teori probabilitas.
Teori peluang awalnya diinspirasi oleh masalah perjudian. Awalnya dilakukan
oleh matematikawan dan fisikawan Itali yang bernama Girolamo Cardano
(1501-1576). Cardano merupakan seorang penjudi pada waktu itu. Walaupun judi
berpengaruh buruk terhadap keluarganya, namun judi juga memacunya untuk
mempelajari peluang. Dalam bukunya yang berjudul Liber de Ludo Aleae (Book on
Games of Changes) pada tahun 1565, Cardano banyak membahas konsep dasar dari peluang
yang berisi tentang masalah perjudian. Cardano merupakan salah seorang dari
bapak probability. Pada tahun 1654, seorang penjudi lainnya yang bernama
Chevalier de Mere menemukan sistem perjudian. Ketika Chevalier kalah dalam
berjudi dia meminta temannya Blaise Pascal (1623- 1662) untuk menganalisis
sistem perjudiannya. Pascal menemukan bahwa sistem yang dipunyai oleh Chevalier
akan mengakibatkan peluang dia kalah 51 %. Pascal kemudian menjadi tertarik
dengan peluang, dan mulailah dia mempelajari masalah perjudian. Dia
mendiskusikannya dengan matematikawan terkenal yang lain yaitu Pierre de Fermat
(1601-1665). Mereka berdiskusi pada tahun 1654 antara bulan Juni dan Oktober
melalui 7 buah surat yang ditulis oleh Blaise Pascal dan Pierre de Fermat yang
membentuk asal kejadian dari konsep peluang. Pascal bekerjasama dengan Fermat
menyelesaikan soal-soal yang diberikan oleh Chevalier de Mere..
Sehingga
antara kombinatorial dan teori peluang (probability) sebenarnya terkait erat.
Teori peluang banyak menggunakan konsep-konsep di dalam kombinatorial. Teori peluang (probabilitas) ini dikembangkan pertama kali
pada abad ke-17 oleh ahli matematika Perancis bernama Blaise Pascal. Dari hasil
studi ini Pascal menemukan berbagai macam properti koefisien binomial. Pada abad ke-18
dikembangkan oleh ahli matematika dari Perancis Laplace. Aplikasi kombinatorial
dan teori peluang saat ini meluas ke berbagai bidang ilmu lain maupun dalam
kehidupan dunia nyata. Sayangnya, kedua bidang ini lahir dari tempat
yang kurang patut, yaitu dari arena judi (gambling games). Salah satu
kasusnya adalah menghitung peluang kemunculan nomor lotre.
§ PENGANTAR
MENUJU PEMAHAMAN KONSEP PROBABILITAS(PELUANG)
Banyak kejadian dalam
kehidupan sehari-hari yang sulit diketahui dengan pasti, apalagi kejadian di
masa yang akan datang. Begitu pula dalam suatu percobaan, kita tidak bisa
mengetahui dengan pasti hasil-hasil yang akan muncul, misalnya :
1. Pada
pelemparan sebuah uang logam, kita tidak tahu dengan pasti hasilnya, apakah
yang akan muncul sisi muka (sisi angka) atau sisi belakang (sisi gambar) dari
uang logam itu ;
2. Pada
pelemparan sebuah dadu, kita tidak tahu dengan pasti hasilnya, apakah yang akan
muncul muka dadu 1, 2, 3, 4, 5 atau 6 ;
3. Pada
penarikan sebuah kartu bridge dalam kotak yang berisi 52 kartu, kita juga tidak
tahu dengan pasti, apakah yang akan muncul kartu as, king, atau yang lainnya.
Meskipun
kejadian-kejadian tersebut tidak pasti, tetapi kita bisa melihat fakta-fakta
yang ada untuk menuju derajat kepastian atau derajat keyakinan bahwa sesuatu
akan terjadi. Bila suatu dadu dilemparkan dengan acak, tanpa rekayasa apa-apa,
maka ada derajat kepastian bahwa muka 1 dari dadu itu akan muncul.
Derajat/tingkat
kepastian atau keyakinan dari terjadinya suatu peristiwa dalam suatu percobaan tertentu
disebut probabilitas atau peluang. Suatu
peluang dilambangkan dengan P. Dengan demikian kita dapat menentukan
peluang terjadinya hujan, peluang munculnya muka 1 pada percobaan pelemparan
sebuah dadu, peluang munculnya kartu as pada penarikan kartu dari sekelompok
kartu bridge, dan seterusnya.
§ RUANG
SAMPEL DAN KEJADIAN
Perhatikan percobaan
mengenai pelemparan sebuah uang logam dan pelemparan sebuah dadu pada bagian
sebelumnya. Pada pelemparan sebuah uang logam, semuanya ada dua hasil yang
mungkin muncul. Yaitu muka = m atau belakang = b. Dua hasil yang mungkin muncul
ini dapat dihimpun menjadi S = {m,b}. Begitu pula pada pelemparan sebuah dadu,
semuanya ada 6 hasil yang mungkin muncul, yaitu muka 1, 2, 3, 4, 5, atau 6.
Seluruh hasil yang mungkin muncul ini dapat ditulis dalam suatu himpunan S =
{1,2,3,4,5,6}.
Himpunan dari semua hasil
yang mungkin muncul pada suatu percobaan disebut ruang sampel yang
dilambangkan dengan himpunan S, sedangkan anggota-anggota dari ruang sampel S
atau setiap hasil percobaan di dalam ruang sampel S disebut titik
sampel. Hasil-hasil percobaan tersebut bersifat saling terpisah.
Dikatakan saling terpisah karena dari seluruh ruang sampel, hanya satu titik
sampel yang muncul. Misalnya pada percobaan pelemparan dadu, hasil percobaan
yang muncul hanya salah satu dari 6 mata dadu, tidak mungkin muncul 2 atau
lebih mata dadu, atau tidak mungkin salah satu dari enam mata dadu tidak ada
yang muncul.
Misalkan ruang
sampel dilambangkan dengan S dan titik-titik sampelnya dilambangkan dengan
,
, . . . , maka :
S = {
,
, . . . ,
}
Menyatakan ruang sampel S yang terdiri dari titik-titik sampel
,
, . . . ,
dan seterusnya. Ruang sampel yang jumlah
anggotanya terbatas disebut ruang sampel diskrit. Peluang terjadinya sebuah
titik sampel disebut peluang diskrit dan disimbolkan dengan p(
).
Definisi 1 :
Misalkan
adalah sebuah titik sampel di dalam ruang sampel
S. Peluang bagi
adalah
ukuran kemungkinan terjadinya atau munculnya
diantara titik-titik sampel yang lain di dalam
S.
Titik sampel yang mempunyai peluang
lebih besar berarti kemungkinan terjadinya lebih besar pula, sedangkan titik
sampel yang peluangnya lebih kecil berarti kemungkinan terjadinya juga lebih
kecil.
§ Sifat-Sifat
Peluang Diskrit
Peluang
diskrit mempunyai sifat sebagai berikut :
1. 0 ≤ p(
) ≤ 1, adalah nilai peluang yaitu bilangan tidak negatif dan selalu lebih
kecil atau sama dengan 1.
2.
= 1, yaitu jumlah peluang semua
titik sampel di dalam ruang sampel S adalah 1.
Peluang
(probabilitas) P(E) = 1 artinya suatu kejadian yang pasti terjadi. Sedangkan
P(E) = 0 adalah suatu kejadian yang tidak mungkin atau mustahil terjadi.
Peluang dalam nilai ekstrim ini jarang terjadi, yang sering terjadi adalah
diantaranya.
§ PENDEKATAN
PERHITUNGAN PELUANG
Ada dua pendekatan dalam menghitung peluang
yaitu pendekatan yang bersifat objektif
(pendekatan klasik dan frekuensi relatif) dan subjektif. Pendekatan
objektif dibagi menjadi dua, yaitu :
1. Pendekatan
Klasik
Peluang dengan
pendekatan klasik didasarkan atas pengertian rangkaian peristiwa yang bersifat
eksklusif secara bersama-sama dan masing-maing-masing mempunyai kesempatan yang
sama untuk muncul. Menurut pendekatan klasik, terjadinya peristiwa E dinyatakan
sebagai rasio satu kejadian dari seluruh kejadian apabila setiap kejadian
mempunyai kesempatan yang sama. Bila kejadian E terjadi dalam m cara dari
seluruh n cara yang mungkin terjadi dan masing-masing n cara itu mempunyai
kesempatan atau kemungkinan yang sama untuk muncul maka pelung kejadian E yang
ditulis P(E) dirumuskan sebagai berikut :
P(E) =
Keterangan :
P(E)
= peluang
terjadinya kejadian E.
m = peristiwa
yang dimaksud.
n =
banyaknya peristiwa.
Contoh 1
:
Pada pelemparan uang logam
dimisalkan sisi pertama kita sebut muka = m dan sisi kedua kita sebut belakang
= b. Maka ada dua kejadian yang mungkin, yaitu kejadian munculnya muka m kita
sebut E = m atau kejadian munculnya sisi
belakang b kita sebut E = b. Oleh karena sisi uang logam terdiri atas dua sisi
(n = 2) dan kedua sisi itu mempunyai kesempatan yang sama untuk muncul maka
peluang munculnya kejadian E = {m} atau E = {b} adalah :
P(E) = P({m}) =
=
atau P(E) = P({b}) =
=
.
Lebih singkat ditulis P(E)
= P(m) =
atau P(E)
= P(b) =
.
Ingat
bahwa dalam pelemparan uang logam tersebut yang akan muncul salah satu
dari E = (m) atau E = (b).
Jadi, bila yang muncul E = (m), maka E = (b) tidak muncul, dan bila yang muncul
E = (b), maka yang tidak muncul adalah E = (m). Jadi, kita mempunyai kejadian
munculnya E = (m), sekaligus kejadian tidak munculnya E = (b).
Contoh 2
:
Pada pelemparan sebuah dadu. Muka dadu
ada 6 yaitu 1, 2, 3, 4, 5, dan 6. Semua muka dadu mempunyai kesempatan yang
sama untuk muncul. Yang akan muncul salah satu dari muka-muka dadu itu (m = 1)
yaitu muka 1, muka 2, muka 3, muka 4, muka 5, atau muka 6. Kita misalkan :
E = (1) bila muncul muka dadu 1,
E = (2) bila muncul muka dadu 2, dan
E = (3) bila muncul muka dadu 3 dan
seterusnya.
Maka peluang kejadian E adalah :
P(E)
= P(1) = P(2) = P(3) = P(4) = P(5) = P(6) =
=
Contoh 3
:
Hitunglah peluang memperoleh kartu hati
bila sebuah kartu diambil secara acak dari seperangkat kartu bridge yang
lengkap.
Penyelesaian :
Jumlah seluruh kartu : n = 52
Jumlah kartu hati : m = 13
Misalkan E = kejadian munculnya kartu
hati. Semua kartu hati mempunyai kemungkinan yang sama untuk muncul. Maka :
P(E)
=
Contoh 4
:
Hitunglah peluang terambilnya bola merah
bila sebuah bola diambil dari suatu kotak yang berisi 10 bola merah dan 10 bola
putih.
Penyelesaian :
Jumlah
seluruh bola : n = 20
Jumlah
bola merah : m = 10
Misalkan
E kejadian diperoleh bola merah. Maka diperoleh peluang E adalah :
P(E)
=
=
=
2.
Pendekatan dengan
Frekuensi Relatif
Perumusan konsep peluang dengan cara klasik mempunyai
kelemahan karena menuntut syarat semua hasil mempunyai kesempatan atau
kemungkinan yang sama untuk muncul. Pengertian ini mengaburkan adanya peluang
yang sama. Sehubungan dengan itu dikembangkan konsep peluang berdasarkan
statistik, yaitu dengan pendekatan empiris. Peluang empiris dari suatu kejadian
dirumuskan dengan memakai frekuensi relatif dari terjadinya suatu kejadian
dengan syarat banyaknya pengamatan atau banyaknya sampel n adalah sangat besar.
Dengan demikian, jika kejadian E terjadi sebanyak f kali dari keseluruhan
pengamatan sebanyak n, maka peluang kejadian E dirumuskan sebagai berikut :
P(E)
=
Dengan
:
f
= banyaknya muncul kejadian E.
n = banyaknya percobaan
yang dilakukan.
Contoh
1 :
Pada
suatu percobaan statistik, yaitu pada pelemparan sebuah dadu yang diulang
sebayak n = 1.000 kali, frekuensi
munculnya muka dadu X adalah seperti pada tabel berikut :
Muka
dadu (X)
|
1
|
2
|
3
|
4
|
5
|
6
|
Frekuensi
(f)
|
164
|
165
|
169
|
169
|
166
|
167
|
Bila
E menyatakan munculnya munculnya muka-muka dadu tersebut maka E = (1), (2),
(3), (4), (5), atau (6) sehingga peluang kejadian E untuk masing-masing
kemungkinan munculnya muka dadu tersebut adalah :
P(E) = P(1) =
,
P(E) = P(2) =
,
P(E) = P(3) =
,
P(E) = P(4) =
,
P(E) = P(5) =
,
P(E) = P(6) =
Contoh
2 :
Dari
100 mahaasiswa yang mengikuti ujian, distribusi frekuensi nilai mahasiswa adalah
seperti pada tabel berikut :
Nilai
(X)
|
45
|
55
|
65
|
75
|
85
|
95
|
Frekuensi
(f)
|
10
|
15
|
30
|
25
|
15
|
5
|
Maka peluang kejadian E mahasiswa
memperoleh nilai tersebut adalah :
P(E) = P(45) =
=
0,1
P(E) = P(55) =
=
0,15
P(E) = P(65) =
=
0,3
P(E) = P(75) =
=
0,25
P(E) = P(85) =
=
0,15
P(E)
= P(95) =
=
0,5
3.
Pendekatan Subjektif
Bila suatu kejadian hanya terjadi
beberapa kali saja, atau tidak ada informasi relatifnya, maka peluang
ditentukan berdasarkan kenyataan, perasaan, terkaan dan pengetahuan individu
atas suatu peristiwa. Pendugaan peluang yang tidak didasarkan bukti atau fakta
disebut peluang subjektif. Oleh sebab itu, karena sifatnya individu peluang suatu kejadian nilainya akan ditaksir
berbeda-beda dari individu satu dan individu lain meskipun informasi awal yang
diterima berkaitan peristiwa tersebut adalah sama. Pendekatan ini seringkali
dipakai oleh orang-orang yang cukup berpengalaman dalam bidangnya guna
meramalkan suatu kejadian. Menurut pendekatan subjektif, peluang diartikan
sebagai tingkat kepercayaan individu yang didasarkan pada peristiwa masa lalu
yang berupa terkaan saja.
Contoh 1
:
Seorang
direktur akan memilih seorang supervisor dari empat orang calon yang telah
lulus ujian saringan. Keempat calon tersebut sama pintar, sama lincah, dan
semuanya dapat dipercaya. Peluang tertinggi (kemungkinan diterima) menjadi
supervisor ditentukan secara subjektif oleh sang direktur.
§ KEJADIAN
(EVENT)
Kejadian atau event
disimbolkan E- adalah himpunan bagian dari ruang sampel. Misalkan pada
percobaan melempar dadu, kejadian munculnya angka ganjil adalah E = {1,3,5}, kejadian munculnya
angka 1 adalah E = {1}. Kejadian yang hanya mengandung satu titik sampel
disebut kejadian sederhana (simple
event) sedangkan kejadian yang
mengandung lebih dari satu titik sampel
disebut kejadian majemuk (compound event).
Perhatikan bahwa pada pelemparan sebuah
uang logam, S = {m,b} dan E = {m} sehingga E
S,
E merupakan himpunan bagian dari S. Begitu pula pada pelemparan sebuah dadu, s
= {1,2,3,4,5,6} dan E = {2}, sehingga E
S.
Pada E = {m}, anggota dari E adalah titik sampel. Suatu kejadian dikatakan terjadi jika salah satu
dari titik sampel di dalam kejadian tersebut terjadi.
Hubungan
antara kejadian E dengan ruang sampel S digambarkan sebagai berikut :
E
S
Ada
suatu keterkaitan antara kejadian E dan ruang sampel S pada konsep peluang
dengan himpunan bagian E dan himpunan semesta S pada teori himpunan, yaitu
sebagai berikut :
Konsep Peluang : Teori
Himpunan :
Ruang
sampel S
Himpunan
semesta S
Kejadian
E
Himpunan bagian E
Titik sampel
Anggota himpunan
Berdasarkan
kejadian E dan ruang sampel tersebut, maka perumusan konsep peluang tersebut
didefinisikan sebagai berikut :
Definisi
:
Peluang
kejadian E di dalam ruang sampel S adalah p(E) = |E|/|S|. Besarnya peluang
suatu peristiwa E terjadi, yang merupakan himpunan bagian dari ruang sampel S
dimana setiap peristiwa didalamnya memililki peluang yang sama untuk terjadi
diberikan oleh P(E) = |E|/|S|.
Dalam
definisi ini, baik E maupun S adalah himpunan, dengan demikian tanda |-|
melambangkan kardinalitas atau banyaknya anggota dari himpunan. Nilai peluang
mempunyai rentang dari 0 (berkaitan dengan peristiwa yang tidak pernah terjadi)
sampai 1 (untuk peristiwa yang pasti terjadi). Peluang kejadian E juga dapat
diartikan sebagai jumlah peluang semua titik sampel di dalam E. Jadi,
kita dapat menuliskan bahwa:
p(E) =
=
)
Contoh
1 :
Berapa peluang munculnya angka ganjil pada pelemparan dadu ?
Penyelesaian :
Pada percobaan melempar dadu, S = {1,2,3,4,5,6}. Kejadian
munculnya angka ganjil E = {1,3,5}. Disini |S| = 6 dan |E| = 3. Kejadian munculnya
angka ganjil adalah 3/6 = ½. Kita juga dapat menghitung peluang munculnya satu angka ganjil =
1/6, sehingga p(E) = 1/6 + 1/6 +1/6 = 3/6 = ½.
Contoh
2 :
Jumlah
cara mengambil 5 kartu sembarang dari 52 kartu = C(52, 5). Jumlah cara
mengambil satu jenis kartu dari 13 jenis yang ada = C(13,1). Jumlah cara
mengambil 4 kartu dari 4 kartu yang sejenis = C(4,4). Jumlah cara mengambil
satu kartu lagi dari 48 kartu yang
tersisa = C(48,1). Sehingga, peluang dari 5 kartu tersebut mengandung 4
kartu sejenis.
Contoh 3
:
Dua buah dadu dilemparkan secara bersamaan. Berapa peluang
munculnya angka-angka dadu dengan jumlah 8?
Penyelesaian :
Ruang
sampel dari dua buah dadu adalah sebagai berikut :
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
(1,1)
|
(1,2)
|
(1,3)
|
(1,4)
|
(1,5)
|
(1,6)
|
2
|
(2,1)
|
(2,2)
|
(2,3)
|
(2,4)
|
(2,5)
|
(2,6)
|
3
|
(3,1)
|
(3,2)
|
(3,3)
|
(3,4)
|
(3,5)
|
(3,6)
|
4
|
(4,1)
|
(4,2)
|
(4,3)
|
(4,4)
|
(4,5)
|
(4,6)
|
5
|
(5,1)
|
(5,2)
|
(5,3)
|
(5,4)
|
(5,5)
|
(5,6)
|
6
|
(6,1)
|
(6,2)
|
(6,3)
|
(6,4)
|
(6,5)
|
(6,6)
|
Ruang sampelnya sebanyak 36. Kejadian munculnya jumlah angka sama
dengan 8 adalah E = {(2,6),(3,5),(4,4),(5,3),(6,2)}.
Peluang munculnya jumlah angka sama dengan 8 adalah 5/36.
Contoh
4 :
Kartu
remi berjumlah 52. Keseluruhan kartu ini terdiri dari 13 jenis kartu, setiap
jenis terdiri dari 4 buah kartu. Tiga belas jenis kartu tersebut
adalah 2, 3, 4, 5, 6, 7, 8, 9, 10, joker, ratu, raja, as. Setiap pemain
remi mendapatkan 5 buah kartu.
Berapa peluang dari 5 kartu tersebut mengandung 4 kartu dari jenis yang
sama ?
Penyelesaian :
· Cara
mengambil 5 kartu sembarang dari 52 buah kartu = C(52,5) (Ini adalah
Ruang sampel).
· Cara
mengambil satu jenis kartu dari 13 jenis yang ada = C(13,1)
· Cara
mengambil 4 kartu dari 4 kartu yang sejenis = C(4,4)
· Cara
mengambil satu kartu lagi dari 48 kartu yang tersisa = C(48,1)
· Peluang
dari 5 kartu tersebut mengandung 4 kartu sejenis = C(13,1) x C(4,4) x
C(48,1) /C(52,5) = 0.00024
Contoh
5 :
Berapa
peluang dari 5 kartu mengandung 4
kartu
as ?
Penyelesaian :
Untuk
mengambil kartu as, maka hanya ada satu cara mengambil jenis kartu as.
Cara
mengambil 4 kartu dari 4 kartu as = C(4,4)
Cara
mengambil satu kartu lagi dari 48 kartu yang tersisa = C(48,1)
Cara
mengambil 5 kartu sembarang dari 52 buah kartu = C(52,5)
Peluang
dari 5 kartu tersebut mengandung 4 kartu as = 1 x C(4,4) x C(48,1) /
C(52,5) = 0.0000185.
Contoh
6 :
Diantara 100 bilangan bulat positif pertama,berapa peluang memilih
secara acak sebuah bilangan yang habis dibagi 3 atau 5 ?
Penyelesaian
:
Misalkan A menyatakan kejadian bilangan bulat yang habis dibagi 3
dan B menyatakan kejadian bilangan bulat yang habis dibagi 5. A ∩ B menyatakan kejadian bilangan bulat yang habis dibagi 3 dan 5 (
yaitu bilangan bulat yang habis dibagi KPK dari 3 dan 5 yaitu 15) maka A∪B menyatakan kejadian bilangan bulat yang habis dibagi 3 atau 5.
|A| =
= 33 ,
|B| =
= 20 ,
| A ∩ B | =
= 6
Maka untuk mendapatkan
P(A∪B)
= p(A) + p(B)– p(A∩B)
= 33/100 + 20/100 – 6/100
= 0,47
Jadi peluang bilangan yang habis dibagi 3 atau 5 adalah 0.45
§ Konsep
Teori Himpunan pada Peluang
Diskrit
Adapun
konsep-konsep teori himpunan pada peluang diskrit antara lain :
Misalkan
diketahui dua buah himpunan A dan B adalah dua kejadian didalam ruang sampel S.
1. Kejadian bahwa A dan B
terjadi sekaligus berarti munculnya salah satu
titik sampel di dalam himpunan A ∩ B. Peluang terjadinya kejadian A dan B adalah :
P (A ∩ B) =
)
2. Kejadian bahwa A atau B
atau keduanya terjadi berarti munculnya salah satu
titik sampel di A ∪ B. Peluang terjadinya kejadian A
atau B adalah :
P (A ∪ B) =
)
3. Kejadian
bahwa A terjadi tetapi B tidak terjadi berarti munculnya salah satu
titik sampel di A – B. Peluang
terjadinya
kejadian A tetapi B tidak adalah
:
P (A - B) =
)
4. Kejadian
salah satu dari A dan B terjadi namun bukan keduanya berarti sama
dengan munculnya salah satu
titik
sampel di A ⊕ B.
Peluang terjadinya salah satu dari
A
dan B namun bukan keduanya adalah
:
P (A ⊕ B) =
)
5. (Komplemen)
peluang bahwa kejadian Ā, komplemen dari kejadian A, terjadi adalah
P(
) = 1
P(A)
1. Kejadian Tidak Saling Lepas/Meniadakan :
Ingat kembali
pengetahuan mengenai teori himpunan bahwa bila A dan B dua himpunan dalam
himpunan semesta S, maka gabungan dari A dan B adalah himpunan baru yang
anggotanya terdiri atas anggota A atau anggota B atau anggota keduanya yang
ditulis :
A
B
= {x∈S
| x∈A
atau x∈B}
A
B
= {x∈S | x∈A dan x∈B}
Diagram
Venn untuk himpunan tersebut ditunjukkan oleh gambar berikut:
Banyaknya
anggota himpunan A
B
dan A
B
adalah :
n(A
∪ B) = n(A) + n(B) – n(A ∩ B)
n(A
∩ B) = n(A) + n(B) – n(A ∪ B)
Sejalan
dengan himpunan gabungan tersebut, karena ada keterkaitan antara teori himpunan
dengan teori peluang, maka kita dapat merumuskan kejadian gabungan A dan B,
yaitu kejadian A
B
pada ruang sampel S.
Bila A dan B kejadian semabrang pada
ruang sampel S, maka kejadian gabungan A dan B ditulis A
B
dan A
B
adalah kumpulan semua titik sampel yang ada pada A atau B atau kedua-duanya.
Kejadian A
B
disebut kejadian majemuk. Demikian halnya, kejadian A ∩ B , yaitu kumpulan
titik sampel yang ada pada A dan B juga disebut kejadian majemuk.
Peluang
kejadian A
B
dan A
B
dirumuskan sebagai berikut :
P(A
∪ B) = P(A) + P(B) – P(A ∩ B)
P(A
∩ B) = P(A) + P(B) – P(A ∪ B)
Penjelasan
lahirnya rumus tersebut adalah sebagai berikut :
Dengan menggunakan prinsip inklusi-eksklusi
kita juga dapat memperlihatkan bahwa :
p(A
∪ B) = p(A) + p(B) – p(A ∩ B)
Bukti
: Prinsip inklusi-ekslusi untuk operasi gabungan dua buah himpunan menyatakan
Dalam
hal ini :
p(A
B) =
=
=
= p(A)
p(B)
p(A
B)
Contoh
1 :
Kita
ambil satu kartu secara acak dari satu set kartu bridge yang lengkap. Bila A =
kejadian terpilihnya kartu AS dan B = kejadian terpilihnya kartu wajik,
hitunglah P(A ∪ B) !
Penyelesaian
:
P(A) =
,
P(B) =
,
P(A ∩ B) =
(
kartu as wajik )
Maka
P(A
∪ B) = P(A) + P(B) – P(A ∩ B)
=
+
–
=
=
Contoh 2
:
Peluang
seorang mahasiswa lulus matematika diskrit adalah
dan peluang lulus kalkulus adalah
.
Bila peluang lulus sekurang-kurangnya satu mata kuliah diatas adalah
,
berapa peluang ia lulus kedua mata kuliah itu ?
Penyelesaian :
Misalkan
A
= kejadian lulus matematika diskrit.
B
= kejadian lulus kalkulus.
P(A)
=
,
P(B)
=
,
P(A
∪ B) =
P(A ∩ B) = P(A)
+ P(B) – P(A ∪ B)
=
+
–
=
Peluang kejadian majemuk A∪B sebagaimana rumus P(A ∪ B)
= P(A) + P(B) – P(A ∩ B) tersebut masih dapat
dikembangkan lebih lanjut menjadi peluang kejadian A, B, dan C yang ditulis
dengan A
B
C. Gambar dari kejadian tersebut
digambarkan sebagai berikut :
Peluang
kejadian majemuk A
B
C dirumuskan seabgai berikut :
P(A∪B)
= P(A)+P(B)+P(C)
P(A∩B)
P(A∩C)
P(B∩C)
P(A∩B∩C)
Penjelasan
lahirnya rumus ini dapat diperoleh dengan melakukan cara yang hampir sama
dengan penjelasan lahirnya rumus P(A ∪ B) = P(A) + P(B) – P(A ∩ B).
2. Kejadian Saling Lepas (Meniadakan) :
Bila A dan B dua kejadian sembarang pada
S dan berlaku A
B =
, maka A dan B dikatakan dua kejadian
saling lepas atau saling bertentangan atau saling pisah (mutually exclusive).
Dua kejadian A dan B dikatakan saling lepas artinya kejadian A dan B tidak
mungkin terjadi secara bersamaan. Dua kejadian saling lepas ditunjukkan pada
gambar berikut ini.
Bila
A dan B dua kejadiaan saling lepas, maka P(A
B)
= P (
) = 0, sehingga peluang kejadiaan A
B
dirumuskan sebagai berikut.
P(A
B)
= P(A) + P(B)
Contoh
1 :
Bila
A dan B dua kejadiannya saling lepas, dengan P(A) =0,3 dan P(B) =0,25, tentukan
P(A
B) !
Penyelesaian
:
Karena
A dan B saling lepas, maka berlaku:
P(A
B) =
P(A) + P(B)
= 0,3 + 0,25
=0,55
Contoh
2 :
Pada
pelemparan dua buah dadu. Tentukan peluang munculnya muka dua dadu dengan
jumlah 7 atau 11!
Penyelesaian
:
Misalkan
A
= kejadian munculnya jumlah 7.
B
= kejadian munculnya jumlah 11.
|
Dadu II
|
||||||
1
|
2
|
3
|
4
|
5
|
6
|
||
D
a
d
u
I
|
1
|
(1,1)
|
(1,2)
|
(1,3)
|
(1,4)
|
(1,5)
|
(1,6)
|
2
|
(2,1)
|
(2,2)
|
(2,3)
|
(2,4)
|
(2,5)
|
(2,6)
|
|
3
|
(3,1)
|
(3,2)
|
(3,3)
|
(3,4)
|
(3,5)
|
(3,6)
|
|
4
|
(4,1)
|
(4,2)
|
(4,3)
|
(4,4)
|
(4,5)
|
(4,6)
|
|
5
|
(5,1)
|
(5,2)
|
(5,3)
|
(5,4)
|
(5,5)
|
(5,6)
|
|
6
|
(6,1)
|
(6,2)
|
(6,3)
|
(6,4)
|
(6,5)
|
(6,6)
|
Diperoleh
:
A
= {(1,6), (2,5), (3,4), (4,3), (5,2),
(6,1)}
B = {(5,6), (6,5)}
Maka A
B
=
, berarti A dan B saling lepas.
P(A)
=
P(B) =
,
sehingga:
P(A
B) =P(A) + P(B) =
+
=
=
Dengan demikian dapat kita kembangkan
rumus peluang tiga kejadian A, B, dan C yang saling lepas,yaitu:
P(A
B
C) = P(A) + P(B) + P(C)
Secara
umum,
,
,
...,
adalah kejadian-kejadian yang saling lepas,
maka berlaku rumus peluang seperti berikut ini:
P(
....,
) = P(
) + P(
) + P(
) + ... + P(
) =
3. Dua
Kejadian Saling Bebas
Dalam percakapan sehari-hari, kita sering
mendengar kata-kata saling tidak mempengaruhi, independen, dan tidak ada
sangkut paut. Semua ungkapan tersebut pada intinya menyatakan bahwa terjadinya
kejadian yang satu tidak dipengaruhi oleh terjadinya kejadian yang lain. Dalam
konsep peluang dua kejadian seperti itu disebut dua kejadian saling bebas.
Dua kejadian A dan B dalam ruang sampel S
dikatakan saling bebas jika kejadian A tidak mempengaruhi kejadian B dan
sebaliknya kejadian B tidak mempengaruhi kejadian A. Jika A dan B dua kejadian
saling bebas, maka berlaku rumus :
P(A
B) = P(A).P(B)
Contoh
1 :
Bila
diketahui dua kejadian A dan B saling bebas dengan P(A) = 0,3 dan P(B) = 0,4.
Maka berlaku :
P(A
B) = P(A).P(B) = (0,3)(0,4) = 0,12
Contoh
2 :
Pada
pelemparan dua uang logam, apakah kejadian munculnya muka dari uang logam
pertama dan uang logam kedua saling bebas ?
Penyelesaian
:
Akal
sehat kita mengatakan seharusnya kejadian itu saling bebas. Sebab dalam
pelemparan dua uang logam secara sekaligus, muncul sisi apa saja pada uang
logam pertama tidak ada sangkut pautnya dangan muncul sisi apa saja dari uang
logam kedua. Atau dapat dikatakan, bila
uang logam pertama menghasilkan sisi muka, maka muncul sisi apa saja dari uang
logam kedua, muka atau belakang, tidak ada sangkut pautnya dangan muncul sisi
apa saja dari uang logam pertama. Penjelasan dengan konsep peluang adalah
sebagai berikut :
Perhatikan
tabel :
Hasil
yang mungkin muncul ditunjukkan pada tabel berikut ini :
|
Uang
logam II
|
||
M
|
B
|
||
Uang
logam I
|
m
|
(m,m)
|
(m,b)
|
b
|
(b,m)
|
(b,b)
|
Jadi ruang sampel S
adalah S = {(m,m), (m,b), (b,m), (b,b)}.
Misalkan
A
= kejadian munculnya muka (m) dari uang logam pertama.
B
= kejadian munculnya muka (m) dari uang logam kedua.
Maka
kejadian majemuk A
B menyatakan munculnya dua muka (m,m)
dari uang logam pertama dan uang logam kedua, sehingga :
A
= {m}, B = {m}, dan A
B = {(m,m)} dengan
P(A)
=
,
P(B) =
,
dan P(A
B) =
. Akan tetapi, juga berlaku :
P(A
B) =
=
.
=
P(A) . P(B)
Dengan
demikian, karena berlaku P(A
B) = P(A) . P(B), maka A dan B saling
bebas.
Contoh
3 :
Pada
pelemparan dua buah dadu, apakah kejadian munculnya muka X
3
dadu I dan kejadian munculnya muka Y
5
saling bebas ?
Penyelesian
:
|
Dadu II
|
||||||
1
|
2
|
3
|
4
|
5
|
6
|
||
D
a
d
u
I
|
1
|
(1,1)
|
(1,2)
|
(1,3)
|
(1,4)
|
(1,5)
|
(1,6)
|
2
|
(2,1)
|
(2,2)
|
(2,3)
|
(2,4)
|
(2,5)
|
(2,6)
|
|
3
|
(3,1)
|
(3,2)
|
(3,3)
|
(3,4)
|
(3,5)
|
(3,6)
|
|
4
|
(4,1)
|
(4,2)
|
(4,3)
|
(4,4)
|
(4,5)
|
(4,6)
|
|
5
|
(5,1)
|
(5,2)
|
(5,3)
|
(5,4)
|
(5,5)
|
(5,6)
|
|
6
|
(6,1)
|
(6,2)
|
(6,3)
|
(6,4)
|
(6,5)
|
(6,6)
|
A
= kejadian munculnya muka X
3
dadu I.
B
= kejadian munculnya muka Y
5
dadu II.
A
= {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,2), (2,3),
(2,4), (2,5), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6)}.
B
= {((5,1), (5,2), (5,3), (5,4), (5,5), (5,6), (6,1), (6,2), (6,3),
(6,4), (6,5), (6,6)}.
A
B = {(1,5), (2,5), (3,5), (1,6), (2,6), (3,6)}.
Maka
diperoleh :
P(A
B) = P(A) . P(B) = (
)(
) =
Jika
A, B, dan C adalah tiga kejadian saling bebas maka berlaku rumus peluang
kejadian A
B
C, yaitu sebagai berikut :
P(A
B
C) = P(A) . P(B) . P(C)
Secara
umum, bila
,
,
, ... ,
adalah kejadian-kejadian yang bebas, maka
berlaku :
P(
...
) = P(
) . P(
) . P(
) . ... . P(
)
Contoh
4
:
Pada
pelemparan tiga buah uang logam, tunjukkanlah bahwa munculnya muka dari tiga
uang logam saling bebas.
Penyelesaian
:
Bila
tiga uang logam dilemparkan, maka ruang sampelnya adalah :
S
= {(m,m,m), (m,m,b), (m,b,m), (b,m,m), (b,m,b), (b,b,m), (m,b,b), (b,b,b)}.
Misalkan
A
= kejadian munculnya muka pada uang logam 1.
B
= kejadian munculnya muka pada uang logam 2.
C
= kejadian munculnya muka pada uang logam 3.
Maka
diperoleh :
A
= {(m,m,m), (m,m,b), (m,b,m), (m,b,b)}
B
= {(m,m,m), (m,m,b), (b,m,m), (b,m,b)}
C
= {(m,m,m), (m,b,m), (b,m,m), (b,b,m)}
Maka
berlaku :
P(A
B
C) = P(A) . P(B) . P(C) =
.
.
=
Jadi
A, B, C adalah kejadian saling bebas.
4. Dua Kejadian Saling Komplementer
Dalam teori himpunan disebutkan bahwa
bila himpunan A
S,
maka komplemen A ditulis
atau
adalah himpunan yang anggotanya S tetapi
bukan anggota A atau :
=
{x∈S | x
A}
Gambar
himpunan A,
dalam himpunan semesta ditunjukkan pada gambar
berikut :
Kiranya
jelas bahwa A
=
atau A
S.
Sejalan dengan pengetahuan itu, kita
mengenal dua kejadian saling komplementer A dan
dalam ruang sampel S. Kejadian
adalah kumpulan titik sampel yang merupakan
titik sampel S tetapi bukan merupakan titik sampel A. Kiranya jelas bahwa A dan
merupakan dua kejadian saling lepas karena A
=
. Bila A dan
dua kejadian dalam S saling komplementer, maka
berlaku rurmus peluang sebagai berikut :
P(
) = 1
P(A)
Penjelasan
lahirnya rumus tersebut diuraikan sebagai berikut :
Perhatikan
karena A
=
atau A
S, maka :
P(A
) = 0 dan P(A
) = P(S) = 1
Akan
tetapi,
P(A
) =
P(A) + P(
)
P(A
)
1 =
P(A) + P(
)
0
P(
) = 1
P(A)
Atau
Persamaan
tersebut dapat dibuktikan sebagai berikut :
P(
) =
= 1
= 1
P(A)
Contoh 1
:
Bila
A dan
dua kejadian saling komplementer, dengan P(A)
= 0,6. Maka P(
) = 1- P(A) = 1
0,6 = 0,4.
Contoh
2 :
Pada
pelemparan dadu, jika A adalah kejadian munculnya muka dadu yang sama,
hitunglah peluang munculnya muka dadu yang tidak sama.
Penyelesaian
:
Perhatikan
tabel berikut :
|
Dadu II
|
||||||
1
|
2
|
3
|
4
|
5
|
6
|
||
D
a
d
u
I
|
1
|
(1,1)
|
(1,2)
|
(1,3)
|
(1,4)
|
(1,5)
|
(1,6)
|
2
|
(2,1)
|
(2,2)
|
(2,3)
|
(2,4)
|
(2,5)
|
(2,6)
|
|
3
|
(3,1)
|
(3,2)
|
(3,3)
|
(3,4)
|
(3,5)
|
(3,6)
|
|
4
|
(4,1)
|
(4,2)
|
(4,3)
|
(4,4)
|
(4,5)
|
(4,6)
|
|
5
|
(5,1)
|
(5,2)
|
(5,3)
|
(5,4)
|
(5,5)
|
(5,6)
|
|
6
|
(6,1)
|
(6,2)
|
(6,3)
|
(6,4)
|
(6,5)
|
(6,6)
|
A = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)}. Maka P(A) =
=
=kejadian munculnya muka dadu yang tidak sama.
Maka A dan
adalah dua kejadian yang saling komplementer
sehingga berlaku :
P(
) = 1- P(A) = 1
=
.
Contoh
3 :
Dari 8 bit (atau 1 byte) yang dibangkitkan secara acak, berapa
peluang bahwa byte tersebut tidak dimulai dengan ‘11’ ?
Penyelesaian
:
Misalkan A menyatakan kejadian bahwa byte yang dibangkitkan
dimulai dengan ‘11’. Maka ~A menyatakan kejadian bahwa byte yang dibangkitkan
tidak dimulai dengan ‘11’. Jumlah byte yang dimulai dengan ‘11’ adalah 26 = 64
buah karena 2 posisi pertama sudah diisi dengan ‘11’ sehingga kita cukup
mengisi 6 posisi bit lainnya. Jadi |A| = 64. Ruang sampel S adalah himpunan semua
bit yang panjangnya 8 disini |S| = 28 =256. Maka peluang byte yang dibangkitkan
tidak dimulai dengan ‘11’ adalah :
P(~A) = 1 – p(A) = 1 – 64/256 = 192 / 256
BAB III
PENUTUP
1.
Kesimpulan
Prinsip Sarang Merpati
terbagi menjadi 3 bentuk. Prinsip pigeonhole bentuk pertama menyatakan jika (n + 1) atau lebih objek ditempatkan
di dalam n buah kotak, maka
paling sedikit terdapat satu kotak yang berisi dua atau lebih objek. Bentuk
kedua menyatakan jika f merupakan
sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y dan
|X| > |Y |, maka f(
) = f(
) untuk beberapa
,
X, dimana
. Bentuk
ketiga menyatakan jika M objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang
berisi minimal [M/n] objek. 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.
Teori peluang banyak
menggunakan konsep-konsep di dalam kombinatorial.
Sayangnya, kedua bidang ini lahir dari tempat yang kurang patut,
yaitu dari arena judi (gambling games). Peluang adalah derajat/tingkat
kepastian atau keyakinan dari terjadinya suatu peristiwa dalam suatu percobaan
tertentu dengan kisaran nilai peluang 0 ≤ p(
) ≤ 1. Ada dua pendekatan dalam menghitung
peluang yaitu pendekatan yang bersifat objektif
(pendekatan klasik dan frekuensi relatif) dan subjektif. Konsep-konsep pada
teori himpunan dapat diterapkan pada peluang diskrit dengan rumus : P (A ∩ B) =
); P (A ∪ B) =
); P (A - B) =
); P (A ⊕ B) =
); P(
) = 1
P(A).
2.
Saran
Sebaiknya kita lebih
mendalami dan memahami mengenai prinsip sarang merpati dan peluang diskrit. Dengan
mempelajari prinsip sarang merpati kita dapat menyelesaikan permasalahan
relasi, geometri, trik kartu kombinatorik, dan lain-lain dengan lebih mudah.
Dan dengan mempelajari peluang, kita dapat membuat dan mengetahui hasil dari
suatu kejadian.
DAFTAR
PUSTAKA