KimiaMath

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

Oleh Aiz — 21 Juni 2019

Kategori: Olimpiade Matematika

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.

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{aligned} 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{aligned}$$ 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{aligned} (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{aligned}$$ 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{aligned} \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{aligned}$$

Berdasarkan sifat $\textbf{(2)}$, diperoleh ${n-1 \choose k-1}={n \choose k}-{n-1 \choose k}$, sehingga $$\begin{aligned} \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{aligned}$$

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{aligned} \sum_{k=2}^n (-1)^k k {n \choose k} &= n \left[ (n-1)-(n-1-1)+0 \right] \\ &= n \cdot 1 \\ &= n \end{aligned}$$ 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{aligned} 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{aligned}$$ 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{aligned} 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{aligned}$$

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{aligned} \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{aligned}$$ 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.

Komentar