CONTOH DAN PENERAPAN MASALAH PENGHITUNGAN DALAM MATEMATIKA DISKRIT

MAKALAH MATEMATIKA DISKRIT

CONTOH DAN PENERAPAN MASALAH PENGHITUNGAN

Disusun Oleh:

1.    FAKHRUR RAZI                                                    (170311861614)

2.    RIRIN NOVIA ASTUTI                                         (170311861527)

3.    NURSIDRATI                                                          (170311861597)

Dosen Pengampu: Prof. Drs. Purwanto, P.hd.

UNIVESITAS NEGERI MALANG

PASCASARJANA

PROGRAM STUDI PENDIDIKAN MATEMATIKA

OKTOBER 2017

DAFTAR ISI

 

COVER.................................................................................................................... i

DAFTAR ISI........................................................................................................... ii

A.    Pendahuluan....................................................................................................... 1

B.     Contoh dan Penerapan Masalah Penghitungan ................................................. 2

1.    Permainan Kartu...................................................................................... 2

2.    Koefisien Multinomial............................................................................. 3

3.    Strategi Penyususunan............................................................................. 5

4.    Penyelesaian Bilangan Bulat pada Persamaan......................................... 6

5.    Pengontrolan Kualitas............................................................................. 7

6.    Paradoks De Mere................................................................................... 7

DAFTAR PUSTAKA.............................................................................................. 8

A.  PENDAHULUAN

Banyak masalah penghitungan dapat diatasi dengan menemukan sejumlah cara terpilih yang ditentukan jumlah elemen yang berbeda dari satu set ukuran tertentu, dimana urutan elemen ini diperhatikan. Banyak masalah penghitungan lainnya dapat dipecahkan dengan menemukan sejumlah cara untuk memilih sejumlah elemen tertentu dari satu set ukuran tertentu, di mana urutan elemen dipilih tidak diperhatikan. Misalnya, dalam berapa banyak cara kita bisa memilih dua siswa dari lima siswa untuk bermain bulu tangkis berpasangan? Berapa banyak panitia tiga orang siswa bisa dibentuk dari kelompok empat siswa? Pada bagian ini kita akan menjelaskan tentang contoh dan aplikasi tentang masalah penghitungan.

B. CONTOH DAN PENERAPAN MASALAH PENGHITUNGAN

1.      Contoh 2.4.1 Permainan Kartu

Soal: Berapa peluang pengambilan secara acak dari 5 kartu  full house (3 kartu senilai dan 2 kartu senilai dengan nilai yang lain) dari seperangkat kartu bridge?

Penyelesaian:

Ada 52 kartu diambil 5 sehingga ada C(52, 5) cara pengambilan. Kita menguraikannya menjadi 4 langkah:

·         Pertama menentukan kartu kembar sehingga ada C(13,1) cara yakni 13 pasang diambil 1 pasang.

·         Kemudian ada C(4,3) cara pada pengambilan 3 kartu yang sama pada tiap pasangannya.

·         Untuk menentukan sepasang yang sama maka tinggal 12 pasang kartu di ambil 1 pasang sehingga ada C(12,1) cara.

·         Karena akan diambil 2 kartu,  maka setiap pasang mempunyai C(4,2) sehingga diperoleh peluang secara acak yaitu

Jadi, peluang pengambilan secara acak dari 5 kartu  full house (3 kartu senilai dan 2 kartu senilai dengan nilai yang lain) dari seperangkat kartu bridge adalah 0,0014

Soal: Di New York LOTTO 48^TM , seorang pemain memilih 6 angka berbeda dari angka 1- 48. Pada suatu malam akan diadakan undian dengan pengambilan 6 bola angka. Jika 6 angka dipilih, kemudian pemain itu menang pada putaran pertama. Jika tepat 5 angka dipilih  dari 6 angka terpilih sebelumnya maka pemain akan menang pada putran kedua. Berapa peluang pemain itu menang di putaran pertama? putaran kedua?

Penyelesaian:

·         Pengundian Pertama

Ada C(48,6) = 12.271.512 cara untuk memilih 6 angka yang berbeda. Pada pengundian pertama peluang seorang pemain menang/beruntung adalah .

·         Pengundian Kedua

Pada pengundian kedua 5 angka dipilih dari 6 angka tepilih sebelumnya maka masih ada C(6,5) dan 1 angka lagi dipih dari sisa 42 angka maka ada C(42, 1) cara setelah sebelumnya telah diambil 6 angka.  Sehingga diperoleh peluang pemain menang pada putaran kedua adalah

Jadi, peluang pemain itu menang di putaran pertama adalah  dan putaran kedua adalah

2.      Contoh 2.4.2 Koefisien Multinomial

Soal: Berapa cara yang dapat digunakan untuk mengubah kata “BOOK-KEEPER”?

Penyelesaian:

Untuk membentuk sebuah susunan, kita mempunyai 10 huruf yaitu 2 huruf O, 2 huruf K, 3 huruf E yang sama, 1 huruf B, 1 huruf P, dan 1 huruf R. Ada 6 langkah penyelesaian masalh ini:

