OLIMPIADE SAINS TERAPAN NASIONAL (OSTN)
SISWA SMK
TAHUN 2008

Untitled Document
 
OLIMPIADE SAINS TERAPAN NASIONAL (OSTN) SISWA SMK TAHUN 2008

Silabus Olimpiade

Matematika Teknik
Matematika Non Teknik
Fisika
Kimia
Biologi
Pemrograman ICT
 

 

11/18/2008

 

 

Kisi – Kisi Materi OSTN 2008

Matematika

 

 

 

 

Science Centre ITS


 

KOMBINATORIK

 Kombinatorik menitikberatkan studi tentang: pengaturan, pola, disain, penandaan, penja-dualan, koneksi dan konfigurasi. Analisis masalah kombinatorik berdasarkan atas pemahaman tentang: prinsip dasar penghitungan, permutasi dan kombinasi. Ada 3 masalah kombinatorik dasar, yaitu: masalah eksistensi (existence problem), masalah penghitungan (counting problem) dan masalah optimasi (optimization problem).

 

1 PRINSIP PENGHITUNGAN DASAR

Dalam analisis masalah kombinatorik dikenal dua prinsip penghitungan dasar (basic counting principles), yaitu: Kaidah Perkalian (Rule of Product) dan Kaidah Penjumlahan (Rule of Sum).

1.1 Kaidah Perkalian

 Kaidah perkalian mengatakan bahwa:

Misal dua percobaan dapat dilakukan. Jika satu percobaan memiliki m hasil yang mungkin dan percobaan yang lain memiliki n hasil yang mungkin, maka jika dua percobaan tersebut dilakukan bersamaan memiliki m.n hasil yang mungkin.

 Secara umum, dikatakan bahwa:

Misalkan r percobaan dapat dilakukan. Jika percobaan ke-i memiliki ni hasil yang mung-kin, 1ir, maka jika semua percobaan itu dilakukan bersamaan memiliki n1.n2.n3…..nr hasil yang mungkin.

 

Contoh-1:

Sebuah komite yang terdiri atas 2 orang masing-masing mewakili mahasiswa yunior dan senior akan dipilih. Jika calon dari yunior ada 6 orang dan calon dari senior ada 4 orang, maka ada 6 x 4 = 24 komite berbeda yang dapat dipilih..

 

Contoh-2:

Sebuah dadu dan sebuah uang logam dilempar secara bersamaan, maka hasil yang mungkin: - untuk dadu, mata dadu: 1, 2, 3, 4, 5, 6, maka ada 6 hasil yang mungkin,

- untuk uang logam, gambar dan angka, maka ada 2 hasil yang mungkin.

Sehingga dengan kaidah perkalian diperoleh 6 x 2 = 12 hasil yang mungkin.

 

1.2   Kaidah Penjumlahan

 

Kaidah penjumlahan mengatakan bahwa:

Misal dua percobaan dapat dilakukan. Jika satu percobaan memiliki m hasil yang mungkin dan percobaan yang lain memiliki n hasil yang mungkin, maka ada m+n hasil yang mungkin jika tepat satu percobaan dilakukan.

Secara umum, dikatakan bahwa:

Misalkan r percobaan dapat dilakukan. Jika percobaan ke-i memiliki ni hasil yang mungkin, maka ada n1+n2+n3+…+nr hasil yang mungkin jika tepat satu percobaan dilakukan.

 

Contoh-3:

Sebuah bola diambil sebuah mangkuk yang berisi 4 bola merah dan sebuah kaleng yang berisi 6 bola putih yang masing-masing bernomor, maka hasil yang mungkin adalah: untuk mangkuk ada 4 hasil dan untuk kaleng ada 6 hasil sehingga dengan kaidah penjumlahan hasil yang mungkin ada 4 + 6 = 10.

 

Contoh-4:.

Sebuah program komputer memiliki valid input berupa string huruf atau string angka dengan panjang 4. Berapa banyak valid input program tersebut yang mungkin?

 

