Showing posts with label Matematika. Show all posts

Buku Kalkulus Edisi 9 Purcell - Varberg - Rigdon Jilid 1 dan 2 Bahasa Inggris PDF

Buku Kalkulus edisi 9 jilid 1 dan 2 karya Dale Varberg, Edwin Purcell, dan Steven E. Rigdon bahasa inggris untuk perguruan tinggi dan universitas. Pdf buku kalkulus merupakan salah satu bahan ajar mahasiswa dalam mata kuliah kalkulus dan kalkulus lanjut yang dapat didownload pada link dibawah.

Buku Kalkulus Purcell Edisi 9 Jilid 1 dan 2 (Gabung) Bahasa Inggris

Solusi dan Kunci Jawaban Buku Kalkulus Purcell Edisi 9 Jilid 1 dan 2

Daftar Isi versi Bahasa Indonesia

0. Preliminaries Persiapan

1. Limit

2. Turunan

3. Aplikasi Turunan

4. Integral Tentu

5. Penerapan Integral

6. Fungsi Transenden

7 Teknik Integrasi

8 Bentuk Tak-tentu dan Integral Tak-Wajar

9 Deret Tak-terhingga

10 Irisan Kerucut dan Koordinat Polar

11 Geometri dalam Ruang dan Vektor

12 Turunan untuk Fungsi Dua Variabel atau Lebih, multi variabel peubah banyak

13 Integral Lipat

14 Kalkulus Vektor

Soal OSK Matematika SMA 2009

1. Banyaknya bilangan asli kurang dari 1000 yang dapat dinyatakan dalam bentuk x2 − y2 untuk suatu bilangan ganjil x dan y adalah ⋅⋅⋅⋅⋅⋅⋅

