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 8 soal isian singkat dan 3 soal uraian. Dalam tulisan ini, kita hanya akan membahas soal isian singkat. Tiga soal uraian akan dibahas dalam tulisan terpisah, Insya Allah.

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-1}.

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-1}, \: \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.

You may also like...

1 Response

  1. Siapa ya says:

    Mantaappppp

Leave a Reply

Your email address will not be published. Required fields are marked *

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