Jawaban:

- Jika huruf atau angka dalam sebuah string boleh sama, maka:

String huruf ada sebanyak : 26 . 26 . 26. .26 = (26)4 = 456976

String angka ada sebanyak: 10 . 10 . 10 . 10 = (10)4 = 10000

Sehingga dengan kaidah penjumlahan, maka banyak valid string adalah:

456976 + 10000 = 466976

 

- Jika huruf atau angka dalam sebuah string tidak boleh sama, maka:

String huruf ada sebanyak : 26 . 25 . 24 . 23 = 358800

String angka ada sebanyak: 10 . 9 . 8 . 7 = 5840

Sehingga dengan kaidah penjumlahan, maka banyak valid string adalah:

358800 + 5840 = 364640

 

 

 

2. PERMUTASI

Definisi: (fakultet/faktorial)

Untuk sembarang bilangan bulat n0, n faktorial yang ditulis n!, didefinisikan sebagai:

0! = 1,

n! = (n) (n-1) (n-2) ….. (3) (2) (1)

 

Sehingga, 10! = 10.9.8.7.6.5.4.3.2.1 = 3628800

 

 

Untuk mengatur 3 huruf : a, b dan c secara berurutan, maka hasil yang mungkin adalah : abc, acb, bac, bca, cab, dan cba. Masing-masing urutan ini disebut “permutasi” dari 3 obyek berbeda yaitu: a, b dan c. Jadi banyaknya permutasi dari 3 obyek berbeda ada 6.

 

Misal, diberikan n obyek berbeda. Banyaknya permutasi n obyek tersebut dapat dihitung sebagai berikut:

- untuk mengisi posisi urutan pertama ada n cara berbeda,

- untuk mengisi posisi urutan kedua ada n-1 cara berbeda,

- untuk mengisi posisi urutan ketiga ada n-2 cara berbeda,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- untuk mengisi posisi urutan ke-r ada n-(r-1) cara berbeda,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- untuk mengisi posisi urutan ke-n ada n-(n-1)=1 cara berbeda.

Sehingga dengan kaidah perkalian diperoleh banyaknya permutasi adalah

(n) (n-1) (n-2) (n-3) … (3) (2) (1) = n !

Secara umum, dikatakan bahwa:

Banyaknya permutasi dari n obyek berbeda adalah n!

 

Contoh-5:

Sebanyak 6 orang akan membeli tiket tanda masuk sebuah pertunjukkan secara bersa-maan. Jika hanya tersedia sebuah loket pembelian tiket, maka berapa konfigurasi antrian yang mungkin dapat terjadi.

Jawaban:

Karena ada 6 orang maka dalam antrian terdapat 6 posisi berurutan. Untuk mengisi posisi antrian urutan pertama sampai keenam berturut-turut ada: 6, 5, 4, 3, 2, 1 cara. Sehingga dengan kaidah perkalian diperoleh banyaknya kofigurasi antrian adalah 6.5.4.3.2.1 = 6! = 720.

 

Contoh-6.

Profesor Amir memiliki koleksi buku yang terdiri atas: 5 buku Matematika, 4 buku Statistika, 3 buku Fisika dan 2 buku Kimia, diatur berjajar dalam sebuah rak buku sehingga buku yang memiliki subyek sama berkumpul. Tentukan ada berapa pola aturan yang mungkin?

 

Jawaban: . .

-          Untuk mengatur kelompok buku Matematika ada 5! pola aturan,

-          Untuk mengatur kelompok buku Statistika ada 4! pola aturan,

-          Untuk mengatur kelompok buku Fisika ada 3! pola aturan,

-          Untuk mengatur kelompok buku Kimia ada 2! pola aturan , dan

-          Untuk mengatur subyek buku ada 4! pola aturan.

Sehingga dengan kaidah perkalian diperoleh (5!) (4!) (3!) (2!) (4!) pola aturan berbeda yang mungkin.

 