·         Pertama pilih huruf O pada awal susunan sehingga ada C(10,2) cara,

·         Kita pilih K sehingga ada C(8,2) cara,

·         Pilih E sehingga ada C(6,3) cara.

·         Kemudian kita pilih B sehingga C(3,1)cara,

·         Lalu, pilih P ada C(2,1) cara dan,

·         Terakhir pilih P sehingga ada C(1,1)cara, sehingga diperoleh:

Bentuk akhir faktorial tidak memperhatikan dan mengetahui dimana letak huruf pada suatu susunan. Semuanya merupakan jumlah dari huruf yang tersusun pada setiap pemodelan/tipe. Misalkan pada bentuk yang lain (seperti huruf K diletakkan di awal) maka akan menghasilkan jawaban yang sama. Ini mengajak kita pada proposisi berikut:

Proposisi 2-10

Diberikan suatu n objek, r₁ objek kesatu, r₂ objek kedua, …, dan r_k objek ke-k, sehingga banyaknya cara untuk menyusun n objek adalah

Hal yang seperti ini dinamakan koefisien multinominal dan dinotasikan sebagai , C(n; r₁, r₂, …, r_k), atau P(n; r₁, r₂, …, r_k). Kita akan mendiskusikan koefisien binomial dan multinomial yang lebih jelas pada bagian berikutnya nanti.

Bukti. Kita mempunyai n tempat yang dapat digunakan untuk meletakkan semua objek. Kita akan membentuk susunan dengan k langkah. Pertama kita pilih tempat pertama untuk objek kesatu sehingga ada C(n,r₁) cara, kemudian tempat kedua (susunan kedua)kita pilih untuk objek kedua sehingga ada C(n - r₁, r₂) cara, dan seterusnya. Sehingga didapat persamaan:

Berdasarkan masalah di atas, koefisien multinominal juga muncul pada permasalahan distribusi (penyusunan).

Masalah: Pada tumpukan kartu bridge terdapat 52 kartu yang dibagikan sama rata kepada 4 pemain. Berapa banyak cara yang dapat digunakan untuk menyelesaikan permasalahan ini?

Penyelesaian: Ambil 13 kartu pada pemain pertama sehingga ada C(52,13) cara, pemain kedua juga mengambil 13 kartu sehingga ada C(39, 13) cara, dan begitu juga untuk pemain ketiga dan keempat. Sehingga diperoleh C(52,13) C(39, 13) C(26, 13) C(13, 13) =  ~ 5.36 x 10²⁸. Dengan keterangan ini, berapa peluang “perfect deal” yakni setiap pemain menerima semua warna dari jenis kartu. Berdasarkan gambaran kita, kejadian ini akan terjadi hanya sekali dari 5.36 x 10²⁸ cara yang ada. Jika terdapat 2 juta permainan bridge 4 pemain bermain bersama setiap detik maka perfect deal akan terjadi sekali pada setiap 8.5 milyar permainan.

3.      Contoh 2.4.3 Strategi Penyusunan

Permasalahan-permasalahan berikut dituliskan dengan menggambarkan beberapa ide:

Permasalahan:

(a) Berapa banyak cara yang dapat digunakan untuk menyusun kata dari kata GARDEN dengan huruf vokal disusun susuai urutan alfabetis?

(b) Berapa banyak cara yang dapat digunakan untuk menyusun kata dari kata GARDEN dengan huruf vokal disusun bersama?

Penyelesaian:

(a)  Ada 6 huruf yang akan menempati tempat yang berbeda. Kita akan membentuk sebagai sebuah penyusunan dengan 3 langkah.

·         Pertama kita pilih tempat untuk huruf vokal sehingga ada C(6,2) cara.

·         Kemudian kita masukan huruf vokal berdasarkan urutan alfabetisnya,ini berarti A berada di kiri dan E berada di kanannya.sehingga

·         Kita tambahkan semua huruf konsonan yaitu ada 4! cara. Berdasarkan hasil tersebut maka jawabannya adalah C(6,2) 4! = 360 cara

(b) Kita akan membentuk susunan dengan 2 langkah.

·         Pertama kita membuat semua kata yang huruf vokalnya digunakan bersamaan/berdekatan yaitu EA atau AE.

·         Kemudian kita susun 1  dari EA atau AE dengan 4 huruf lainnya sehingga ada 5! bara. Berdasarkan langkah penyelesaian tersebut maka diperoleh 2 x 5! = 240 cara.

Permasalahan:

Berapa banyak cara yang dapat digunakan untuk menyusun huruf BANDANAS dengan syarat tidak ada huruf vokal yang berurutan?

Penyelesaian:

Terkadang kita berfikir akan menjumlahkan semua cara sebelum kita menyusunnya.

Strategi: Kita mempunyai 3 huruf vokal dan 5 huruf konsonan. Kita namai 3 V dan 5 C. Pertama  kita perhatikan bahwa susunan kata yang akan disusun tidak ada huruf vokal yang berurutan. Kemudian kitasusun V dan C pada suatu kata.

