Last Updated on Januari 1, 2023 by prooffic
Postingan kali ini adalah tentang pembahasan soal KNMIPA 2021 Kombinatorika Tingkat Wilayah. Soal untuk bagian kombinatorika pada seleksi tingkat wilayah KNMIPA 2021 kali ini terdiri dari soal isian singkat dan soal uraian sama seperti tahun-tahun sebelumnya. Materi yang terkait khususnya untuk soal tahun ini adalah relasi rekursif dan kombinasi
**Selamat menikmati**
Isian
Soal 1
Solusi dari relasi rekuren $$x_n = 4 x_{n-1} -3 x_{n-2} + 2^n, (n \geq 3) $$dengan syarat $x_1 = 1, x_2=11$ adalah …
Jawab: Relasi rekuren di soal tersebut, yaitu $x_n = 4 x_{n-1} -3 x_{n-2} + 2^n,$ merupakan relasi rekuren tak homogen. Sehingga, kita perlu menentukan solusi homogen dan solusi partikularnya. Untuk itu, kita terlebih dahulu akan menentukan solusi homogennya, yaitu solusi dari $$x_n = 4 x_{n-1} -3 x_{n-2}, (n \geq 3) $$dengan syarat $x_1 = 1, x_2=11.$
Perhatikan bahwa persamaan karakteristik dari relasi rekuren homogen tersebut adalah $$r^2-4r+3=0 \Rightarrow (r-3)(r-1) = 0$$Sehingga solusinya adalah $r=1,3.$ Akibatnya, solusi homogen memiliki bentuk umum $$h_n = c_1 (1)^n+c_2 (3)^n = c_1 + 3^n c_2$$ untuk suatu $c_1, c_2 \in \mathbb{R}.$
Kemudian, dari bentuk $2^n,$ kita bisa melihat bahwa solusi partikularnya akan berbentuk $p_n = A 2^n$ untuk suatu bilangan real $A. $Karena $p_n = A 2^n$ adalah solusi partikular, maka kita dapat mensubtitusikannya ke relasi rekuren $x_n = 4 x_{n-1} -3 x_{n-2} + 2^n$ yang berakibat bahwa $$\begin{aligned} 2^n A – 4 2^{n-1} A + 3 2^{n-2} A &= 2^n \\ 4A-8A+3A &=4 \\ -A & =4 \\ A& = -1\end{aligned} $$Dari sini, solusi partikularnya adalah $p_n = (-4) 2^n = – 2^{n+2}$
Oleh karena itu, relasi rekuren $x_n = 4 x_{n-1} -3 x_{n-2} + 2^n$ memiliki solusi umum berbentuk $$\begin{aligned} x_n & = h_n+p_ n \\ & = c_1 + 3^n c_2 – 2^{n+2}\end{aligned} $$untuk suatu bilangan real $c_1, c_2$ Langkah selanjutnya adalah menentukan masing-masing nilai $c_1, c_2$ dengan memanfaatkan nilai awal yang diberikan.
Karena $x_1 = 1,$ maka $1 = c_1+3c_2 – 2^{1+2} = c_1+3c_2-8$ atau $c_1 + 3 c_2 = 9.$ Subsitusi $x_2 = 11,$ ke $x_n = c_1+3c_2 – 2^{n+2}, $maka diperoleh juga bahwa $11 = c_1 +9c_2 – 2^{2+2} = c_1+9_2-16$ atau $c_1+9c_2=27.$ Dari sini, diperoleh sistem persamaan linear dua variabel dalam $c_1$ dan $c_2$ berikut. $$\begin{aligned} c_1 + 3 c_2 &= 9 \\ c_1+9c_2 &=27 \end{aligned} $$Jika kita menyelesaikannya, kita peroleh $c_1 = 0, c_2 = 3.$ Sehingga, $$\begin{aligned}x_n &= c_1 + 3^n c_2 – 2^{n+2}\\ &=0 + 3^n 3 – 2^{n+2} \\ &=3^{n+1} – 2^{n+2}\end{aligned} $$untuk setiap $n \in \mathbb{N}.$ Jadi, solusi dari relasi rekuren $$x_n = 4 x_{n-1} -3 x_{n-2} + 2^n, (n \geq 3) $$dengan syarat $x_1 = 1, x_2=11$ adalah $$x_n = 3^{n+1} – 2^{n+2} $$ untuk setiap $n \in \mathbb{N}.$
Baca juga:
Pembahasan KNMIPA 2020 Uraian Kombinatorika dan Isian Kombinatorika
Pembahasan KNMIPA 2021 Analisis Real Tingkat Wilayah
Pembahasan KNMIPA 2021 Analisis Kompleks Tingkat Wilayah
Soal 2
Kata sandi tanpa perulangan karakter dibentuk dengan menggunakan huruf kapital. Sebuah kata sandi dikatakan sempurna bila tidak memuat untaian karakter $XYZ$ maupun $ZYX.$ Besarnya peluang untuk membentuk kata sandi sempurna yang terdiri dari atas 8 huruf adalah …
Jawab: Kita akan menentukan banyaknya kata sandi tanpa perulangan karakter yang dapat dibentuk dan kata sandi sempurna yang terdiri dari 8 huruf. Perhatikan bahwa berdasarkan aturan perkalian, maka banyaknya kata sandir tanpa perulangan karakter yang dapat dibentuk dengan banyaknya huruf ada 8 adalah $26!/18!.$ Kemudian, banyaknya kata sandi tanpa perulangan yang memuat untaian karakter $XYZ$ adalah $\frac{23!}{18!} \cdot 6.$ Hasil yang sama juga diperoleh untuk banyaknya kata sandi tanpa perulangan yang memuat untaian karakter $ZYX.$
Berdasarkan prinsip inklusi-eksklusi, diperoleh bahwa banyaknya kata sandi sempurna adalah $$\begin{aligned}\frac{26!}{18!} – \left( \frac{23!}{18!} \cdot 6+\frac{23!}{18!} \cdot 6 \right) &=\frac{26!}{18!} – 2 \frac{23!}{18!} \cdot 6 \end{aligned} $$Dari sini, peluang untuk membentuk kata sandi sempurna yang terdiri dari atas 8 huruf adalah $$\begin{aligned} \frac{\frac{26!}{18!} – 2 \frac{23!}{18!} \cdot 6}{26!/18!} & = 1 – \frac{2 \cdot 6}{26\cdot 25 \cdot 24} \\ &=1- \frac{1}{1300}\\ &=\frac{1299}{1300}\end{aligned}$$
Uraian
Soal
Pengubinan dengan panjang $n \geq 1$ adalah sebuah cara menutupi lantai berukuran $1 \times n$ dengan menggunakan ubin $1 \times 1$ berwarna merah, putih, hijau, kuning, atau biru. Sebuah pengubinan dikatakan ideal bila pengubinan menggunakan genap ubin merah, genap ubin hijau, dan ganjil ubin biru. Tentukan banyaknya pengubinan ideal dengan panjan $n.$
Jawab: Perhatikan bahwa masalah ini melibatkan permutasi sehingga kita akan menggunakan fungsi pembangkit eksponensial untuk menyelesaikannya, yaitu untuk menentukan banyaknya pengubinan ideal dengan panjang $n$. Sebelumnya, kita telah mengetahui bahwa $$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!} $$Selanjutnya, kita akan menentukan fungsi pembangkit untuk masing-masing warna ubin. Untuk ubin berwarna merah dan hijau, fungsi pembangkitnya adalah $$1+ \frac{x^2}{2!} + \frac{x^4}{4!}+\cdots= \frac{e^x + e^{-x}}{2}$$Fungsi pembangkit untuk ubin biru adalah $$x+ \frac{x^3}{3!} + \frac{x^5}{5!}+\cdots = \frac{e^x – e^{-x}}{2}$$
Sedangkan, fungsi pembangkit untuk ubin putih dan kuning adalah $$1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots = e^x $$Oleh karena itu, fungsi pembangkit untuk permasalahan tersebut adalah$$ P(x)= \left( 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \right)^2 \left(1+ \frac{x^2}{2!} + \frac{x^4}{4!}+\cdots \right)^2 \left( x+ \frac{x^3}{3!} + \frac{x^5}{5!}+\cdots \right) $$Sehingga, $$\begin{aligned} P(x) &= \left( e^x \right)^2 \left( \frac{e^x + e^{-x}}{2} \right)^2 \left( \frac{e^x – e^{-x}}{2} \right) \\&= (e^{2x}) \frac{e^{3x}+e^x-e^{-x}-e^{-3x}}{8} \\&= \frac{1}{8} \left(e^{5x}+e^{3x}-e^x-e^{-x}\right) \\&=\frac{1}{8} \left( \sum_{n=0}^{\infty} \frac{(5x)^n}{n!} + \sum_{n=0}^{\infty} \frac{(3x)^n}{n!} – \sum_{n=0}^{\infty} \frac{(x)^n}{n!} – \sum_{n=0}^{\infty} \frac{(-x)^n}{n!} \right) \\&= \frac{1}{8} \left( \sum_{n=0}^{\infty} (5^n) \frac{x^n}{n!} + \sum_{n=0}^{\infty} (3^n) \frac{x^n}{n!} – \sum_{n=0}^{\infty} \frac{x^n}{n!} – \sum_{n=0}^{\infty} (-1)^n \frac{x^n}{n!} \right) \\ &= \frac{1}{8} \sum_{n=0}^{\infty} \left( 5^n+3^n-1-(-1)^n \right) \frac{x^n}{n!}\end{aligned}$$
Banyaknya pengubinan ideal dengan panjang $n$ adalah koefisien dari $x^n /n!$ dari $P(x).$ Jadi, banyaknya pengubinan ideal dengan panjang $n$ adalah $ 5^n+3^n-1-(-1)^n.$
Demikian postingan kali ini tentang pembahasan soal KNMIPA 2021 Kombinatorika Tingkat Wilayah. Jika Anda tertarik dengan pembahasan ONMIPA/KNMIPA lainnya, silahkan ke sini. Jika Anda tertarik dengan topik/materi lainnya, silahkan ke sini. Semoga membantu. Sekian dan terima kasih.