Contoh-7:

Tentukan ada berapa cara untuk menyusun berjajar huruf-huruf yang terdapat dalam sebuah kata “PEPPER”!

Jawaban:

Jika 3 huruf P dan 2 huruf E dapat dibedakan, maka ada sebanyak 6! cara berbeda yang mungkin. Akan tetapi jika 3 huruf P dan 2 huruf E tidak dapat dibedakan, maka 3! susunan huruf P dikalikan 2! susunan huruf E hanya diwakili salah satu saja. Sehingga banyaknya susunan yang mungkin ada = = = 60.

 

Secara umum, dikatakan bahwa:

 

Banyaknya permutasi dari n obyek dengan n1 obyek sama, n2 obyek sama, …, nr obyek sama, dengan n1 + n2 + n3 + … + nr n, adalah

 

Contoh-8:

Sebanyak 9 bola: 4 bola berwarna merah, 3 bola berwarna putih, dan 2 bola berwarna biru dimasukkan kedalam sebuah tabung kaca. Tentukan ada berapa pola warna susunan bola yang mungkin!

 

Jawaban:

Karena 4 bola merah, 3 bola putih dan 2 bola biru tak dapat dibedakan, maka terdapat sebanyak = = = 1260 pola warna.

 

Teorema-2.1: Permutasi

Banyaknya permutasi r obyek yang diambil dari n obyek berbeda adalah

nr =

 

Bukti:

Setiap permutasi r obyek memuat r posisi berurutan. Untuk mengisi posisi pertama sampai posisi ke-r secara berurutan dapat dilakukan dengan : n, n-1, n-2, n-3, …, n-(r-1) cara. Sehingga untuk mengisi r posisi urutan sekaligus diperlukan:

 

(n)(n-1)(n-2)(n-3)…(n-(r-1)) =

=

 

Contoh-9:

Ada berapa cara untuk memilih seorang pemenang pertama, seorang pemenang kedua dan seorang pemenang ketiga dari sebuah kontes yang diikuti oleh 100 kontestan?

Jawaban:

Masalah ini identik dengan mendapatkan permutasi 3 obyek yang diambil dari 100 obyek berbeda. Jadi ada sebanyak 100 P 3 == (100).(99).(98) = 970.200 cara.

 

Contoh-10:

Sebuah kata kunci (password) terdiri atas 6 huruf kecil. Tentukan ada berapa kata kunci berbeda yang mungkin?

 

Jawaban:

- Jika huruf-huruf dalam kata kunci boleh sama, maka ada :

26 x 26 x 26 x 26 x 26 x 26 = (26)6 kata kunci.

 

- Jika huruf-huruf dalam kata kunci tidak boleh sama, maka ada:

26 P 6 = = (26).(25).(24).(23).(22).(21) kata kunci.

 

3. KOMBINASI

Sebuah kombinasi r obyek yang dipilih dari sebuah himpunan dengan n elemen adalah sebuah pemilihan r elemen tak berurutan dari himpunan tersebut.

Teorema-2.2: Kombinasi

Untuk sembarang bilangan bulat positip n dan bilangan tak negatip r, dengan rn, maka:

Banyaknya kombinasi r obyek yang diambil dari n obyek berbeda adalah

=

Bukti:

Jika urutan dalam r elemen diperhatikan, maka ada nPr hasil berbeda. Karena kombinasi tidak memperhatikan urutan, maka seluruh permutasi r elemen tertentu dalam himpunan n elemen yaitu sebanyak r! pola diwakili salah satu saja. Jadi banyaknya kombinasi adalah

=

Contoh-11:

Sebuah team bola volley inti diseleksi dari sebanyak 10 kandidat anggota. Berapakah banyaknya konfigurasi team inti yang mungkin?

Jawaban:

Karena dalam team tidak dikenal urutan, maka masalah ini identik dengan masalah menghitung kombinasi 6 obyek yang diambil dari 10 obyek berbeda. Jadi ada sebanyak = = 210 konfigurasi team inti.