2. Bilangan bulat positif terkecil n dengan n > 2009 sehingga 1^3+2^3+3^3+...+n^3/n merupakan bilangan bulat adalah ⋅⋅⋅⋅⋅⋅⋅⋅⋅ 3. Banyaknya solusi real x dari persamaan 3^(1/2 + log3(cos x-sin x)+2^(log2(cosx+sin x)) adalah ⋅⋅⋅⋅

4. Diberikan fungsi f : R R sedemikian hingga x2f(x) + f(1 − x) = 2x − x4 untuk semua x ∈ R. Nilai f(2009) adalah ⋅⋅⋅⋅⋅⋅

5. Banyaknya segitiga siku-siku yang kelilingnya 2009 dan sisi-sisinya bilangan bulat serta jari-jari lingkaran dalamnya juga bilangan bulat adalah ⋅⋅⋅⋅⋅⋅⋅

6. Nilai eksak dari adalah ⋅⋅⋅⋅⋅⋅⋅⋅ (2009 1) + (2009 2) +...+ (2009 1004)

7. Jika tiga pasang suami isteri akan menempati tujuh kursi yang berjajar ke samping dengan syarat semua suami isteri duduk berdekatan dan tidak ada laki-laki dan perempuan bukan suami isteri yang duduk berdekatan, maka banyak caranya adalah ⋅⋅⋅⋅⋅⋅⋅

8. Nilai dari adalah ⋅⋅⋅⋅⋅⋅⋅⋅ (∑=FPB(k,7)

9. Banyaknya pasangan bilangan asli (x, y) sehingga x4 + 4y4 merupakan bilangan prima adalah ⋅⋅⋅⋅⋅

10. Bilangan real x sehingga pernyataan x2 = x jika dan hanya jika x3 = x bernilai salah adalah ⋅⋅⋅⋅⋅

11. Diketahui ABC adalah segitiga siku-siku di A dengan AB = 30 cm dan AC = 40 cm. Misalkan AD adalah garis tinggi dari dan E adalah titik tengah AD. Nilai dari BE + CE adalah ⋅⋅⋅⋅⋅⋅⋅

12. Suatu turnamen diikuti 20 tim, dimana setiap tim bertemu satu kali dengan semua tim yang lain. Kemenangan memperoleh poin 1, sedangkan kekalahan 0. Pada klasemen akhir, 3 tim teratas memperoleh poin yang sama, sedangkan 17 tim yang lain memperoleh poin yang berbeda-beda. Jumlah semua bilangan yang tidak muncul pada poin yang dimiliki suatu tim pada klasemen akhir adalah ⋅⋅⋅⋅⋅⋅⋅⋅

13. Titik E terletak di dalam persegi ABCD sedemikian rupa sehingga ABE adalah segitiga sama sisi. Jika panjang AB = 3 1+ dan F titik potong antara diagonal BD dengan segmen garis AE, maka luas segitiga ABF sama dengan ⋅⋅⋅⋅⋅⋅

14. Misalkan f(x) = ( 1 sin 3−+ ) ( 3 ycos 1 ) y +. Nilai maksimum untuk (f(y))2 dimana y bilangan real adalah ⋅⋅⋅⋅⋅⋅

15. Diberikan persegi ABCD dengan panjang sisi 10. Misalkan E pada AB dan F pada BD dengan AE = FB = 5. Misalkan P adalah titik potong CE dan AF. Luas DFPC adalah ⋅⋅⋅⋅⋅⋅⋅⋅⋅

16. Jika x k + 1 = x k + 2 1 untuk k = 1, 2, ⋅⋅⋅ dan x1 = 1 maka x1 + x2 + ⋅⋅⋅ + x400 = ⋅⋅⋅⋅⋅⋅⋅

17. Diberikan segitiga ABC tumpul (∠ABC > 90o), AD dan AE membagi sudut BAC sama besar. Panjang segmen garis BD, DE dan EC berturut-turut adalah 2, 3, dan 6. Panjang terpendek dari sisi segitiga ABC adalah ⋅⋅⋅⋅⋅⋅

18. Jika 10999999999 dibagi oleh 7, maka sisanya adalah ⋅⋅⋅⋅⋅⋅⋅⋅⋅

19. Diketahui A adalah himpunan semua bilangan asli yang habis dibagi 3, tidak habis dibagi 5, dan tidak lebih dari 100. Banyaknya fungsi f dari himpunan semua bilangan real yang tidak nol ke dalam A yang memenuhi f ⎜ ⎝ ⎛ ⎜ y x ⎟ ⎠ ⎞ ⎟ = f x (y − ) adalah ⋅⋅⋅⋅⋅⋅

20. Delapan bilangan asli memiliki rata-rata 6,5. Empat dari delapan bilangan tersebut adalah 4, 5, 7, dan 8. Selisih antara bilangan terbesar dan terkecil adalah 10. Jika ke delapan bilangan diurutkan dari kecil ke besar, maka banyaknya susunan ada ⋅⋅⋅⋅⋅⋅⋅

Soal OSP Matematika SMA 2009

1. Tiga dadu berwarna hitam, merah, dan putih dilempar bersama-sama. Macam hasil lemparan sehingga jumlah ketiga mata dadu adalah 8 sebanyak ⋅⋅⋅⋅⋅⋅⋅⋅⋅

2. Banyaknya bilangan real x yang memenuhi persamaan x4 − 2x3 + 5x2 − 176x + 2009 = 0 adalah ⋅⋅⋅⋅⋅⋅

3. Bilangan rasional a < b < c membentuk barisan hitung (aritmatika) dan a/b+b/c+c/a=3 Banyaknya bilangan positif a yang memenuhi adalah ⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

4. Misalkan N menyatakan himpunan semua bilangan bulat positif dan Banyaknya himpunan bagian dari S adalah ⋅⋅⋅⋅⋅⋅⋅⋅⋅

5. Diberikan segitiga ABC dengan tan ∠CAB = 22/7. Melalui titik sudut A ditarik garis tinggi sedemikian rupa sehingga membagi sisi BC menjadi segmen-segmen dengan panjang 3 dan 17. Luas segitiga ABC adalah ⋅⋅⋅⋅⋅⋅⋅⋅

6. Nilai minimum dari f(x)=9x2 sin2 x+4/xsin x untuk 0 < x < π adalah ⋅⋅⋅⋅⋅⋅⋅

7. Diberikan segitiga dengan panjang dari ketiga garis tinggi segitiga itu merupakan bilangan bulat. Jika panjang kedua garis tingginya adalah 10 dan 6, maka panjang maksimum garis tinggi ketiga adalah ⋅⋅⋅⋅⋅⋅

8. Suatu fungsi f : Z Q mempunyai sifat f(x+1)=1+f(x)/1-f(x) untuk setiap x ∈ Z. Jika f(2) = 2, maka nilai fungsi f(2009) adalah ⋅⋅⋅⋅⋅

9. Diketahui segitiga siku-siku ABC dengan panjang sisi-sisinya a, b, dan c serta a < b < c. Misalkan r dan R berturut-turut menyatakan panjang jari-jari lingkaran dalam dan lingkaran luarnya. Jika r(a+b+c)/R2 maka nilai dari r/a+b+c adalah ⋅⋅⋅⋅⋅⋅⋅⋅

10. Jika tan x + tan y = 25 dan cot x + cot y = 30, maka nilai tan (x + y) adalah ⋅⋅⋅⋅⋅⋅

11. Pada bagian kanan 100! terdapat digit 0 berturut-turut sebanyak ⋅⋅⋅⋅⋅⋅⋅⋅

12. Ada empat pasang sepatu akan diambil empat sepatu secara acak. Peluang bahwa yang terambil ada yang berpasangan adalah ⋅⋅⋅⋅⋅⋅

13. Diketahui k, m, dan n adalah tiga bilangan bulat positif yang memenuhi mk + nm 4 = Bilangan m terkecil yang memenuhi adalah ⋅⋅⋅⋅⋅⋅ 6 1

14. Bilangan prima p yang memenuhi (2p − 1)3 + (3p)2 = 6p ada sebanyak ⋅⋅⋅⋅⋅⋅

15. Jika x1, x2, ⋅⋅⋅, x2009 bilangan real, maka nilai terkecil dari cos x1 sin x2 + cos x2 sin x3 + ⋅⋅⋅ + cos x2009 sin x1 adalah ⋅⋅⋅⋅⋅

16. Misalkan a, b, c adalah akar-akar polinom x3 − 8x2 + 4x − 2. Jika f(x) = x3 + px2 + qx + r adalah polinom dengan akar-akar a + b − c, b + c − a, c + a − b maka f(1) = ⋅⋅⋅⋅⋅⋅

17. Banyaknya segitiga tumpul dengan sisi bilangan asli yang memiliki sisi-sisi terpanjang 10 adalah ⋅⋅ (Catatan : dua segitiga kongruen dianggap sama)

18. Misalkan n bilangan asli terkecil yang mempunyai tepat 2009 faktor dan n merupakan kelipatan 2009. Faktor prima terkeci dari n adalah ⋅⋅⋅⋅⋅⋅

19. Misalkan p(x) = x2 − 6 dan A = {x ∈ R⏐p(p(x)) = x}. Nilai maksimal dari {⏐x⏐ : x ∈ A} adalah ⋅⋅⋅⋅⋅⋅

20. Misalkan = 5 + 1 q dan ⎣x⎦ menyatakan bilangan bulat terbesar yang lebih kecil atau sama 2 dengan x. Nilai ⎣q⎣qn⎦⎦ − ⎣q2n⎦ untuk sebarang n ∈ N adalah ⋅⋅⋅⋅⋅⋅

1. Seekor semut hendak melangkah ke makanan yang berada sejauh 10 langkah di depannya. Semut tersebut sedang mendapatkan hukuman, ia hanya boleh melangkah ke depan sebanyak kelipatan tiga langkah dan selebihnya harus melangkah ke belakang. Tentukan banyaknya cara melangkah agar bisa mencapai makanan, jika ia harus melangkah tidak lebih dari dua puluh langkah. (Catatan : jika semut melangkah dua kali dimana masing-masing melangkah sekali ke belakang, maka dianggap sama saja dengan dua langkah ke belakang.) 2009

2. Diberikan n adalah bilangan asli. Misalkan 6+ x2009 =. Jika n x x 3 − − rasional, tunjukkan bahwa n merupakan kuadrat dari suatu bilangan asli. x x merupakan bilangan

3. Diberikan segitiga ABC dan titik D pada sisi AC. Misalkan r1, r2 dan r berturut-turut menyatakan jari-jari lingkaran dalam dari segitiga-segitiga ABD, BCD, dan ABC. Buktikan bahwa r1 + r2 > r.

4. Diketahui p adalah bilangan prima sehingga persamaan 7p = 8x2 − 1 dan p2 = 2y2 − 1 mempunyai solusi x dan y berupa bilangan bulat. Tentukan semua nilai p yang memenuhi.

5. Diketahui himpunan H mempunyai lima anggota dari {0, 1, 2, 3, ⋅⋅⋅, 9}. Buktikan ada dua himpunan bagian dari H, yang tidak kosong dan saling asing, yang jika semua anggotanya dijumlahkan hasilnya sama.

Soal OSN Matematika SMA 2009

1. Tentukan banyaknya bilangan n ∈ {1, 2, 3, ⋅⋅⋅, 2009} sedemikian sehingga 4n6 + n3 + 5 habis dibagi 7.

2. Misalkan untuk setiap bilangan real x didefinisikan ⎣x⎦ sebagai bilangan bulat terbesar yang lebih kecil atau sama dengan x. Diberikan a1, a2, a3, ⋅⋅⋅ suatu barisan bilangan asli yang memenuhi a1+1/a2=a2+1/a3=a3+1/a4=... . Buktikan bahwa an+1/a(n+1)<1 untuk setiap bilangan asli n.

3. Pada segitiga ABC, titik-titik D, E dan F berturut-turut terletak pada segmen BC, CA dan AB. Nyatakan P sebagai titik perpotongan AD dan EF. Tunjukkan bahwa AD/AFxDC + AC/AExDB + AD/APxBC

4. Di suatu pulau terdapat 7 kota dan ada jaringan kereta api yang melalui kota-kota tersebut. Setiap segmen rel menghubungkan tepat 2 kota, dan diketahui bahwa setiap kota memiliki paling sedikit 3 segmen ke kota lain. Buktikan bahwa terdapat rute perjalanan kereta api yang mengunjungi 4 kota yang berbeda masing-masing sekali dan kembali ke kota asalnya. (Contoh : rute A − B − C − D − A)

5. Di dalam suatu laci terdapat paling banyak 2009 bola yang terdiri dari bola putih dan biru yang tercampur secara acak. Jika dua bola diambil secara acak tanpa pengembalian, maka diketahui probabilitas bahwa terambil keduanya bola warna putih atau keduanya bola warna biru adalah 21 . Berapa banyak maksimum bola putih yang mungkin berada dalam laci sedemikian sehingga pernyataan tentang probabilitas tersebut tetap terpenuhi ?

6. 6. Tentukan nilai terkecil yang mungkin dari fungsi f(x) = x2008 − 2 x2007 + 3 x2006 − 4 x2005 + 5 x2004 + ⋅⋅⋅ − 2006 x3 + 2007 x2 − 2008x + 2009 untuk sebarang bilangan real x.

7. Suatu pasangan bilangan bulat (m, n) dikatakan baik bila m⏐n2 + n dan n⏐m2 + m Diberikan sebarang dua bilangan asli a, b > 1 yang relatif prima, buktikan bahwa terdapat pasangan baik (m, n) dengan a⏐m dan b⏐n tetapi a tidak membagi n dan b tidak membagi m.

8. Diberikan segitiga ABC lancip. Lingkaran dalam segitiga ABC menyinggung BC, CA, dan AB berturut-turut di D, E, dan F. Garis bagi sudut A memotong DE dan DF berturut-turut di K dan L. Misalkan AA1 adalah garis tinggi dan M titik tengah BC. (a) Buktikan bahwa BK dan CL tegak lurus garis bagi sudut BAC (b) Tunjukkan bahwa A1KML adalah segiempat talibusur

Definisi Pewarnaan Graf (Coloring Graph)

Masalah pewarnaan graf adalah memberikan warna pada elemen-elemen tertentu dari graf yang tunduk pada batasan-batasan tertentu. Pewarnaan titik adalah masalah pewarnaan graf yang paling umum. Soalnya, diberikan m warna, temukan cara mewarnai simpul dari suatu graf sedemikian rupa sehingga tidak ada dua simpul bertetangga yang diwarnai menggunakan warna yang sama.

Bilangan Kromatik

Bilangan Kromatik adalah banyaknya warna minimum yang diperlukan untuk mewarnai simpul-simpul suatu graf G sedemikian rupa sehingga tidak ada dua simpul bertetangga yang memiliki warna yang sama dilambangkan dengan x(G).

Teorema Bilangan Kromatik pada Subgraf bagian : Jika H adalah subgraf dari G,χ(H)≤χ(G).

Bukti: Setiap pewarnaan G memberikan pewarnaan yang tepat untuk H, hanya dengan memberikan warna yang sama pada simpul-simpul H yang mereka miliki di G. Ini berarti bahwa H dapat diwarnai dengan warna (G), bahkan mungkin lebih sedikit.

Teorema Pewarnaan Graf Komplit (Complete Graph): Jika G adalah graf lengkap dengan n titik (Kn) maka χ(n)=n.

Bukti: Karena G merupakan graf lengkap maka tiap titiknya berderajat n-1. Pilih sembarang titik v untuk diwarnai maka untuk mewarnai titik lain yang bertetangga memerlukan n-1 warna. Sehingga banyak warna n-1+1=n warna.

Teorema Graf Nol (Null Graph) : Jika G adalah graf nol maka χ(G)=1.

Bukti: Karena G graf nol maka tidak akan ada titik yang bertetangga sehingga hanya butuh satu warna untuk semua titik di G.

Teorema Graf Bipartisi : G graf bipartisi jika dan hanya jika χ(G).

Bukti: Himpunan titik V(G) dibagi menjadi dua himpunan bagian V1 dan V2. Pilih salah satu himpunan bagian V1, karena setiap titik pada himpunan bagian V1 tersebut tidak bertetangga maka hanya perlu menggunakan 1 warna begitu juga dengan V2. Kemudian tiap titik di V1 bertetangga di V2 sehingga V1 dan V2 memiliki warna yang berbeda sehingga χ(G)=2.

Teorema Graf Sikel: Jika G graf sikel Cn maka χ(G)=2 untuk n genap dan 3 untuk n ganjil.

Bukti: Untuk sikel genap, titik titik pada G dapat diwarnai selang seling sehingga hanya dibutuhkan 2 warna. Selanjutnya untuk sikel ganjil n, n-1 genap sehingga dapat selang seling, tetapi ada titik ke n yang terhubung dengan titik 1 dan n-1 yang memiliki 2 warna berbeda sehingga pada titik n memerlukan warna ke 3.

Teorema Derajat Terbesar: Misalakn G graf sederhana dengan derajat terbesar Δ(G), maka χ(G)≤ Δ(G)+1.

Teorema Graf Planar : Pada Graf Planar G dapat diwarnai oleh 4 warna.

Algoritma Welsh Powell

Dalam teori graf, pewarnaan simpul adalah cara memberi label pada setiap simpul individu sedemikian rupa sehingga tidak ada dua simpul bertetangga yang memiliki warna yang sama. Tapi kita perlu mencari tahu jumlah warna yang kita butuhkan untuk memenuhi kondisi yang diberikan. Tidak diinginkan untuk memiliki banyak variasi warna atau label. Jadi, Kami memiliki algoritma yang disebut algoritma welsh Powell yang memberikan warna minimum yang kami butuhkan. Algoritma ini juga digunakan untuk mencari bilangan kromatik suatu graf. Ini adalah pendekatan serakah berulang.

Algoritma Welsh Powell terdiri dari Langkah-langkah berikut:

Tentukan derajat setiap simpul
Daftar simpul dalam urutan derajat menurun.
Warnai simpul pertama dengan derajat terbesar dengan warna 1.
Pindah ke bawah daftar dan warnai semua simpul yang tidak terhubung ke simpul berwarna, dengan warna yang sama.

Ulangi langkah 4 pada semua simpul yang tidak diwarnai dengan warna baru, dalam urutan derajat yang menurun hingga semua simpul diwarnai.

Dengan memulai dengan derajat terbesar, kami memastikan bahwa simpul dengan jumlah konflik tertinggi dapat ditangani sedini mungkin.

Definisi Graf Eulerian

Lintasan Euler atau Eulerian path melalui graf adalah lintasan yang daftar sisinya memuat setiap sisi graf tepat satu kali.

Lintasan Euler yang berawal dan berakhir pada simpul yang sama disebut sirkuit Euler. Graf Euler adalah graf yang memiliki sirkuit Euler.

Teorema Graf Euler

Kasus Umum: Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki nol atau dua simpul yang berderajat ganjil. Jika tidak ada simpul yang berderajat ganjil, maka grafnya adalah Euler.

Berdasarkan teorema diatas akan didapatkan teorema dibawah:

Jika suatu graf terhubung dan setiap simpul berderajat genap, maka ia memiliki setidaknya satu sirkuit Euler.

Jika suatu graf terhubung dan memiliki tepat dua simpul berderajat ganjil, maka graf tersebut memiliki paling sedikit satu lintasan Euler (biasanya lebih). Setiap jalur tersebut harus dimulai pada salah satu simpul derajat ganjil dan berakhir di simpul lainnya.

Jumlah derajat semua simpul dari suatu graf sama dengan dua kali jumlah sisi (dan karenanya harus bilangan genap).

Cara Mencari Lintasan Sirkuit Euler / Eulerian

Pastikan bahwa setiap simpul dalam jaringan memiliki derajat genap.
Mulailah rangkaian Euler di sembarang simpul dalam jaringan.
Saat Anda memilih tepi, jangan pernah menggunakan tepi yang merupakan satu-satunya koneksi ke bagian jaringan yang belum Anda kunjungi.
Beri label tepi dalam urutan yang Anda tempuh dan lanjutkan ini sampai Anda telah melakukan perjalanan di sepanjang setiap tepi tepat satu kali dan Anda berakhir di simpul awal.

Definisi Graf Hamiltonian

Lintasan Hamilton atau Hamiltonian melalui suatu graf adalah lintasan yang daftar simpulnya berisi setiap simpul dari graf tepat satu kali, kecuali jika lintasannya adalah sirkuit, dalam hal ini simpul awal muncul untuk kedua kalinya sebagai simpul terminal/akhir. Jika lintasannya berupa sirkuit, maka disebut sirkuit Hamilton. Graf Hamilton adalah graf yang memiliki sirkuit Hamilton.

Teorema Hamilton

Grafik lengkap pasti memiliki sirkuit Hamilton.

Graf lengkap dengan N simpul adalah (N-1)! sirkuit Hamilton. Karena setengah dari sirkuit adalah bayangan cermin dari setengah lainnya, sebenarnya hanya ada setengah dari banyak sirkuit unik ini.

Cara mengatasi Travelling Salesman Problem (TSP)

Masalah penjual keliling adalah masalah di mana Anda membayangkan bahwa penjual keliling melakukan perjalanan bisnis. Dia mulai di kota asalnya (A) dan kemudian perlu melakukan perjalanan ke beberapa kota yang berbeda untuk menjual barang dagangannya (kota lainnya adalah B, C, D, dll.). Untuk menyelesaikan TSP, Anda perlu menemukan cara termurah bagi penjual keliling untuk memulai di rumah, A, bepergian ke kota lain, dan kemudian pulang ke A di akhir perjalanan. Ini hanya menemukan sirkuit Hamilton dalam grafik lengkap yang memiliki bobot keseluruhan terkecil. Ada beberapa algoritma yang berbeda yang dapat digunakan untuk memecahkan masalah jenis ini.

Algoritma Brute Force

Daftar semua kemungkinan sirkuit Hamilton dari grafik.
Untuk setiap sirkuit, temukan bobot totalnya.
Sirkuit dengan bobot total paling kecil adalah sirkuit Hamilton yang optimal.

Algoritma Tetangga Terdekat (Nearest-Neighbor Algorithm)

Pilih simpul sebagai titik awal.
Dari titik awal pergi ke simpul dengan tepi dengan bobot terkecil. Jika ada lebih dari satu pilihan, pilih secara acak.
Lanjutkan membangun sirkuit, satu per satu simpul dari antara simpul yang belum dikunjungi.
Dari simpul terakhir, kembali ke titik awal.

Algoritma Tetangga Terdekat Berulang (Repetitive Nearest-Neighbor Algorithm)

Biarkan X menjadi sembarang simpul. Terapkan Algoritma Tetangga Terdekat dengan menggunakan X sebagai titik awal dan hitung total biaya rangkaian yang diperoleh.
Ulangi proses tersebut dengan menggunakan setiap simpul lain dari graf sebagai simpul awal.
Dari sirkuit Hamilton yang didapat, pertahankan yang terbaik. Jika ada titik awal yang ditunjuk, tulis ulang rangkaian ini dengan titik tersebut sebagai titik referensi.

Algoritma Tautan Termurah (Cheapest-Link Algorithm)

Pilih link dengan bobot terkecil terlebih dahulu (jika ada seri, pilih salah satu secara acak). Tandai tepi yang sesuai dengan warna merah.
Pilih tautan termurah berikutnya dan tandai tepi yang sesuai dengan warna merah.
Lanjutkan memilih tautan termurah yang tersedia. Tandai tepi yang sesuai dengan warna merah kecuali jika a) menutup sirkuit atau b) menghasilkan tiga tepi yang keluar dari satu simpul.
Ketika tidak ada lagi simpul untuk dihubungkan, tutup sirkuit merah.

