Soal dan Pembahasan KNMIPA 2020 Kombinatorika Isian Singkat

Last Updated on Juli 28, 2021 by prooffic

Pembahasan kali ini adalah terkait dengan soal dan pembahasan KNMIPA 2020 Kombinatorika Isian Singkat. Pembahasan jawabannya menggunakan teknik yang terdapat di buku Ralph P. Grimaldi “Discrete and combinatorial mathematics an applied introduction”, terutama terkait dengan persamaan rekursif dan prinsip kombinasi.

**Selamat menikmati**

Soal 1

Banyaknya solusi bilangan bulat non negatif dari persamaan $$a+b+c=13$$ dengan $a\leq4, 2\leq b \leq 5$, dan $1\leq c\leq 6$ adalah …

Jawab: Kita akan menggunakan dua pendekatan berbeda untuk menyelesaikan soal tersebut. Meskipun pendekatannya berbeda, tetapi nantinya akan diperoleh hasil yang sama.

Pertama, kita akan menggunakan prinsip inklusi eksklusi. Kita mengubah permasalahan tersebut menjadi permasalahan yang berkaitan dengan masalah menentukan banyaknya solusi bilangan bulat tak negatif untuk $x_1 + … + x_k = n$ dengan $n,k \in \mathbb{N}$. Sebagaimana kita ketahui bahwa banyaknya solusi yang dimaksud adalah ${n+k-1} \choose {n}$. Untuk itu, misalkan $$x=a, y=b-2, z=c-1$$ Maka, $$x+y+z=10$$ dengan $0 \leq x \leq4,$ $0 \leq y \leq 3$ dan $0 \leq z \leq 5.$

Selanjutnya, misalkan:

• $n(A)$ adalah banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $x \geq 5,$ $y \geq 0$ dan $z \geq 0$.
• $n(B)$ adalah banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $x \geq 0,$ $y \geq 4$ dan $z \geq 0$.
• $n(C)$ adalah banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 6$.
• $n(A \cap B)$ menyatakan banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $x \geq 5,$ $y \geq 4$ dan $z \geq 0$.
• $n(A \cap C)$ menyatakan banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $x \geq 5,$ $y \geq 0$ dan $z \geq 6$.
• $n(B \cap C)$ menyatakan banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $x \geq 0,$ $y \geq 4$ dan $z \geq 6$.
• $n(A \cap B \cap C)$ menyatakan banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $x \geq 5,$ $y \geq 4$ dan $z \geq 6$.

Berdasarkan prinsip inklusi dan eksklusi, jika $n(\bar{A} \cap \bar{B} \cap \bar{C})$ menyatakan banyaknya solusi bulat yang memenuhi $$x+y+z=10$$ dengan $0 \leq x \leq4,$ $0 \leq y \leq 3$ dan $0 \leq z \leq 5$, maka $$n(\bar{A} \cap \bar{B} \cap \bar{C})=n(S)-(n(A)+n(B)+n(C))+(n(A \cap B)+n(A \cap C)+n(B \cap C))-n(A \cap B \cap C)$$

Kemudian, akan ditentukan masing-masing nilai tersebut.

• Dengan mengubah permasalahan $x+y+z=10$ dengan $x \geq 5,$ $y \geq 0$ dan $z \geq 0$ sama seperti sebelumnya, maka banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 5,$ $y \geq 0$ dan $z \geq 0$ adalah sama dengan banyaknya solusi bulat yang memenuhi $x+y+z=5$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 0$, yaitu ${5+3-1}\choose{5}$ $= 21$. Sehingga $n(A)=21$.
• Dengan argumen yang sama, maka banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 0,$ $y \geq 4$ dan $z \geq 0$ adalah sama dengan banyaknya solusi bulat yang memenuhi $x+y+z=6$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 0$, yaitu ${6+3-1} \choose {6} $ $= 28$. Sehingga $n(B)=28$.
• Banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 6$ adalah sama dengan banyaknya solusi bulat yang memenuhi $x+y+z=4$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 0$, yaitu ${4+3-1} \choose {4} $ $= 15$. Sehingga $n(C)=15$.
• Banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 5,$ $y \geq 4$ dan $z \geq 0$ adalah sama dengan banyaknya solusi bulat yang memenuhi $x+y+z=1$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 0$, yaitu ${1+3-1} \choose {1} $ $= 3$. Sehingga $n(A \cap B)=3$.
• Banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 5,$ $y \geq 0$ dan $z \geq 6$ adalah $0$. Sehingga $n(A \cap C)=0$.
• Banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 0,$ $y \geq 4$ dan $z \geq 6$ adalah sama dengan banyaknya solusi bulat yang memenuhi $x+y+z=0$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 0$, yaitu ${0+3-1} \choose {0}$ $ = 1$. Sehingga $n(B \cap C)=1$.
• Banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 5,$ $y \geq 4$ dan $z \geq 6$ adalah $0$. Sehingga $n(A \cap B \cap C)=0$.