Contoh-12:

Empat team bulu tangkis ganda disusun dari sejumlah 8 pemain. Tentukan banyaknya konfigurasi yang mungkin, jika setiap pemain hanya bermain pada satu team?

Jawaban:

- Untuk memilih team pertama sampai team ke empat ada: , , dan

Jadi dengan kaidah perkalian banyaknya konfigurasi adalah:

...= .. .

= (28).(15).(6).(1)

= 2520.

 

4. KOEFISIEN BINOMIAL

 

Segitiga Pascal:

Untuk sembarang bilangan bulat positip n dan bilangan bulat tak negatip k, dengan kn, maka bilangan membangun sebuah segitiga bilangan yang disebut “segitiga pascal

 

 

Teorema-2.3: Binomial

Untuk sembarang bilangan bulat positip n, maka berlaku identitas berikut:

( x + y )n = xk yn-k

 

Bukti:

Dengan melakukan induksi matematik terhadap n, diperoleh:

-          Basis Induksi: Untuk n = 1, maka diperoleh:

-          x + y = x0 y1 + x1 y0 = x + y

-          Hipotesa Induksi: Untuk n -1, diasumsikan ekspresi berikut benar.

-          ( x + y )n-1 = xk yn-1-k

-          Step Induksi: Untuk n diperoleh:

-          ( x + y )n = ( x + y ) ( x + y )n-1

-          = ( x + y ) xk yn-1-k

-          = xk+1 yn-1-k + xk yn-k

-          dengan mengambil: i = k + 1 pada suku pertama dan

-          i = k pada suku kedua.

-          maka diperoleh

 

= xi yn-1 + xi yn-1

 

= xn + + xi yn-1 + yn

= xn + xi yn-1 + yn

= xi yn-i

 

Bilangan dalam teorema diatas dikenal sebagai “koefisien binomial”.

 

Contoh-13:

Tulislah (x + y)4 kedalam ekspansi binomial!

 

Jawaban:

(x + y)4 = x k y4-k

= x 0 y4-0 + x1 y4-1 + x2 y4-2 + x3 y4-3 + x4 y4-4

= y4 + 4xy3 + 6x2y2 + 4x3y + x4

 

Contoh-14:

Hitunglah jumlah koefisien suku-suku dalam (x + y)n ?

 

Jawaban:

Karena (x + y)n = xk yn-k , maka: dengan mengambil x = 1 dan y = 1, diperoleh:

(1 + 1)n = 2n =

 

Jadi jumlah koefisien dari (x + y)n adalah 2n.

 

5. KOEFISIEN MULTINOMIAL

Misal sebuah himpunan n obyek berbeda dibagi kedalam r kelompok berbeda yang masing-masing berukuran n1, n2, n3, ….., nr , dengan: n1 + n2 + n3 + … + nr n. Banyaknya pembagian berbeda yang mungkin dapat dihitung sebagai berikut:

 

- banyaknya pilihan berbeda yang mungkin untuk kelompok pertama, kedua, ketiga, keempat,..…, ke-r secara berurutan adalah , , , ..…,

- sehingga dengan kaidah perkalian, banyaknya pembagian berbeda yang mungkin adalah …..=

 

 

 

Notasi:

 

Jika n1 + n2 + n3 + … + nr = n, maka ekspresi

=

menyatakan banyaknya pembagian yang mungkin dari n obyek berbeda kedalam r kelompok yang berukuran n1, n2, n3, …, nr.

 

Contoh-15:

Sebanyak 50 orang turis manca negara ingin mengunjungi sebuah pulau dengan menggu-nakan jalur udara. Jika hanya tersedia sebuah pesawat dengan kapasitas 10 penumpang yang menuju pulau tersebut, ada berapa formasi penerbangan para turis tersebut?

 

Jawaban:

