Pembahasan Soal ON MIPA-PT Matematika Tahun 2018 Kombinatorika (Isian)

Dalam tulisan ini, kita akan membahas soal Kombinatorika dalam ON MIPA-PT Matematika Tahun 2018. Soal kombinatorika terdiri dari delapan soal isian singkat dan tiga soal uraian. Dalam tulisan ini, kita akan membahas soal isian singkat.

INFORMASI
Pembahasan soal uraian kombinatorika telah tersedia. Silakan kunjungi link berikut.
Pembahasan Soal ON MIPA-PT Matematika Tahun 2018 Kombinatorika (Uraian)
Nomor 1

Banyaknya subset dari himpunan \{ 1,2,\cdots,25 \} yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalah…

PEMBAHASAN
Misalkan K adalah himpunan dengan m anggota dan K adalah subset dari M dengan k anggota. Himpunan K dapat dinyatakan sebagai barisan biner dengan panjang m. Angka 1 menyatakan anggota yang bersesuaian merupakan anggota subset dan angka 0 menyatakan anggota yang bersesuaian bukan anggota subset. Misalnya kita punya himpunan M=\{a,b,c,d,e\}. Subset K=\{a,c,d\} dari M dapat dinyatakan sebagai barisan biner 10110.

Diketahui himpunan \{ 1,2,\cdots,25 \}. Akan dicari banyaknya subset yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan. Dalam konteks barisan biner, soal ini dapat dipandang sebagai banyaknya barisan biner dengan panjang 25 yang terdiri dari 3 angka 1 dan 22 angka 0, dimana angka 1 tidak boleh berdampingan.

Pertama, tuliskan 22 angka 0 secara berurutan. Agar angka 1 tidak berdampingan, ketiga angka 1 harus ditempatkan di antara dua angka 0 atau pada ujung barisan. Banyaknya posisi yang mungkin untuk menempatkan angka 1 adalah 23 (2 pada bagian ujung dan 21 pada bagian tengah). Banyaknya cara menempatkan 3 objek pada 23 tempat yang tersedia adalah

    \[{23 \choose 3}=\frac{23!}{(23-3)!3!}=1771\]

Jadi, banyaknya subset dari himpunan \{ 1,2,\cdots,25 \} yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalah 1771.

Nomor 2

Sebuah klub bulu tangkis mempunyai 35 anggota terdiri dari 15 anak laki-laki dan 20 anak perempuan. Klub akan membentuk 10 pasangan ganda campuran. Banyaknya cara yang mungkin untuk membentuk 10 pasangan ganda campuran adalah…

PEMBAHASAN
Pertama, pilih masing-masing 10 anak laki-laki dan perempuan yang akan dipasangkan. Banyaknya cara adalah {15 \choose 10}{20 \choose 10}. Selanjutnya, anak laki-laki pertama dapat dipasangkan dengan 1 dari 10 anak perempuan, anak laki-laki kedua dengan 1 dari 9 anak perempuan yang tersisa, dan seterusnya, sampai pada anak laki-laki kesepuluh. Berdasarkan aturan perkalian, ada sebanyak 10! cara.
Jadi, banyaknya cara yang mungkin untuk membentuk 10 pasangan ganda campuran adalah 10!{15 \choose 10}{20 \choose 10}.

Nomor 3

Sebuah toko roti memproduksi 8 jenis donat. Donat dikemas dalam kotak berisi 12 buah donat. Banyaknya cara untuk mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis adalah…

PEMBAHASAN
Misalkan x_i menyatakan banyaknya donat jenis i dalam kotak, untuk 1 \leq i \leq 8. Banyaknya cara mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis sama dengan banyaknya solusi bilangan bulat dari

    \[x_1+x_2+\cdots+x_8=12, \quad x_i \geq 1, \: 1 \leq i \leq 8\]

Banyaknya solusi persamaan persamaan di atas, sama dengan banyaknya solusi bilangan bulat non negatif dari

    \[y_1+y_2+\cdots+y_8=4\]

dengan y_i=x_i-1, untuk 1 \leq i \leq 8, yaitu sebanyak

    \[{4+8-1 \choose 4}={11 \choose 4}=\frac{11!}{(11-4)!4!}=330\]

Jadi, banyaknya cara untuk mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis adalah 330.

Nomor 4

Untuk bilangan bulat positif n \geq 2, nilai dari \sum_{k=2}^n (-1)^k k {n \choose k} adalah…

PEMBAHASAN
Sebelum menyelesaikan soal ini, ada beberapa hal yang perlu kita ketahui.

    \[k {n \choose k}=n {n-1 \choose k-1} \quad \ldots \textbf{(1)}\]