Definisi Pohon (Tree) dapa Teori Graph

Graf terhubung tak berarah G disebut pohon jika penghapusan salah satu sisinya membuat G terputus. Sekumpulan pohon Tree disebut hutan (forest).

Dalam teori graf, tree adalah graf tak berarah, terhubung, dan asiklik. Dengan kata lain, graf terhubung yang tidak memuat satu siklus pun disebut pohon.

Sebuah pohon mewakili struktur hierarkis dalam bentuk grafik. Elemen-elemen pohon disebut simpulnya dan tepi pohon disebut cabang. Sebuah pohon dengan n simpul memiliki (n-1) sisi.

Daun pada pohon adalah simpul berderajat 1 atau setiap simpul yang tidak memiliki cabang ke bawah disebut daun.

Sifat-sifat Tree Pohon

Setiap pohon pada dua atau lebih simpul memiliki setidaknya satu simpul daun.

Simpul yang berada di bagian atas pohon dikenal sebagai akar pohon.

Item data yang tersisa dibagi menjadi himpunan bagian yang terpisah-pisah yang disebut sebagai subpohon.

Pohon itu diperluas dari atas ke arah bawah.

Graf T adalah pohon jika dan hanya jika antara setiap pasangan simpul berbeda dari T terdapat lintasan yang unik.

Sebuah pohon dengan n simpul memiliki tepat n−1 cabang atau sisi.

Sebuah pohon dengan simpul berderajat k≥1 memiliki setidaknya k simpul daun. Secara khusus, setiap pohon dengan setidaknya dua simpul memiliki setidaknya dua simpul daun.

Sebuah titik potong pada graf terhubung G adalah sebuah titik yang penghilangannya memutuskan graf tersebut. Setiap graf terhubung memiliki simpul daun yang bukan merupakan titik potong.

Elemen elemen pada Tree

Edge – Garis yang menghubungkan dua node.

Level – Sebuah pohon dipartisi menjadi beberapa level sedemikian rupa sehingga simpul akar berada pada level 0. Kemudian, anak-anak terdekatnya berada di level 1, dan anak-anak terdekatnya berada pada level 2 dan seterusnya hingga terminal atau simpul daun.

Derajat – Ini adalah jumlah subpohon dari sebuah simpul di pohon tertentu.

Depth – Ini adalah tingkat maksimum dari setiap simpul di pohon tertentu dan juga dikenal sebagai ketinggian.

Node terminal – Node level tertinggi adalah node terminal sementara node lain kecuali terminal dan node root dikenal sebagai node non-terminal.