Untuk mengangkut 50 orang turis tersebut, ada 5 penerbangan, dimana:

-          untuk pengelompokan penerbangan ada

-          untuk urutan penerbangan kelompok ada 5!

Sehingga dengan kaidah perkalian banyaknya formasi penerbangan yang mungkin adalah

(5!)

 

 

Contoh-16:

Sekumpulan 100 job menunggu diproses oleh sebuah sistem komputer yang melakukan pemrosesan berkelompok (bath-processing) secara acak dengan besar kelompok 20 job. Tentukan banyaknya konfigurasi pemrosesan job tersebut yang mungkin?

 

Jawaban:

Sebanyak 100 job tersebut akan dikerjakan dengan 5 proses secara berurutan, dimana:

-          untuk membagi secara berkelompok ada

-          untuk urutan pemrosesan kelompok ada 5!

Jadi banyaknya konfigurasi pemrosesan job tersebut adalah (5!).

 

Teorema-2.4: Multinomial

 

Jika n1 + n2 + n3 + …+ nr = n, maka:

( x1 + x2 + x3 + … + xr )n = x1n1.x2n2.x3n3…...xrnr

 

Bukti:

Dengan melakukan induksi terhadap r (banyaknya suku), diperoleh:

 

Basis Induksi: Untuk r = 1, maka n1 = n dan diperoleh:

(x1)n = (x1)n = (x1)n

 

Hipotesa Induksi : Untuk r-1, diasumsikan ekspresi berikut benar:

(x1 + x2 + x3 + … + xr-1)n = x1n1 x2n2 x3n3 … xr-1n(r-1)

 

Step Induksi : Untuk r, diperoleh:

 

(x1 + x2 + x3 + … + xr)n = (x1 + x2 + x3 + … + xr-1) + xrn

= (x1 + x2 + x3 + … + xr-1)k (xr)n-k

= x1n1 x2n2 x 3 n3 xr-1n(r-1)(xr)n-k

= . x1n1 x2n2 x3n3 … xr-1n(r-1)(xr)n-k

dengan substitusi: n-k = nr , diperoleh:

= x1n1 x2n2 x3n3 xrnr

= x1n1 x2n2 x3n3 … xrnr

 

 

Bilangan dikenal sebagai “koefisien multinomial”.

 

Contoh-17:

Ekspansikan ekspresi (x1 + x2 + x3 )2 dengan teorema multinomial?

 

Jawaban:

(x1 + x2 + x3)2 = x12 x20 x30 + x10 x22 x30 + x10 x20 x32 +

x11 x21 x30 + x11 x20 x31 + x10 x21 x31

= x12 + x22 + x32 + 2x1x2 + 2x1x3 + 2x2x3

 

Teorema-2.5:

Terdapat sebanyak vektor dengan komponen tak negatip (x1, x2, x3, …, xr) ber-beda yang memenuhi : x1 + x2 + x3 + … + xr = n.

 

Bukti:

Perhatikan sebuah vektor yang memiliki komponen: 1 sebanyak n dan 0 sebanyak r-1.

Untuk setiap permutasi komponen vektor tersebut:

-          x1 banyaknya komponen angka 1 di sebelah kiri komponen angka 0 pertama,

-          x2 banyaknya komponen angka 1 diantara komponen 0 pertama dan kedua,

-          x3 banyaknya komponen angka 1 diantara komponen 0 kedua dan ketiga, dst,

-          xr-1 banyaknya komponen angka 1 diantara komponen 0 ke-(r-2) dan ke-(r-1),

-          xr banyaknya komponen angka 1 disebelah kanan komponen angka 0 terakhir.

-           

Sebagai contoh, jika n = 6 dan r = 4 maka vektor berbentuk (1,1,0,0,1,1,1,0,1) memiliki solusi: x1 = 2, x2 = 0, x3 = 3, dan x4 = 1. Disini, banyaknya permutasi: ==

 