Sedangkan $n(S)$ adalah banyaknya solusi bulat yang memenuhi $x+y+z=10$ dengan $x \geq 0,$ $y \geq 0$ dan $z \geq 0$, yaitu ${10+3-1} \choose {10}$ $ = 66$. Dari sini, $$\begin{aligned} n(\bar{A} \cap \bar{B} \cap \bar{C}) &=n(S)-(n(A)+n(B)+n(C))+(n(A \cap B)+n(A \cap C)+n(B \cap C))-n(A \cap B \cap C) \\ & = 66 – (21 +28 +15) + (3 + 0+1) – 0 \\ &= 6 \end{aligned}$$

Jadi, banyaknya solusi bilangan bulat non negatif dari persamaan $a+b+c=13$ dengan $a\leq4, 2\leq b \leq 5$, dan $1\leq c\leq 6$ adalah 6.

Kedua, kita dapat menggunakan fungsi pembangkit untuk menyelesaikan soal tersebut. Dari syarat yang diberikan, fungsi pembangkit untuk variabel $a$ adalah $$P_a (x)=1+x+x^2+x^3+x^4$$ Fungsi pembangkit dari variabel $b$ adalah $$P_b (x)=x^2+x^3+x^4+x^5$$ Sedangkan, fungsi pembangkit untuk variabel $c$ adalah $$P_c (x)=1+x+x^2+x^3+x^4+x^5+x^6$$ Dengan mengalikan ketiga polinom tersebut, kita peroleh fungsi pembangkit dari permasalahan tersebut adalah $$\begin{aligned}P_(x) &= P_a (x)\cdot P_b (x) \cdot P_c (x) \\&=x^3+3x^4+6x^5+10x^6+14x^7+17x^8+18x^9+17x^{10}+14x^{11}+10x^{12}+6x^{13}+3x^{14}+x^{15}\end{aligned}$$

Banyaknya solusi dari permasalahan tersebut adalah koefisien dari $x^{13}$. Jadi, banyaknya solusi bilangan bulat non negatif dari persamaan $a+b+c=13$ dengan $a\leq4, 2\leq b \leq 5$, dan $1\leq c\leq 6$ adalah 6.

Baca Juga: Pembahasan Soal KNMIPA 2020 Uraian Kombinatorika

Soal 2 

Solusi dari relasi rekuren $u_n = 3u_{n-2} – 2u_{n-3}, (n \geq 3),$ dengan syarat awal $u_0 = 1, u_1 = 0$ dan $u_2 = 0$ adalah …

Jawab: Pembahasan soal KNMIPA 2020 Kombinatorika isian singkat selanjutnya menyangkut materi mengenai relasi rekursif. Persamaan karakteristik dari relasi rekursif tersebut adalah $$\begin{aligned}r^3 – 3r + 2 &= 0 \\ (r-1)^{2} (r+2) &= 0 \end{aligned}$$Solusi dari relasi rekuren tersebut adalah $r=2$ serta $r=1$. Oleh karena itu, $u_n$ akan berbentuk $$\begin{aligned} u_n &= c_0 (1)^n + c_1 n (1)^n + c_2 (-2)^n \\&=c_0 +c_1 n +c_2 (-2)^n \end{aligned}$$Selanjutnya, akan ditentukan nilai dari masing-masing koefisien tersebut dengan menggunakan informasi dari syarat awal yang diberikan.

• Untuk $u_0 = 1$, maka $c_0 + c_2 = 1$
• Untuk $u_1 = 0$, maka $c_0 + c_1 – 2c_2 = 0$
• Untuk $u_2 = 0$, maka $c_0 + 2c_1 + 4c_2 = 0$

Sehingga diperoleh sistem persamaan linear tiga variabel. Dengan menyelesaikan sistem tersebut, maka $c_0 = 8/9, c_1 = -6/9, c_2 = 1/9$. Dengan demikian, $$u_n = \frac{8}{9} + \frac{-6}{9}n + \frac{1}{9} (-2)^n = \frac{1}{9} (8-6n+(-2)^n)$$

Jadi, $u_n = \frac{1}{9} (8-6n+(-2)^n)$ untuk setiap n bilangan bulat tak negatif.

Demikian kali ini tentang Pembahasan soal KNMIPA 2020 Kombinatorika. Jika Anda tertarik dengan topik Pembahasan soal ONMIPA/KNMIPA lainnya, silahkan ke sini. Jika Anda tertarik dengan topik lainnya, silahkan ke sini.