Perbedaan Tree dan Graf

Pada tree pohon hanya ada satu jalur antara dua simpul sedangkan grafik dapat memiliki jalur searah dan dua arah antara node.

Pada pohon, ada tepat satu simpul akar, dan setiap anak hanya dapat memiliki satu orang tua. Sebaliknya, dalam grafik, tidak ada konsep simpul akar.

Sebuah pohon tidak dapat memiliki loop dan self-loop sedangkan graph dapat memiliki loop dan self-loop.

Grafik lebih rumit karena dapat memiliki loop dan self-loop. Sebaliknya, pohon sederhana dibandingkan dengan grafik.

Sebuah pohon dapat memiliki n-1 sisi. Sebaliknya, dalam grafik, tidak ada jumlah tepi yang ditentukan sebelumnya, dan itu tergantung pada grafik.

Pohon memiliki struktur hierarkis sedangkan grafik memiliki model jaringan.

Pohon Merentang (Spanning Tree)

Jika G adalah graf terhubung pada n simpul, pohon merentang pada G adalah subgraf dari G yang merupakan pohon pada n simpul. Setiap graf terhubung memiliki spanning tree.

Metode Spanning Tree

Kita dapat menemukan pohon merentang secara sistematis dengan menggunakan salah satu dari dua metode:

1. Metode pemotongan

Mulailah memilih graf melingkar apa pun di Grafik G.

Hapus salah satu tepi graf melingkar.

Ulangi proses ini sampai tidak ada lingkaran yang tersisa.

2. Metode membangun

Pilih tepi graf G satu per satu. Sedemikian rupa sehingga tidak ada siklus yang dibuat.

Ulangi proses ini sampai semua simpul dimasukkan.

Definisi Graf Isomorfik

Isomorfisme graf adalah fenomena keberadaan graf yang sama dalam lebih dari satu bentuk yang disebut graf isomorfik.

Graf G dan H bersifat isomorfik jika terdapat struktur yang mempertahankan korespondensi satu-satu antara simpul dan sisi. Dengan kata lain, kedua graf tersebut hanya berbeda nama sisi dan simpulnya saja, tetapi secara struktural ekuivalen

Syarat dan Kondisi Dua Graf Isomorfik

Untuk setiap dua grafik menjadi isomorfik, 4 kondisi berikut harus dipenuhi,yaitu:

Jumlah simpul pada kedua graf harus sama.
Jumlah rusuk pada kedua graf harus sama.
Urutan derajat kedua grafik harus sama.
Jika sebuah siklus dengan panjang k dibentuk oleh simpul { v1 , v2 , ….. , vk } dalam satu graf, maka sebuah siklus dengan panjang k yang sama harus dibentuk oleh simpul { f(v1) , f(v2) , ….. , f(vk) } di grafik lain juga.

4 kondisi di atas hanyalah kondisi yang diperlukan untuk setiap dua grafik menjadi isomorfik. Mereka sama sekali tidak cukup untuk membuktikan tetapi hanya menunjukan bahwa kedua grafik tersebut mungkin isomorfik. Jika keempat syarat tersebut memenuhi, maka tidak dapat dikatakan bahwa graf tersebut pasti isomorfik. Namun, jika ada syarat yang dilanggar, maka dapat dikatakan bahwa graf tersebut pasti tidak isomorfik.

Kondisi berikut adalah kondisi yang cukup untuk membuktikan dua graf isomorfik. Jika salah satu dari kondisi ini memenuhi, maka dapat dikatakan bahwa grafik tersebut pasti isomorfik.

Dua graf dikatakan isomorfik jika dan hanya jika graf komplemennya isomorfik.
Dua graf dikatakan isomorfik jika matriks ketetanggaannya sama.
Dua graf dikatakan isomorfik jika sub-graf yang bersesuaian diperoleh dengan menghapus beberapa simpul dari satu graf dan gambar yang bersesuaian pada graf lainnya adalah isomorfik.

Definisi Graf Planar dan Graf Bidang (Planar Graf)

Suatu graf dikatakan planar jika graf tersebut dapat digambarkan pada suatu bidang tanpa ada sisi yang bersilangan. Gambar seperti itu disebut representasi planar graf.

Ketiga gambar diatas adalah graf K4 dan isomorfiknya merupakan contoh graf planar. Jika diperhatikan graf dikatakan planar jika salah satu isomorfiknya merupakan graf planar. Graf isomorfik yang digambarkan dengan sisi tidak menyilang satu sama lain disebut graf bidang (plane graph). Contoh Graf bidang adalah gambar ke 2 dan 3 dari K4.

Wilayah (Region) pada Graf Planar

Ketika graf planar digambar tanpa sisi-sisi yang bersilangan, sisi-sisi dan simpul-simpul dari graf tersebut membagi bidang menjadi daerah-daerah. Kami akan menyebut setiap wilayah sebagai wajah termasuk diluar graf. Graf K4 terdapat 4 wilayah. Wilayah pada planar disibolkan dengan f

Jumlah wajah tidak berubah bagaimanapun Anda menggambar grafik (selama Anda melakukannya tanpa tepi bersilangan), jadi masuk akal untuk menganggap jumlah wajah sebagai properti grafik planar.

Ada hubungan antara jumlah simpul (v), jumlah sisi (e) dan jumlah daerah (f) pada graf planar yang terhubung.

Untuk setiap graf planar terhubung dengan v simpul, tepi e dan wajah f, kita memiliki v−e+f=2 atau f=2-v+e.

Selain itu terdapat teorema lain yaitu:

Jika G adalah graf planar terhubung dengan e sisi dan v simpul, di mana v≥3, maka e≤3v-6. Juga G tidak dapat memiliki titik yang berderajat lebih dari 5.

Jenis Jenis Graf pada Teori Graph

Ada banyak jenis graf yang berbeda tergantung pada jumlah simpul, jumlah sisi, interkonektivitas, dan struktur keseluruhannya, beberapa jenis graf yang umum adalah sebagai berikut:

Graf Sederhana (Simple Graph)

Graf sederhana adalah graf yang tidak memiliki lebih dari satu sisi di antara dua simpul dan tidak ada sisi yang berawal dan berakhir pada simpul yang sama. Dengan kata lain graf sederhana adalah graf tanpa loop dan sisi ganda.

Graf Multi (Multi Graph)

Graf yang memiliki banyak sisi di antara setiap pasangan simpulnya atau terdapat sisi dari suatu simpul ke dirinya sendiri (loop) disebut graf multi.

Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang sisi-sisinya diberi label dengan beberapa bobot atau angka.

Panjang suatu lintasan pada graf berbobot adalah jumlah bobot semua sisi pada lintasan tersebut.

Graf Berarah (Directed Graph) dan Tidak Berarah (Undirected Graph)

Graf berarah adalah graf yang memiliki sisi dengan arah. Sisi menunjukkan hubungan satu arah, di mana setiap sisi hanya dapat dilalui dalam satu arah.

Sedangkan, Graf tak berarah adalah graf yang memiliki sisi yang tidak memiliki arah. Tepi menunjukkan hubungan dua arah, di mana setiap tepi dapat dilalui di kedua arah.

Graf Terhubung (Connected Graph) dan Graf Tak terhubung (Disconnected Graph)

Graf terhubung adalah graf yang memiliki lintasan atau jalur dari titik mana pun ke titik lain dalam grafik.

Graf tak terhubung adalah graf yang titik-titik terpisah menjadi dua atau lebih grup yang berbeda, di mana tidak mungkin menghubungkan simpul dalam satu grup ke simpul di grup lain dengan melakukan perjalanan sepanjang serangkaian tepi.

Graf Nol (Null Graph)

Graf nol didefinisikan sebagai graf yang hanya terdiri dari simpul-simpul yang terisolasi. Ini berarti graf nol tidak memiliki sisi yang yang menghubungkan titik simpul pada graf. Graf nol dengan n simpul dinotasikan dengan Nn.

Graf Trivial

Graf trivial adalah graf yang hanya memiliki satu simpul.

Graf Reguler (Regular Graph)

Graf Reguler adalah graf yang derajat semua simpulnya sama. Jika derajat semua simpul adalah k, maka disebut graf beraturan k.

Graph Komplit (Complete Graph)

Graf yang setiap pasang simpulnya dihubungkan oleh tepat satu sisi disebut graf lengkap. Ini berisi semua kemungkinan tepi. Graf lengkap dengan n simpul mengandung tepat nC2 sisi dan diwakili oleh Kn.

Graph Sikel (Cycle Graph)

Graf dengan 'n' simpul (di mana, n>=3) dan 'n' tepi membentuk lingkaran 'n' dengan semua sisinya dikenal sebagai graf sikel. Graf yang mengandung setidaknya satu siklus di dalamnya dikenal sebagai graf siklik. Pada graf sikel, derajat setiap simpul adalah 2. Graf siklus yang memiliki n simpul dilambangkan dengan Cn.

Graph Lintasan (Path Graph)

Graf lintasan adalah sebuah pohon dengan dua simpul yang berderajat 1 dan satu simpul lainnya. simpul derajat 2. Oleh karena itu, graf jalur adalah graf yang dapat ditarik sehingga semua simpul dan tepinya terletak pada satu garis lurus.

Graph Roda (Wheel Graph)