Bentuk: Pada  langkah pertama kita akan menyusun V dan C dengan tidak ada V yang berurutan. Sehingga didaapat bentuk V … V … V dengan C selalu dan harusberada diantara huruf V,maka susunan tersebut menjadi V C V C V.

Selanjutnya kita letakkan 3 huruf C lainnya pada 4 tempat yang mungkin: berada di kiri dari V yang pertama, berada  diantara huruf V pertama dan kedua, berada diantara huruf V yang kedua dan ketiga, dan berada disebelah kanan huruf V yang ketiga. Ini sama artinya dengan meletakkan 3 huruf konsonan lainnya pada 4 tempat. Oleh karena itu langkah pertamayang kita kerjakan ada C(4-1 +3, 3) = 20 cara. Pada langkah kedua kita mengganti V dengan huruf vokal sehingga kitamemiliki 3 huruf A yang sama, dan tanpa memperhatikan mana A yang terlebih dahulu diletakkan sehingga ini hanya ada 1 cara. Akhirnya, kita mengganti C dengan huruf konsonan. Seperti contoh terakhir ini dapat diselesaikan dengan 5!/2! = 60 cara. dari hasil di atas maka penyelesaiannya adalah 20 x 60 = 1200 cara penyusunan.

4.      Contoh 2.4.4 Masalah Penyelesaian Bilangan Bulat pada Persamaan

Permasalahan:

Berapa banyak cara penyelesaian bilangan bulat dari X₁ + X₂ + X₃ = 10 dengan X_i ≥ 0?

Penyelesaian:
Misalkan X₁ =  X₂ = 0 maka X₃ = 10

Kita mempunyai 3 tempat, setiap tempat sebagai variabel dan kita susun kesepuluh angka yang mungkin yang dapat menentukan nilai dari variabel. Kemudian masalah ini sama dengan cara penyusunan 10 angka yang identik ke dalam 3 tempat yang berbeda setiap selnya / tempatnya dapat dinotasikan C(3-1+10,10) = 66.

Berikut 3 masalah yang ekuivalen:

1.    Jumlah cara yang dapat dipilih untuk memilih r objek dari n objek dengan cara pengulangan

2.    Jumlah cara untuk menyusun r objek pilihan yang identik ke dalam n tempat dengan berbeda setiap selnya

3.    Jumlah cara penyelesaian bilangan bulat dari X₁ + X₂ + X₃ = 10 dengan X_i ≥ 0
.

5.      Contoh 2.4.5 Pengontrolan Kualitas

Permasalahan:

Sebuah perusahaan menghasilkan 10000 kepingan computer. Dari pengambilan sampel 100 ditemukan 5 kepingan rusak. Berapa kemungkinan cara pengambilan jika terdapat k kepingan yang rusak?

Penyelesaian:

Ada C(10000,100) cara untuk memilih 100 kepingan dari kumpulan 10000 kepingan.  Kemudian kita temukan banyak cara untuk pengambilan 5 kepingan yang rusak. Kita dapat menyusun itu sebagai sampel ke dalam 2 langkah. Pertama kita pilih 5 kepingan yang rusak sehingga ada C(k, 5) cara. Selanjutnya kita pilih 95 kepingan yang baik sehingga ada C(10000 – k,95). Oleh karena itu, jumlah dari sampelnya adalah C(k, 5) C(10000 – k,95), dan kemungkinannya C(k, 5) C(10000 – k,95) / C(10000,100). Jika sampel kita benar-benar acak, maka kita dapat memperkirakan ada 500 kepingan yang rusak pada 10000 kepingan yang tersedia. k = 500 merupakan kemungkinan kerusakan terbanyak yang mungkin.

6.      Contoh 2.4.6 Paradoks De Mere

Permasalahan:

(a) Berapa peluang dari 4 kali lemparan dadu paling sedikit muncul sekali dadu bermata 6?

(b) Berapa peluang dari 24 kali lemparan dari sepasang dadu yang menghasilkan paling sedikit muncul 1 kali yang keduanya bermata 6?

Penyelesaian:

(a) Banyak cara dari pelemparan sebuah dadu sebanyak 4 kali adalah 6⁴, misalkan M adalah banyak cara pelemparan dadu paling sedikit muncul sekali dadu bermata 6. Misalkan N banyak cara pelemparan dan O adalah dadu yang munculbukan angka 6, maka N = M + O sehingga M = N – O. jadi O = 5⁴ sehingga M = 6⁴ – 5⁴. Sehingga peluangnya (6⁴ – 5⁴)/ 6⁴ = 0.5177…

(b) Dengan cara yang sama, peluang dari 24 kali lemparan dari sepasang dadu yang menghasilkan paling sedikit muncul 1 kali yang keduanya bermata 6 adalah (36²⁴ – 35²⁴)/36²⁴ = 0.4914

DAFTAR PUSTAKA

Townsend, R. 1987. Discrete Mathematics: Applied Combinatorics and Graph Theory. California: The Benjamin/Cummings Publishing Company

Rosen, H.K. 2007. Discrete Mathematics and Its Application. New York. The McGraw-Hill Companies.