KOMBINATORIKA Erwin Harahap
Disampaikan pada acara Sosialisasi OLIMPIADE MATEMATIKA, FISIKA, DAN KIMIA 2011 KOPERTIS WILAYAH IV JAWA BARAT Jatinangor- Bandung, 22 Maret 2011
1
KEMENTRIAN PENDIDIKAN NASIONAL DIREKTORAT JENDERAL PENDIDIKAN TINGGI DIREKTORAT PEMBELAJARAN DAN KEMAHASISWAAN 2011 2
3
4
Materi Olimpiade Matematika
5
Jenis Tes/Soal
6
Content • • • • • • • •
Koefisien Binomial Pohon The Marriage Theorem Pigeonhole Principle Inklusi-Eksklusi Paritas Eulerian / Hamiltonian Rekuren 7
Koefisien Binomial Jika a dan b adalah bilangan real dan n adalah bilangan bulat positif, maka : n
( a b)
n
C (n, k )a
n k
b
k
k 0
Materi terkait: Prinsip penjumlahan, perkalian, Permutasi, kombinasi, permutasi dan kombinasi dengan pengulangan 8
Pohon (tree) • Pohon (tree) adalah Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh satu lintasan tertentu • Pohon merupakan graf tak-berarah yang terhubung dan tidak memiliki siklus maupun sirkuit.
9
The Marriage Theorem • Jika S adalah suatu himpunan simpul di G, misal d(S) adalah sejumlah titik di G yang berpasangan dengan paling sedikit satu anggota S • Pengertian tentang teorema ini lebih mengarah kepada graf bipartisi (bipartite)
10
The Marriage Theorem (lanjutan) • Graf bipartisi (bipartite graph) adalah graf yang himpunan titiknya dapat dipisahkan menjadi dua himpunan tak kosong X dan Y sehingga masingmasing sisi di graf tersebut menghubungkan satu titik di X dan satu titik di Y
11
Pigeonhole Principle • Jika k buah benda ditempatkan pada k buah kotak, maka akan terdapat paling sedikit 2 buah benda pada satu kotak • Akan terdapat paling sedikit 2 sarung tangan pada tangan yang sama dari 3 buah sarung tangan
12
Pigeonhole Principle (lanjutan) Jika n merpati (pigeon) dimasukkan kedalam m kandang (hole) dimana n>m , maka akan terdapat paling sedikit satu kandang berisi lebih dari satu merpati
13
Pigeonhole Principle : Soal 1 Paling sedikit dalam berapa kali pelemparan dari sebuah dadu agar dapat dijamin angka yang sama akan muncul 2 kali ?
14
Pigeonhole Principle : Jawab 1 Paling sedikit 7 kali pelemparan
15
Pigeonhole Principle : Soal 2 Misalkan P1, P2, P3, P4, P5 adalah lima titik latis berbeda pada suatu bidang cartesius.
Buktikan bahwa terdapat sepasang titik (Pi, Pj), i ≠ j, sedemikian sehingga ruas garis Pi Pj akan memuat titik latis selain Pi dan Pj.
16
Pigeonhole Principle : Jawab 2 Misalkan 2 titik yang merupakan bagian dari Pn titik tersebut adalah
( x1 , y1 ) dan ( x2 , y2 ) Maka koordinat titik tengahnya adalah :
1 (( x1 x2 ), ( y1 2
y2 ))
17
Pigeonhole Principle : Jawab 2 (lanjutan)
Dikarenakan koordinat titik tengah tersebut merupakan bilangan bulat maka
( x1 x2 ) dan ( y1
y2 )
adalah genap jika dan hanya jika paritas x1 dan x2 sama, serta paritas y1 dan y2 sama.
18
Pigeonhole Principle : Jawab 2 (lanjutan)
4 Paritas titik yang mungkin : (genap, genap), (genap, ganjil) (ganjil, genap), (ganjil, ganjil) Maka menurut pigeonhole principle, jika terdapat 5 titik latis berbeda (P1, P2, P3, P4, P5 ), maka dua titik diantaranya memiliki paritas yang sama, dan memuat titik latis selain Pn 19
Prinsip Inklusi-Eksklusi
Untuk mencacah banyaknya unsur di dalam A∪B, kita dapat melakukannya dengan mencacah banyaknya unsur himpunan A dan himpunan B − A dan kemudian menjumlahkannya
|A B| =|A| + |B| -|A B| 20
Inklusi Eksklusi : Soal 1 Tentukan banyaknya bilangan bulat dari 1 s/d 1000 yang habis dibagi 3 atau 5
21
Inklusi Eksklusi : Jawab 1 |A| habis dibagi 3 333 |B| habis dibagi 5 200 |A B| habis dibagi 3*5 66 Total : |A B| =|A| + |B| -|A B| = 333 + 200 - 66 = 467 22
Inklusi Eksklusi : Soal 2 Tentukan banyaknya bilangan bulat dari 1 s/d 1000 yang tidak habis dibagi 3 dan tidak habis dibagi 5
23
Inklusi Eksklusi : Jawab 1 (lanjutan) Hukum de Morgan :
(A’ B’)= (A B)’ |(A B)’| =|S| -|A B| = 1000 - 467 = 533
24
Eulerian / Hamiltonian • Misal G suatu graf. LIntasan Euler pada G adalah lintasan yang memuat setiap sisi di G. • Graf G di sebut graf Euler (Eulerian) jika G memuat lintasan Euler yang tertutup • Sirkuit Hamilton G adalah sirkuit yang memuat setiap titik di G • Graf G di sebut Graph Hamilton (Hamiltonian) jika G memuat sirkuit Hamilton 25
Eulerian / Hamiltonian (lanjutan)
26
Rekuren • Persamaan rekurensi adalah persamaan yang menentukan nilai suku xn dalam fungsi dari suku-suku sebelumnya, yaitu xn-1 , xn-2 , ... • Persamaan rekurensi berbentuk
• Fungsi karakteristik
27
Rekuren : Soal 1 Barisan a1, a2, . . . didefinisikan dengan a1 = 1, a2 = 1,
Dan
Tentukan bentuk eksplisit dari an
28
Rekuren : Jawab Soal 1 Barisan
Persamaan karakteristik : Difaktorkan menjadi :
Bentuk umum :
29
Rekuren : Jawab Soal 1 (lanjutan) 1 1 c 2 c ( 1 ) 1 2c1 c2 1 a1 = 1 1 2 2 2 a2 = 1 c1 2 c2 ( 1) 1 4c1 c2 1
Eliminasi
Dengan demikian, bentuk umum an : Untuk n = 1,2,3, … 30
Rekuren : Soal 2 Barisan a1, a2, . . . an dimana a1 1
2 an
1
Tentukan bentuk umum a n
31
Rekuren : Jawab Soal 2 Persamaan karakteristik : an
2 an 1
Bentuk umum : a1 1 maka
Dgn demikian :
x 2 0 c2n
an c
an
1 2
2
n 1
untuk n = 1,2,3, … 32
Sekian dan Terima kasih
[email protected] http://erwin2h.wordpress.com
33