Sehingga untuk kasus diatas, maka banyaknya permutasi vektor dengan komponen 1 sebanyak n dan komponen 0 sebanyak r-1 adalah =

 

Contoh-18:

Tentukan banyaknya solusi berupa bilangan bulat tak negatip berbeda yang mungkin untuk persamaan: x1 + x2 = 3 !

 

Jawaban:

Disini, nilai n = 3 dan r = 2. Jadi ada sebanyak = = 4 solusi berbeda, yaitu: (0,3), (1,2), (2,1), dan (3,0).

 

Contoh-19:

Tentukan banyaknya suku pada ekspansi binomial dari (x1 + x2 + x3 + … + xr )n !

 

Jawaban:

Karena pada (x1 + x2 + x3 + … + xr )n = x1n1 x2n2 x3n3 … xrnr nilai: n1, n2, n3, …, nr bulat tak negatip dan memenuhi n1 + n2 + n3 + … + nr = n, maka menurut teorema-2.5 banyaknya suku adalah .

 

6. SOAL LATIHAN

 

1. Sebuah pusat komputer memiliki 32 PC, setiap PC memiliki 24 port. Ada berapa port berbeda dalam pusat komputer tersebut ? .

 

2. Ada berapa fungsi dari sebuah himpunan dengan m elemen ke sebuah himpunan dengan n elemen ?

 

3. Ada berapa banyak plat ijin berbeda dapat dibuat, jika setiap pelat memuat sebuah barisan 3 huruf diikuti dengan 3 angka?

 

4. Seorang mahasiswa dapat memilih sebuah tugas mata kuliah ilmu komputer satu dari tiga daftar. Tiga daftar tersebut memuat: 23, 15 dan 19 tugas yang memungkinkan. Berapa banyaknya tugas yang mungkin dapat dipilih?

 

5. Setiap pemakai (user) pada sebuah sistem komputer memiliki sebuah kata kunci (password) dengan panjang 6 sampai dengan 8 karakter dan setiap karakter berupa sebuah huruf besar atau sebuah angka. Jika setiap kata kunci memuat sekurang-kurangnya satu angka, ada berapa kata kunci yang mungkin?

 

6. Berapa banyaknya string angka (bits string) dengan panjang 10 dan memuat :

a) tepat tujuh angka 1.

b) sekurang-kurangnya tujuh angka 1.

7. Buktikan: = + + … + dengan: rm, dan rn

 

8. Jelaskan bahwa: =

 

9. Dengan induksi matematika, buktikan bahwa: = +

 

10.Buktikan: = 2

 

Kunci Jawaban:

  1. 32 . 24 = 768 port.
  2. n . n . n … n = nm fungsi.
  3. 26 . 26 . 26 . 10 . 10 . 10 = 17.576.000 pelat.

4. 23 + 15 + 19 = 57 tugas.

5. Kata kunci dengan panjang : 6, 7 dan 8 berturut-turut sebanyak: 366-266, 367–267

dan 368-268

Jadi banyaknya kata kunci adalah = (366-266) + (367-267) + (368-268)

= 2.684.483.063.360.

6. a) 93 . 107 = 729 . 720 = 524.880 string.

b) 90 . 10P10 + 91 . 10 P9 + 92 . 10 P8 + 93 . 10 P7 = 1 + 9 .10! + 81.

 

Pascal's Triangle

Figure 1Pandang segitiga Pascal:

 

 

 

Gambar 1

Pada baris ke nilai-nilai koefisien adalah berbentuk barisan , dengan i=0, 1, …, n dan k=0, 1, …,i.

Segitiga di atas dapat digunakan untuk mengekspansi (x+y)n , sebagai berikut.

( x + y )n = xk yn-k

Perhitungan , untuk i=1,2,3,4,5 dapat dilakukan dengan mudah:

        

        

        

        

        

 


Download contoh soal

OLIMPIADE SAINS TERAPAN NASIONAL (OSTN) 2008
Fax : 021-5725474, 021-5725409