Graf roda diperoleh dengan menghubungkan sebuah simpul ke semua simpul dari graf siklus. Dilambangkan dengan Wn, untuk n > 3 dimana n adalah jumlah simpul pada graf. Graf roda dengan n simpul berisi graf siklus dengan orde n – 1 dan semua simpul dari siklus terhubung ke satu simpul . Banyaknya rusuk pada graf Roda, Wn adalah 2n – 2.

Graf Bintang (Star Graf)

Graf bintang adalah jenis graf khusus di mana n-1 simpul memiliki derajat 1 dan satu simpul memiliki derajat n – 1. Ini terlihat seperti n – 1 simpul terhubung ke satu simpul pusat. Graf bintang dengan total n simpul disebut sebagai Sn.

Graph Platonik (Platonic Graph)

Graf platonik muncul dari lima benda padat: tetrahedron, oktahedron, kubus, dodecahedron, dan ikosahedron, di mana titik-titik graf sama dengan titik-titik padatan, dan sisi-sisi graf sama dengan sisi-sisi padatan . Tentu saja, graf-graf ini dapat diubah dalam berbagai cara selama setiap simpul terhubung dengan tepat.

Graph Bipartisi (Bipartite Graph)

Graf bipartisi adalah graf yang himpunan simpulnya dapat dipartisi menjadi dua himpunan sehingga sisi-sisinya hanya berada di antara himpunan, bukan di dalamnya.

Suatu graf G(V,E) disebut graf bipartisi jika himpunan titiknya V(G) dapat diuraikan menjadi dua himpunan bagian tak-kosong yang saling lepas V1(G) dan V2(G) sedemikian rupa sehingga setiap sisi e∈E(G) memiliki satu sambungan terakhir di V1(G) dan titik terakhir lainnya di V2(G).

Partisi V = V1∪V2 disebut bipartisi dari G.

Graph Bipartisi Komplit (Complete Bipartite Graph)

Graf bipartisi lengkap adalah graf bipartisi yang setiap simpul pada himpunan pertama dihubungkan dengan setiap simpul pada himpunan kedua dengan tepat satu sisi. Misal banyak titik pada kedua himpunan bagian pasrtisi adalah r dan s maka banyak titik adalah r+s dan banyak sisi adalah rs.

Merepresentasi Graf kedalam Matriks

Dalam teori graf, representasi graf adalah teknik untuk menyimpan graf ke dalam memori komputer.

Untuk merepresentasikan sebuah graf, kita hanya memerlukan himpunan simpul, dan untuk setiap simpul tetangga dari simpul tersebut (simpul yang terhubung langsung dengannya oleh sebuah sisi). Jika graf merupakan graf berbobot, maka bobot tersebut akan diasosiasikan dengan setiap sisinya.

Ada berbagai cara untuk merepresentasikan grafik secara optimal, tergantung pada kerapatan sisinya, jenis operasi yang akan dilakukan, dan kemudahan penggunaan.

Matriks Adjacency atau Keterhubungan

Matriks Adjacency adalah representasi sekuensial. Digunakan untuk merepresentasikan node mana yang terhubung satu sama lain. Yaitu apakah ada sisu yang menghubungkan titik-titk dalam graf.

Dalam representasi Matriks Adjacency ini, kita harus membangun matriks n×n A. Jika ada sisi dari titik i ke titik j, maka elemen yang sesuai dari A, aij = 1 (bisa lebih dari 1 jika sisi ganda) dan jika tidak aij= 0.

Jika ada graf berbobot maka alih-alih 1 dan 0, kita dapat menyimpan bobot sisinya.

Kelebihan: Representasi lebih mudah diterapkan dan diikuti.

Kekurangan: Dibutuhkan banyak ruang dan waktu untuk mengunjungi semua tetangga dari sebuah simpul, kita harus melintasi semua simpul dalam grafik, yang memakan waktu cukup lama.

Contoh Matriks Adjacency

Matriks Adjacency Graf Tidak Berarah

Matriks Adjacency Graf Berarah

Matriks Adjacency Graf Berbobot

Matriks Incidence atau kebersisian

Dalam representasi matriks Insiden, grafik dapat direpresentasikan menggunakan matriks ukuran: jumlah total simpul × jumlah total tepi.

Artinya, jika suatu graf memiliki 4 simpul dan 6 rusuk, maka graf tersebut dapat direpresentasikan menggunakan matriks kelas 4×6. Dalam matriks ini, kolom mewakili tepi dan baris mewakili simpul.

Matriks ini diisi dengan 0 atau 1 atau -1 (untuk graf berarah). Di mana,

0 digunakan untuk mewakili tepi baris yang tidak terhubung ke simpul kolom.
1 digunakan untuk mewakili tepi baris yang terhubung sebagai tepi keluar ke simpul kolom.
-1 digunakan untuk mewakili tepi baris yang terhubung sebagai tepi masuk ke simpul kolom.

Contoh Matriks Incidence

Graf, Subgraf dan Komplemen Graf

Teori graf merupakan cabang matematika yang mempelajari jaringan titik-titik yang dihubungkan oleh garis. Subjek teori graph berawal dari masalah matematika rekreasi, tetapi telah berkembang menjadi area penelitian matematika yang signifikan, dengan aplikasi dalam kimia, riset operasi, ilmu sosial, dan ilmu komputer.

Sejarah teori graf dapat ditelusuri secara khusus ke tahun 1735, ketika matematikawan Swiss Leonhard Euler memecahkan masalah jembatan Königsberg. Masalah jembatan Königsberg adalah teka-teki lama tentang kemungkinan menemukan jalur di atas setiap satu dari tujuh jembatan yang membentang di sungai bercabang yang mengalir melewati sebuah pulau, tetapi tanpa melintasi jembatan apa pun dua kali. Euler berpendapat bahwa tidak ada jalan seperti itu. Pembuktiannya hanya melibatkan referensi ke susunan fisik jembatan, tetapi pada dasarnya dia membuktikan teorema pertama dalam teori graph.

Definisi Graf

Graf G merupakan pasangan dua himpunan yaitu V(G) himpunan tak kosong yang anggotanya disebut titik dan E(G) himpunan yang anggotanya disebut sisi.

Dari definisi diatas dapat disimpulkan bahwa graf adalah kumpulan titik-titik yang dihubungkan oleh garis dari titik satu ke titik lainnya.

Unsur dan Elemen Graf

Berdasarkan definisi graf, graf memiliki dua elemen yaitu titik dan sisi.

Titik dapat disebut juga vertex, simpul, point, atau node. Titik dalam graf yang dapat mewakili persimpangan jalan, daratan, atau lokasi umum, seperti "kantor" atau "sekolah". Titik sering dihubungkan oleh sisi.

Sisi dapat disebut juga edge, rusuk, ruas atau line. Sisi merupakan garis yang menghubungkan pasangan titik. Sisi dapat mewakili hubungan fisik antara lokasi, seperti jalan, atau hanya bahwa ada rute yang menghubungkan dua lokasi, seperti penerbangan maskapai.

Loop adalah jenis sisi atau garis khusus yang menghubungkan titik ke dirinya sendiri. Loop tidak banyak digunakan dalam grafik jaringan jalan.

Sisi ganda, merupakan dua atau lebih garis yang memiliki 2 ujung titik yang sama. Dalam graf tak berarah, dua atau lebih sisi yang bersinggungan dengan dua simpul yang sama, atau dalam graf berarah, dua atau lebih sisi dengan kedua simpul ekor yang sama dan simpul kepala yang sama.

Adjacent (terhubung/bertetangga), dua titik dikatakan bertetangga, jika terdapat sisi atau garis yang menghubungkan kedua titik tersebut. Di sini, kedekatan simpul dipertahankan oleh sisi tunggal yang menghubungkan kedua simpul tersebut. Dalam suatu graf, dua sisi dikatakan bertetangga, jika terdapat sebuah titik persekutuan di antara kedua sisi tersebut. Titik dengan loop "melihat" dirinya sebagai titik yang berdekatan dari kedua ujung sisi sehingga menambahkan dua, bukan satu ke derajat.

Incident (bersisian), sebuah titik bersisian dengan suatu sisi jika titik tersebut adalah salah satu dari dua titik yang dihubungkan oleh sisi tersebut. Insidence adalah pasanga simpul dan merupakan titik tepi.

Isolated vertex (Titik terisolasi) adalah titik yang tidak memiliki sisi atau garis yang menghubungkan titik tersebut dengan titik lainnya.

Lintasan atau Path merupakan rute di sepanjang tepi graf. Sebuah jalur dapat mengikuti satu sisi secara langsung di antara dua titik, atau mungkin mengikuti beberapa sisi melalui beberapa titik.

Orde atau order suatu graph adalah jumlah simpul atau titik dalam graf tersebut (Orde=n[V(G)]).

Ukuran atau size suatu graph adalah jumlah sisi dalam graf tersebut (Size=n[E(G)]).

Definisi Subgraf

Misalkan G=(V,E) dan H=(W,F) graf. H dikatakan subgraph dari G jika W⊆V dan F⊆E.

Subgraf adalah Graf yang titik dan sisinya merupakan himpunan bagian dari graf lain. Subgraph bisa didapatkan dengan menghapus sisi atau titik pada suatu graf.

Sebuah subgraf dapat dibentuk dengan menghapus sisi atau sebuah sub himpunan dari E(G). Subgraf juga didapat dengan menghapus titik atau sub himpunan dari V(G) dengan menghapus juga sisi yang bersisian (incident) dengan titik yang dihapus.

Komplemen Graf