Bukti

    \begin{align*} k {n \choose k} &= k \frac{n!}{(n-k)!k!} \\ &= k \frac{n(n-1)!}{(n-k)!k(k-1)!} \\ &= \frac{n(n-1)!}{(n-k)!(k-1)!} \\ &= n\frac{(n-1)!}{((n-1)-(k-1))!(k-1)!} \\ &= n {n-1 \choose k-1} \end{align*}

Terbukti.

    \[{n \choose k}={n-1 \choose k-1}+{n-1 \choose k} \quad \ldots \textbf{(2)}\]

Bukti
Misal A=\{ 1,2,3,\cdots,n \}. Banyaknya subset dari A yang terdiri dari k anggota dapat dihitung dengan dua cara.
Cara I: Kita dapat memilih k anggota dari himpunan A yang akan menjadi anggota subset. Banyaknya subset yang mungkin adalah {n \choose k}.
Cara II: Tinjau salah satu anggota A, misalnya 1. Ada dua kasus yang mungkin dalam membentuk subset dengan k anggota, yaitu 1) 1 merupakan anggota subset, dan 2) 1 bukan anggota subset. Jika 1 merupakan anggota subset, maka ada sebanyak {n-1 \choose k-1} cara untuk memilih k-1 anggota lainnya. Sedangkan, jika 1 bukan anggota subset, maka ada sebanyak {n-1 \choose k} cara untuk membentuk subset dengan k anggota tersebut. Berdasarkan aturan penjumlahan, banyaknya subset yang mungkin adalah {n-1 \choose k-1}+{n-1 \choose k}.
Berdasarkan kedua cara di atas, dapat disimpulkan bahwa {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.
Terbukti.

    \[\sum_{k=2}^m(-1)^k {m \choose k}=m-1 \quad \ldots \textbf{(3)}\]

Bukti: Berdasarkan teorema binomial, diperoleh

    \begin{align*} (1+(-1))^n &= \sum_{k=0}^m 1^{m-k} (-1)^k {m \choose k} \\ 0^n &= \sum_{k=0}^m (-1)^k {m \choose k} \\ 0 &= (-1)^0 {m \choose 0} + (-1)^1 {m \choose 1} + \sum_{k=2}^m (-1)^k {m \choose k} \\ 0 &= 1-m+\sum_{k=2}^m (-1)^k {m \choose k} \end{align*}

Tambahkan m-1 pada kedua ruas, sehingga diperoleh

    \[\sum_{k=2}^m(-1)^k {m \choose k}=m-1\]

Terbukti.

Itulah tiga hal yang perlu kita ingat, sebelum menjawab soal ini.
Berdasarkan sifat \textbf{(1)}, diperoleh

    \begin{align*} \sum_{k=2}^n (-1)^k k {n \choose k} &= \sum_{k=2}^n (-1)^k n {n-1 \choose k-1} \\ &= n\sum_{k=2}^n (-1)^k {n-1 \choose k-1} \end{align*}

Berdasarkan sifat \textbf{(2)}, diperoleh {n-1 \choose k-1}={n \choose k}-{n-1 \choose k}, sehingga

    \begin{align*} \sum_{k=2}^n (-1)^k k {n \choose k} &= n\sum_{k=2}^n (-1)^k \left[ {n \choose k}-{n-1 \choose k} \right] \\ &= n \left[ \sum_{k=2}^n (-1)^k {n \choose k}-\sum_{k=2}^n (-1)^k {n-1 \choose k} \right] \\ &= n \left[ \sum_{k=2}^n (-1)^k {n \choose k}-\left(\sum_{k=2}^{n-1} (-1)^k {n-1 \choose k} + (-1)^n {n-1 \choose n} \right) \right] \end{align*}

Berdasarkan sifat \textbf{(3)}, diperoleh \sum_{k=2}^n (-1)^k {n \choose k}=n-1 dan \sum_{k=2}^{n-1} (-1)^k {n-1 \choose k}=(n-1)-1. Akibatnya

    \begin{align*} \sum_{k=2}^n (-1)^k k {n \choose k} &= n \left[ (n-1)-(n-1-1)+0 \right] \\ &= n \cdot 1 \\ &= n \end{align*}

Jadi, \sum_{k=2}^n (-1)^k k {n \choose k} = n.

Nomor 5

Misalkan b_n adalah banyaknya untaian atas n huruf yang dapat dibentuk dengan menggunakan A, B, dan C sedemikian sehingga bila huruf A muncul bukan sebagai huruf akhir pada untaian, maka A harus segera diikuti oleh B. Relasi rekurensi dari barisan \{ b_n \} adalah…

PEMBAHASAN
Misalkan untaian yang memenuhi disebut untaian cantik. Untaian cantik atas n huruf dapat diawali dengan huruf A, B, atau C.
Kasus I: Huruf pertama adalah A. Berdasarkan syarat untaian cantik, huruf berikutnya harus B. Sehingga untaian ini harus diawali dengan AB. Banyaknya untaian yang memenuhi sama dengan banyaknya untaian cantik atas n-2 huruf, yang dinyatakan sebagai b_{n-2}. Mengapa? Karena yang kita lakukan adalah menambahkan AB pada awal setiap untaian cantik atas n-2 huruf. Jadi, banyaknya untaian cantik pada kasus I adalah b_{n-2}.
Kasus II: Huruf pertama adalah B. Tidak ada batasan mengenai huruf berikutnya, sehingga banyaknya untaian cantik dengan huruf pertama B sama dengan banyaknya untaian cantik atas n-1 huruf, yaitu sebanyak b_{n-1}.
Kasus III: Huruf pertama adalah C. Dengan cara yang sama dengan kasus II, diperoleh banyaknya untaian cantik pada kasus III adalah b_{n-1}.

Berdasarkan tiga kasus di atas, banyaknya untaian cantik atas n huruf adalah b_n=2b_{n-1}+b_{n-2}.

Untuk nilai awal, kita memerlukan nilai b_1 dan b_2. Untuk n=1, banyaknya untaian cantik adalah 3, yaitu A, B, dan C. Untuk n=2, banyaknya untaian cantik adalah 7, yaitu AB, BA, BB, BC, CA, CB, dan CC. Jadi, relasi rekurensi dari barisan \{ b_n \} adalah

    \[b_n=2b_{n-1}+b_{n-2}, \: \text{ untuk } n \geq 3, \: \text{ dengan } b_1=3 \text{ dan } b_2=7\]

Nomor 6

Diberikan permutasi \pi = \left( \begin{array}{cccc} 1 & 2 & \cdots & n \\ \pi (1) & \pi (2) & \cdots & \pi (n) \end{array} \right) atas himpunan \{ 1,2,\cdots,n \} dengan n \geq 7. Banyaknya permutasi \pi sehingga \pi (1)=5 atau \pi (3)=7 atau \pi (6)=2 adalah…

PEMBAHASAN
Kita akan menyelesaikan soal ini dengan prinsip inklusi dan eksklusi.
Misalkan S adalah himpunan semua permutasi \pi yang mungkin atas \{ 1,2,\cdots,n \}. Banyaknya permutasi yang mungkin adalah S_0=n!. Permutasi \pi \in S dikatakan memenuhi sifat

  1. c_1, jika \pi (1)=5,
  2. c_2,jika \pi (3)=7,
  3. c_3, jika \pi (6)=2.

Jawaban dari soal ini adalah N(\bar{c_1}\bar{c_2}\bar{c_3}).

Kita akan menghitung S_1 yang nilainya sama dengan N(c_1)+N(c_2)+N(c_3).
Kita mulai dengan N(c_1). Permutasi \pi memenuhi sifat c_1, jika \pi (1)=5. Nilai \pi (2) yang mungkin adalah sebanyak (n-1), nilai \pi (3) sebanyak (n-2), dan seterusnya, Berdasarkan aturan perkalian, diperoleh N(c_1)=(n-1)!. Dengan cara yang sama, diperoleh N(c_2)=N(c_3)=(n-1)!. Sehingga

    \[S_1=N(c_1)+N(c_2)+N(c_3)=3(n-1)!\]

Selanjutnya, kita akan menghitung S_2 yang nilainya sama dengan N(c_1c_2)+N(c_1c_3)+N(c_2c_3). Dengan perhitungan yang serupa dengan S_1, diperoleh

    \[S_2=N(c_1c_2)+N(c_1c_3)+N(c_2c_3)=3(n-2)!\]

Terakhir, kita akan menghitung S_3 yang nilainya sama dengan N(c_1c_2c_3). Banyaknya permutasi \pi yang mungkin, dengan \pi (1)=5, \pi (3)=7, dan \pi (6)=2 adalah sebanyak (n-3)!. Sehingga

    \[S_3=N(c_1c_2c_3)=(n-3)!\]

Berdasarkan prinsip inklusi dan eksklusi, diperoleh

    \begin{align*} N(\bar{c_1}\bar{c_2}\bar{c_3}) &= S_0-S_1+S_2-S_3 \\ &= n!-3(n-1)!+3(n-2)!-(n-3)! \\ &= (-1)^0 {3 \choose 0} (n-0)! + (-1)^1 {3 \choose 1} (n-1)! + (-1)^2 {3 \choose 2} (n-2)! + (-1)^3 {3 \choose 3} (n-3)! \\ &= \sum_{k=0}^3 (-1)^k {3 \choose k} (n-k)! \end{align*}

Jadi, banyaknya permutasi \pi sehingga \pi (1)=5 atau \pi (3)=7 atau \pi (6)=2 adalah \sum_{k=0}^3 (-1)^k {3 \choose k} (n-k)!.

Nomor 7

Dalam bentuk paling sederhana, fungsi pembangkit eksponensial (exponential generating function) dari barisan (0!,1!,2!,3!,\cdots,n!,\cdots) adalah…

PEMBAHASAN
Berdasarkan definisi fungsi pembangkit eksponensial diperoleh

    \begin{align*} f(x) &= 0! + 1!x + 2!\frac{x^2}{2!} + 3!\frac{x^3}{3!} + \cdots + n!\frac{x^n}{n!} + \cdots \\ &= 1+x+x^2+x^3+\cdots+x^n+\cdots \end{align*}

Untuk \lvert x \rvert < 1, diperoleh

    \[f(x)=\frac{1}{1-x}\]

Jadi, fungsi pembangkit eksponensial dari barisan (0!,1!,2!,3!,\cdots,n!,\cdots), dalam bentuk paling sederhana adalah f(x)=\frac{1}{1-x}, untuk \lvert x \rvert < 1.

Nomor 8

Diberikan sebuah graf sederhana G atas 6 titik v_1,v_2,\cdots,v_6. Bila G mempunyai 8 sisi dan derajat dari titk-titik v_1,v_2,\cdots,v_5 masing-masing adalah 1, 3, 3, 3, dan 2, maka derajat dari titik v_6 adalah…

PEMBAHASAN
Sebelum menjawab soal ini, kita perlu mengingat teorema berikut:

Teorema
Jika G=(V,E) adalah graf tak berarah atau graf ganda, maka \sum_{v \in V} \text{deg}(v)=2 \lvert E \rvert.

Diketahui G=(6,8) dan derajat dari 5 titik pada graf. Graf sederhana merupakan graf tak berarah, sehingga berdasarkan teorema di atas, diperoleh

    \begin{align*} \sum_{v \in V} \text{deg}(v) &= 2 \lvert E \rvert \\ 1+3+3+3+2+\text{deg}(v_6) &= 2 \cdot 8 \\ 12+\text{deg}(v_6) &= 16 \\ \text{deg}(v_6) &= 4 \end{align*}

Jadi, derajat dari titik v_6 adalah 4.

Semoga bermanfaat! Jika ada yang perlu diperbaiki atau anda punya solusi yang berbeda, silakan beritahu melalui komentar.

29 Responses

  1. Efrin says:

    Pak boleh bagi file soal kimia 2018 nggak? Email saya efrinsitumorang21@gmail.com

  2. NN says:

    MaasyaaAllah…
    Tulisan yang sangat bagus
    Oh ya di no.5 mungkin yang dimaksud b_n=2b_{n-1}+b_{n-2}.
    Tapi, afwan kalau saya salah 🙂

  3. RIKO says:

    Pak, bisa minta file PDF dari jawabannya gak?

  4. Iqlima says:

    Pak saya boleh minta soal on mipa tahun 2018 yang fisika?

  5. Ridwan says:

    Boleh minta file soal ONMIPA 2018 Pak?. Ini email saya. ridwanmath15@gmail.com

  6. Eyuana says:

    Wah rumusnya rumit juga ya. Berarti kita harus ngehafalin rumus teorama dulu

  7. Rani says:

    Halo pak,mau tanyak. Soal uraiannya belum bisa di lihat ya pak? Kalau ada saya boleh di kirimin sama bapak? Trims

  8. Feifei says:

    Wah sy udah lama gak liat soal mat asik juga sleseinnya daripada nganggur.

  9. Kurnia says:

    Permisi bapak, apa bapak punya juga soal-soal onmipa 2018 untuk bidang lainnya, kimia misalnya?

  10. Jusuf situmeang says:

    Soal onmipa 2018 ada ngak sama bapak?
    Bagilah file nya pak?

  11. Siapa ya says:

    Mantaappppp

Leave a Reply

Your e-mail address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.