Komplemen atau invers dari graf G adalah graf H dimana graf H memiliki simpul-simpul yang sama dengan graf G sehingga dua simpul berbeda dari H bertetangga jika dan hanya jika keduanya tidak bertetangga di G.

Misalkan suatu graf lengkap memiliki titik anggota himpunan V sisi yang merupakan anggota himpunan E. Misalkan G adalah graf dengan titik himpunan V dan sisi yang anggota E1 dimana E1 adalah sub himpunan dari E. Misalkan juga graf H memiliki titik himpunan V dan sisi E2 merupakan subhimpunan E dimana E2=E-E1. Graf H disebut komplemen atau inverst graf G.

Komplemen subgraf dari graf G adalah graf yang diperoleh dari G dengan menghapus semua sisi yang ada pada subgraf.

Soal dan Pembahasan OSK Matematika 2015 SMA

1. Banyaknya faktor bulat positif dari 2015 adalah ....

2015=5×13×31

Banyak faktor (1+1)(1+1)(1+1)=8

2. Suatu dadu ditos enam kali. Probabilitas jumlah mata yang muncul 9 adalah ....

1+1+1+1+1+4=9 Banyak susunan=6!/5!=6

1+1+1+1+2+3=9 Banyak susunan=6!/4!=30

1+1+1+2+2+2=9 Banyak susunan=6!/3!3!=20

Banyak kemungkinan dalam 6 pelemparan 66

Peluang jumlah mata 9=56/66

3. Jika (f o g)(x) = 7x+3/5x-9 dan g(x) = 2x–4, maka nilai f(2) adalah ....

(fog)=f(g(x))

2=g(x)

2=2x-4

x=3

(fog)=24/6=4

4. Diberikan trapesium ABCD, dengan AB sejajar DC dan AB = 84 serta DC = 25. Jika trapesium ABCD memiliki lingkaran dalam yang menyinggung keempat sisinya, keliling trapesium ABCD adalah ....

Jika lingkaran dalam menyinggung 4 sisi trapesium sehingga K=2(84+25)=218

5. Diketahui barisan bilangan real a1, a2, … , an, … merupakan barisan geometri. Jika a1 + a4 = 20, maka nilai minimal dari a1 + a2 + a3 + a4 + a5 + a6 adalah ….

a+ar3=20

a(1+r3)=20

S6=a(r6-1)/r-1=a(r3+1)(r2+r+1)

=20(r2+r+1)

Nilai minimum persamaan kuadrat

Min=-(b2-4ac)/4a=3/4

MinS6=20×3/4=15

6. Bilangan bulat x jika dikalikan 11 terletak diantara 1500 dan 2000. Jika x dikalikan 7 terletak antara 970 dan 1275. Jika x dikalikan 5 terletak antara 960 dan 900. Banyaknya bilangan x sedemikian yang habis dibagi 3 sekaligus habis dibagi 5 ada sebanyak ….

1500<x<2000=1500/11<x<2000/11

=136,...<x<181,...

970<7x<1275=138,...<x<182,...

690<5x<900=138<x<180

Sehingga didapat

138<x<180

x habis dibagi 3 dan 5 maka x habis dibagi 15

x={150, 165} ada 2

7. Suatu sekolah mempunyai lima kelompok belajar siswa kelas 11. Kelompok-kelompok belajar itu berturut-turut mengirimkan 2, 2, 2, 3, dan 3 siswa untuk suatu pertemuan. Mereka akan duduk melingkar sehingga setiap siswa memiliki paling sedikit satu teman dari kelompok belajar yang sama yang duduk disampingnya. Banyaknya cara melakukan hal tersebut adalah ….

Banyak kelompok=5

2 orang 1 kelompok juga 3 orang dianggap 1 kelompok karena jika dihitung 2 maka 1 lagi sendirian dan harus duduk bersebelahan dengan salah satu dari 2 orang lainnya.

Maka banyak cara duduk melingkar

=(5-1)!2!2!2!3!3!=4!2!2!2!3!3!

8. Diberikan segitiga ABC dengan sudut ABC = 90o. Lingkaran L1 dengan AB sebagai diameter sedangkan lingkaran L2 dengan BC sebagai diameternya. Kedua lingkaran L1 dan L2 berpotongan di B dan P. Jika AB = 5, BC = 12 dan BP = x, maka nilai dari 240/x adalah

Karena ∠ARB = 90o maka lingkaran berdiameter AB akan melalui titik R.

Karena ∠BRC = 90o maka lingkaran berdiameter BC akan melalui titik R. Jadi, titik R = P.

AC ⋅ BP = AB ⋅ BC

13 ⋅ BP = 5 ⋅ 12

BP=x=60/13

240/x =52

9. Diketahui bilangan real positif a dan b memenuhi persamaan a4 + a2b2 + b4 = 6 dan a2 + ab + b2 = 4 Nilai dari a + b adalah ….

a2+b2=4-ab

(a2+b2)2=(4-ab)2

a4+2a2b2+b4=16-8ab+a2b2

6+a2b2=16-8ab+a2b2

8ab=10

ab=5/4

(a+b)2=4+5/4=21/4

a+b=√21/4

10. Diketahui susunan 4 × 5 titik yang jarak ke kanan sama dan jarak ke bawah sama. Ada berapa segitiga (dengan luas positif) yang titik-titik sudutnya adalah ketiga titik pada susunan tersebut?

Segitiga dibentuk dengan memilih 3 titik dari 20 titik

Banyak segitiga =20C3=1140

Agar memiliki nilai positip maka 3 titik tidak boleh garis lurus

3 titik horisontal=4×5C3=40

3 titk vertikal=5×4C3=20

3 titik diagonal berisi 4 titik=4×4C3=16

3 titik diagonal berisi 3 titik=8×3C3=8

Total segutiga yang tidak memenuhi syarat=40+20+16+8=84

Banyak segitiga yang didapat=1140-80=1056

11. Bilangan x adalah bilangan bulat positif terkecil yang membuat 31n + x . 96n merupakan kelipatan 2015 untuk setiap bilangan asli n. Nilai x adalah ….

31n + x ⋅ 96n ≡ 1n + x ⋅ 1n (mod 5) ≡ 1 + x (mod 5)

Jadi, x ≡ −1 (mod 5) ≡ 4 (mod 5)

31n + x ⋅ 96n ≡ 5n + x ⋅ 5n (mod 13) Jadi, x ≡ −1 (mod 13)

31n + x ⋅ 96n ≡ x ⋅ 3n (mod 31) FPB (3, 31) = 1 maka x ≡ 0 (mod 31)

Teorema sisa cina

x≡ ai (mod ni)

a1=4

a2=-1

a3=0

N=n1×n2×...×ni

N=5×13×31=2015

Ni=N/ni

N1=2015/5=403

N2=2015/13=155

N3=2015/31=65

Nixi≡ 1 mod ni

403x1≡ 3x1 mod 5≡ 1 mod 5

x1≡ 2 mod 5

155x2≡ 12x2 mod 13≡ 1 mod 13

x2≡ 12 mod 13

65x3≡ 3 mod 31≡ 1 mod 31

x3≡ 0 mod 31

x=a1N1x1+a2N2x2+a3×N3x3

=4×403×2-1×155×12+0×65×0

=3224-1860+0=1364

12. Semua bilangan bulat n yang memenuhi 120172222)(22345678nnnnnnnnnnp bulat adalah ….

Semua bilangan bulat n yang memenuhi p(x)=n8+n7+n6+2n5+2n4+2n3+2017/n2-n+1 bulat adalah ….

13. Diketahui a, b, c akar dari persamaan x3 – 5x2 – 9x + 10 = 0. Jika sukubanyak P(x) = Ax3 + Bx2 + Cx – 2015 memenuhi P(a) = b + c, P(b) = a + c, P(c) = a + b, maka nilai dari A + B + C adalah ….

14. Pada segitiga ABC, garis tinggi AD, garis bagi BE dan garis berat CF berpotongan di satu titik. Jika panjang AB = 4 dan BC = 5, dan CD = m2/n2 dengan m dan n relatif prima, maka nilai dari m – n adalah ….

15. Banyaknya bilangan asli n ≤ 2015 yang dapat dinyatakan dalam bentuk n = a + b dengan a, b bilangan asli yang memenuhi a – b bilangan prima dan ab bilangan kuadrat sempurna adalah ….

a>b sehingga

2b<n

2b<n<=2015, n bulat

2b<=2014

b<=1007

Karena a+b=n<=2015 dengan b<=1007 maka

a<=1008

Misalkan FPB(a, b) = d

Maka a = dp dan b = dq

a − b = d(p − q) bilangan prima. Maka d = 1

Karena ab kuadrat sempurna sedangkan FPB (a, b) = 1 maka a dan b masing-masing kuadrat sempurna.

a=x2

b=y2

x dan y bulat

a-b=(x+y)(x-y) prima

Maka x-y=1 dan x+y prima

a<=1008 sehingga x<=31,... karena x bulat maka x<=31

b<=1007 sehingga y<=31,... karena y bulat maka y<=31

x+y<=62 bilangan prima kurang dari 62 ada 18.

Karena FPB a dan b adalah 1 serta a dan b kuadrat sempurna, sehingga tidak mungkin x+y=2.

Maka banyak n=62-1=61

16. Tiga titik berbeda B, C, dan D terletak segaris dengan C diantara B dan D. Titik A adalah suatu titik yang tidak terletak digaris BD dan memenuhi |AB| = |AC| = |CD|. Jika diketahui ||||1||1||1BDCDBDCD maka besar sudut BAC adalah ….

17. Masing-masing kotak pada papan catur berukuran 3 × 3 dilabeli dengan satu angka, yaitu 1, 2, atau 3. Banyaknya penomoran yang mungkin sehingga jumlah angka pada masing-masing baris dan masing-masing kolom habis dibagi oleh 3 adalah ….

A B C

D E F

G H I

Ambil 4 kotak membentuk persegi misal A, B, D dan E.

Masing masing dari 4 kotak dapat diisi 3 kemungkinan 1,2 dan 3

Titik lainnya (C, F, G, H, I) menyesuaikan sehingga hanya dapat diisi oleh 1 kemungkinan sehingga ketiga titik garis lurus habis dibagi 3.

Banyak cara =3×3×3×3=81

18. Pada segilima beraturan ABCDE, diagonal-diagonalnya berpotongan di F, G, H, I dan J. misalkan S1 menyatakan luas segilima ABCDE dan S2 menyatakan luas segilima FGHIJ. Jika knmSS21, dengan k, m, n bilangan bulat positif dan n tidak memiliki faktor kuadrat selain 1, maka nilai dari k + m + n adalah ….

19. Suatu permutasi a1, a2, …, a10 dari {1, 2, …, 10} dikatakan sebagai suatu permutasi yang hampir naik jika terdapat tepat satu indeks i sehingga ai1 > ai. Banyaknya permutasi hampir naik yang mungkin adalah ….

20. Untuk setiap bilangan real a, didefinisikan f(a) sebagai nilai maksimal dari 2 sin Nilai maksimal dari f(a) adalah ….

Soal, Kunci Jawaban dan Pembahasan OSK KSN K SMA Matematika 2016

Soal OSK Matematika SMA 2016

Kunci Jawaban OSK Matematika SMA 2016

Pembahasan Soal ISK Matematika SMA 2016

1. Jika a, b, c, d, e merupakan bilangan asli dengan a < 2b, b < 3c, c < 4d, d < 5e dan e <100, maka nilai maksimum dari a adalah ....

2. Rudi membuat bilangan asli dua digit. Probabilitas bahwa kedua digit bilangan tersebut merupakan bilangan prima dan bilangan tersebut bersisa 3 jika dibagi 7 adalah ....

3. Pada segitiga ABC, titik M terletak pada BC sehingga AB = 7, AM = 3, BM = 5, dan MC =6. Panjang sisi AC adalah ....

4. Diberikan a dan b bilangan real dengan √a-√b=20. Nilai maksimum dari a-5b adalah ....

5. Padasegitiga ABC, titik-titik X, Y, dan Z berturut-turut terletak pada sinar BA, CB, dan AC sehingga BX = 2BA, CY = 2CB, dan AZ = 2AC. Jikaluas ABC adalah 1, maka luas XYZ adalah ....

6. Banyaknya bilangan asli n yang memenuhi sifat hasil jumlah n dan suatu pembagi positif n yang kurang dari n sama dengan 2016 adalah ....

7. Misalkan a adalah bilangan real sehingga polinomial p(x) = x4 +4x+a habis dibagi oleh (x-c)^2 untuk suatu bilangan real c. Nilai a yang memenuhi adalah ....

8. Anak laki-laki dan anak perempuan yang berjumlah 48 orang duduk melingkar secara acak. Banyak minimum anak perempuan sehingga pasti ada enam anak perempuan yang duduk berdekatan tanpa diselingi anak laki-laki adalah ....

9. Misalkan (a, b, c, d, e, f) adalah sebarang pengurutan dari (1, 2, 3, 4, 5, 6). Banyaknya pengurutan sehingga a + c +e > b+d+f adalah ....

11. Segitiga ABC mempunyai panjang sisi AB = 20, AC = 21, dan BC = 29. Titik D dan E terletak pada segmen garis BC, dengan BD = 8 dan EC = 9. Besar DAE adalah ... derajat.

12. Bilangan real t sehingga terdapat dengan tunggal tripel bilangan real (x, y, z) yang memenuhi x2 +2y2 = 3z dan x+y+z = t adalah ....

13. Palindrom adalah bilangan yang sama dibaca dari depan atau dari belakang. Sebagai contoh 12321 dan 32223 merupakan palindrom. Palindrom 5 digit terbesar yang habis dibagi 303 adalah ....

14. Diberikan barisan fang dan fbng dengan an = 1 np n dan bn = 1 1 + 1 n+ q 1 + 1 n , untuk setiap bilangan asli n. Misalkan Sn = a1b1 + a2b2 + ::: + anbn. Banyaknya bilangan asli n dengan n 2016 sehingga Sn merupakan bilangan rasional adalah ....

15. Diberikan persegi ABCD dengan panjang sisi 1. Titik K dan L berturut-turut terletak pada segmen garis BC dan DC sehingga keliling dari 4KCL adalah 2. Luas minimum dari 4AKL adalah ....

16. Banyaknya pasangan terurut bilangan asli (a, b, c) dengan a, b, c {1, 2, 3, 4, 5} sehingga max{a, b, c}< 2min{a, b, c} adalah ....

17. Banyaknya bilangan asli n {1,2,..., 1000} sehingga terdapat bilangan real positif x yang memenuhi x2 +bxc2 = n adalah ....

18. Misalkan x,y,z bilangan real positif yang memenuhi 3logx(3y) = 3log3x(27z) = log3x4(81yz)= 0. Nilai dari x5y4z adalah ....

19. Diberikan empat titik pada satu lingkaran dalam urutan A, B, C, D. Sinar garis AB dan DC berpotongan di E, dan sinar garis AD dan BC berpotongan di F. Misalkan EP dan FQ menyinggung lingkaran berturut-turut di P dan Q. Misalkan pula bahwa EP =60 dan FQ=63, maka panjang EF adalah ....

20. Pada sebuah bidang datar, terdapat 16 garis berbeda dan n titik potong berbeda. Nilai minimal n sehingga dapat dipastikan terdapat 3 kelompok garis yang masingmasing memuat garis-garis berbeda yang saling sejajar adalah ....

Kurva Indiferen

Sebuah alternatif populer untuk analisis utilitas marjinal permintaan adalah Analisis Kurva Indiferen. Ini didasarkan pada preferensi konsumen dan percaya bahwa kita tidak dapat mengukur kepuasan manusia secara kuantitatif dalam istilah moneter . Pendekatan ini memberikan urutan preferensi konsumen daripada mengukurnya dalam bentuk uang.

kurva indiferen (indifference curve) adalah kurva grafik yang berfungsi untuk menggambarkan / menunjukan kombinasi dua barang yang memberikan kepuasan dan utilitas yang sama kepada konsumen. Setiap titik pada kurva indiferen menunjukkan bahwa konsumen acuh tak acuh antara keduanya dan semua titik memberinya utilitas yang sama.

Secara grafis, kurva indiferen digambarkan sebagai cembung miring ke bawah ke titik asal. Grafik tersebut menunjukkan kombinasi dua barang yang dikonsumsi konsumen.

Peta Indiferen

Peta Indiferen adalah sekumpulan Kurva Indiferen. Ini menggambarkan gambaran lengkap dari preferensi konsumen.

Kita tahu bahwa konsumen acuh tak acuh di antara kombinasi yang terletak pada kurva indiferen yang sama. Namun, penting untuk dicatat bahwa ia lebih memilih kombinasi pada kurva indiferen yang lebih tinggi daripada yang ada pada kurva yang lebih rendah.

Ini karena kurva indiferen yang lebih tinggi menyiratkan tingkat kepuasan yang lebih tinggi.

Kemiringan Kurva Indiferen

Kurva indiferen memiliki slope atau kemiringan negatif ke bawah karena, jika utilitas akan tetap sama di semua titik sepanjang kurva, pengurangan jumlah barang pada sumbu vertikal harus diimbangi dengan peningkatan jumlah barang pada sumbu horizontal (atau dan sebaliknya).

Satu set kurva indiferen dapat miring ke atas jika ketika satu set kurva indiferen miring ke atas, itu berarti salah satu barang adalah "buruk" di mana konsumen lebih menyukai lebih sedikit barang daripada lebih banyak barang.

Sifat Karakteristik dan Ciri Kurva Indiferen

Kurva indiferensi memiliki ciri sebagai berikut:

Miring ke bawah ke kanan: Kemiringan ini menandakan bahwa ketika kuantitas satu komoditas dalam kombinasi meningkat, jumlah komoditas lainnya berkurang. Ini penting agar tingkat kepuasan tetap sama pada kurva indiferen.
Selalu cembung ke titik asal : Ini adalah tingkat substitusi marjinal yang semakin berkurang.

Tingkat memberikan bentuk cembung pada kurva indiferen. Namun, ada dua skenario ekstrem:

Dua komoditas adalah substitusi sempurna satu sama lain – Dalam hal ini, kurva indiferen adalah garis lurus, di mana MRS konstan.
Dua barang adalah barang pelengkap yang sempurna – Contoh barang tersebut adalah bensin dan air di dalam mobil. Dalam kasus seperti itu, IC akan berbentuk L dan cembung ke titik asal.

Kurva indiferen tidak pernah berpotongan satu sama lain: Dalam teori konsumen, kurva indiferen tidak dapat bersilangan atau daling berpotongan karena akan melanggar asumsi transitivitas. Kurva yang menunjukkan kombinasi bundel konsumsi yang memberi konsumen utilitas yang sama.
Kurva yang lebih tinggi menunjukkan tingkat kepuasan yang lebih tinggi dibandingkan dengan kurva yang lebih rendah : kurva yang lebih tinggi berarti konsumen lebih menyukai barang daripada tidak.
Kurva tidak menyentuh sumbu : tidak mungkin kurva menyentuh sumbu karena asumsi kami bahwa seorang konsumen mempertimbangkan kombinasi yang berbeda dari dua komoditas dan menginginkan keduanya. Jika kurva menyentuh salah satu sumbu, maka itu berarti dia puas hanya dengan satu komoditas dan tidak menginginkan yang lain, yang bertentangan dengan asumsi kami.

Kurva indiferen untuk barang substitusi sempurna

Kurva indiferen berbentuk L disebut preferensi Leontief dan mewakili fungsi utilitas. Mereka mewakili barang substitusi yang sempurna. Subtitusi sempurna adalah barang yang hanya bernilai ketika dikonsumsi bersama pada rasio tertentu, rasionya adalah.

Garis Anggaran (Budget Line)

Karena kurva indiferen yang lebih tinggi mewakili tingkat kepuasan yang lebih tinggi, konsumen akan mencoba mencapai Kurva setinggi mungkin untuk memaksimalkan kepuasannya. Untuk melakukannya, dia harus membeli lebih banyak barang dan harus bekerja di bawah dua kendala berikut:

Dia harus membayar harga barang dan
Dia memiliki pendapatan terbatas, membatasi ketersediaan uang untuk membeli barang-barang ini.

Garis anggaran menunjukkan kombinasi dua barang yang dapat dikonsumsi konsumen, dengan batasan anggaran. Kurva indiferen menunjukkan kombinasi dua barang yang menghasilkan kepuasan yang sama. Untuk memaksimalkan utilitas, konsumen memilih kombinasi dua barang di mana kurva indiferen bersinggungan dengan garis anggaran.

Jika kurva indiferen konsumen berpotongan dengan budget line / garis anggaran, maka akan selalu mungkin bagi konsumen untuk melakukan pertukaran di sepanjang garis anggaran yang bergerak ke kurva indiferen yang lebih tinggi.

Distribusi Binomial : Eksperimen Binomial, Peluang Binomial, dan Probabilitas Binomial Kumulatif

Distribusi binomial adalah distribusi diskrit yang umum digunakan dalam statistik, bukan distribusi kontinu, seperti distribusi normal . Ini karena distribusi binomial hanya menghitung dua status, biasanya direpresentasikan sebagai 1 (untuk keberhasilan) atau 0 (untuk kegagalan) berdasarkan sejumlah uji coba dalam data. Distribusi binomial, oleh karena itu, mewakili probabilitas untuk x sukses dalam n percobaan, dengan p probabilitas sukses untuk setiap percobaan.

Distribusi binomial merangkum jumlah percobaan, atau pengamatan ketika setiap percobaan memiliki kemungkinan yang sama untuk mencapai satu nilai tertentu. Distribusi binomial menentukan probabilitas pengamatan sejumlah hasil tertentu yang berhasil dalam sejumlah percobaan tertentu.

Eksperimen Binomial

Sebuah percobaan binomial adalah uji statistik yang memiliki sifat sebagai berikut:

Percobaan terdiri dari n percobaan berulang.
Setiap percobaan hanya dapat menghasilkan dua kemungkinan hasil. Kami menyebut salah satu hasil ini sukses dan yang lainnya gagal.
Probabilitas keberhasilan, dilambangkan dengan P , adalah sama di setiap percobaan.
Uji coba bersifat independen ; Artinya, hasil pada satu percobaan tidak mempengaruhi hasil pada percobaan lainnya.

Pertimbangkan eksperimen statistik berikut. Anda melempar koin 2 kali dan menghitung berapa kali koin itu mendarat di kepala. Ini adalah percobaan binomial karena:

Percobaan terdiri dari percobaan berulang. Kami melempar koin 2 kali.
Setiap percobaan hanya dapat menghasilkan dua kemungkinan hasil - kepala atau ekor.
Probabilitas keberhasilan konstan - 0,5 pada setiap percobaan.

Uji coba bersifat independen; artinya, mendapatkan kepala pada satu percobaan tidak mempengaruhi apakah kita mendapatkan kepala pada percobaan lain.

Notasi

Notasi berikut berguna, ketika kita berbicara tentang probabilitas binomial.

x : Jumlah keberhasilan yang dihasilkan dari percobaan binomial.
n : Jumlah percobaan dalam percobaan binomial.
P : Kemungkinan sukses pada percobaan individu.
T : Probabilitas kegagalan pada uji coba individu. (Ini sama dengan 1 - P. )
n! : Faktorial n (juga dikenal sebagai n faktorial).
b ( x ; n, P ): probabilitas Binomial - probabilitas bahwa n -trial hasil percobaan binomial di persis x keberhasilan, ketika probabilitas keberhasilan pada percobaan individu P .
n C r : Banyaknya kombinasi dari n benda, diambil r sekaligus.

Distribusi Binomial

Distribusi binomial dihitung dengan mengalikan probabilitas keberhasilan pangkat dari jumlah keberhasilan dan probabilitas kegagalan pangkat dari perbedaan antara jumlah keberhasilan dan jumlah uji coba. Kemudian, kalikan hasil perkaliannya dengan kombinasi jumlah percobaan dan jumlah keberhasilan.

Misalkan kita melempar koin dua kali dan menghitung jumlah gambar (berhasil). Variabel acak binomial adalah jumlah kepala, yang dapat memiliki nilai 0, 1, atau 2. Distribusi binomial disajikan di bawah ini

Jumlah Gambar	Kemungkinan
0	0.25
1	0,50
2	0.25

Distribusi binomial memiliki properti berikut:

Mean dari distribusi (μ x ) sama dengan n × P .
Varians (σ 2 x ) adalah n × P × (1 - P ).
Standar deviasi (σ x ) adalah sqrt [ n × P × (1 - P )]

Rumus Binomial dan Probabilitas Binomial

The probabilitas binomial mengacu pada probabilitas bahwa hasil percobaan binomial di persis x keberhasilan. Misalnya, pada tabel di atas, kita melihat bahwa probabilitas binomial untuk mendapatkan tepat satu kepala dalam dua lemparan koin adalah 0,50.

Diberikan x , n , dan P , kita dapat menghitung probabilitas binomial berdasarkan rumus binomial:

Formula Binomial. Misalkan percobaan binomial terdiri dari n percobaan dan menghasilkan x sukses. Jika probabilitas keberhasilan pada percobaan individu adalah P , maka probabilitas binomialnya adalah:

b ( x ; n, P ) = nCx P^x × (1 - P)^{n - x}

atau

b ( x ; n, P ) = {n! / [x! (n - x)! ]} × P^x × (1 - P)^{n – x}

Contoh

Misalkan dadu dilempar 5 kali. Berapa probabilitas untuk mendapatkan tepat 2 angka 4?

Solusi: Ini adalah percobaan binomial dimana jumlah percobaan sama dengan 5, jumlah keberhasilan sama dengan 2 percobaan, dan probabilitas keberhasilan pada satu percobaan adalah 1/6 atau sekitar 0,167. Oleh karena itu, probabilitas binomialnya adalah:

b (2; 5, 0,167) = 5 C 2×(0,167) ²×(0,833) ³

b (2; 5, 0,167) = 0,161

Probabilitas Binomial Kumulatif

Sebuah probabilitas binomial kumulatif mengacu probabilitas bahwa variabel acak binomial jatuh dalam kisaran tertentu (misalnya, lebih besar dari atau sama dengan batas bawah yang dinyatakan dan kurang dari atau sama dengan batas atas lain).

Misalnya, kita mungkin tertarik pada probabilitas binomial kumulatif untuk mendapatkan 45 gambar atau kurang dalam 100 lemparan koin (lihat Contoh 1 di bawah). Ini akan menjadi jumlah dari semua probabilitas binomial individual ini.

b (x ≤ 45; 100, 0,5) =b (x = 0; 100, 0,5) + b (x = 1; 100, 0,5) + ... + b (x = 44; 100, 0,5) + b ( x = 45; 100, 0,5)

Contoh 1

Berapa probabilitas untuk mendapatkan 3 gambar atau kurang dalam 5 lemparan koin?

b (x ≤ 45; 100, 0,5) = b (x = 0; 100, 0,5) + b (x = 1; 100, 0,5) +. . . + b (x = 3; 100, 0,5)

b (x ≤ 45; 100, 0,5) = 0,8125

Contoh 2

Probabilitas seorang siswa diterima di perguruan tinggi bergengsi adalah 0,3. Jika 5 siswa dari sekolah yang sama melamar, berapakah probabilitas paling banyak 2 diterima?

Solusi: Untuk mengatasi masalah ini, kami menghitung 3 probabilitas individu, menggunakan rumus binomial. Jumlah dari semua probabilitas ini adalah jawaban yang kita cari. Jadi,

b (x ≤ 2; 5, 0,3) = b (x = 0; 5, 0,3) + b (x = 1; 5, 0,3) + b (x = 2; 5, 0,3)

b (x ≤ 2; 5 , 0,3) = 0,1681 + 0,3601 + 0,3087

b (x ≤ 2; 5, 0,3) = 0,8369