Pembahasan Soal UAS Matematika Diskrit Tahun 2020

 Baiklah kali ini kita membahas soal UAS matematika diskrit tahun 2020. Perhatikan dan tetap semangat. Semoga pembahasannya membantu..

1. Suatu bilangan bulat positif disebut bilangan Palindrom jika digit-digit dibaca dari depan dan belakang sama nilainya. (misal : 1, 33, 272, 1881). Tentukan banyaknya bilangan Palindrom enam angka yang merupakan bilangan genap.

Jawab : Bilangan Palindrom enam angka dapat dituliskan sebagai $\textit{abccba}$, dimana $\textit{a,b,c}$ adalah suatu digit dan $a\neq 0$. Jadi akan dicari banyak total kemungkinan nilai $\textit{a,b,c}$ yang memenuhi kondisi soal. Pertama, karena $\textit{abccba}$ bilangan genap maka banyak kemungkinan nilai $\textit{a}$ adalah $4$ yaitu $2,4,6,8$. Sedangkan nilai $\textit{b}$ dan nilai $\textit{c}$ banyak kemungkinannya adalah $10$. Oleh karenanya berdasarkan aturan perkalian dapat dikatakan banyak total kemungkinan nilai $\textit{a,b,c}$ yang memenuhi kondisi soal adalah $4\times 10\times 10=400$. Jadi, banyaknya bilangan Palindrom enam angka yang merupakan bilangan genap adalah $400$

2. Jika $n$ bilangan bulat non negative, tunjukkan bahwa $\sum_{k=0}^n3^k\binom{n}{k}=4^n$

Jawab : Kita akan gunakan bukti kombinatorial untuk membuktikannya. Perhatikan bahwa ruas kanan yaitu $4^n$ menyatakan bahwa banyaknya kata sandi dengan panjang $n$ yang disusun dari kata $\{a,b,c,d\}$. Dilain sisi kita bisa menghitung hal ini dengan memandang suatu huruf dalam kata sandi tersebut katakan $a$. Sehingga kita akan mendapatkan beberapa kasus.

-) Jika banyak $a$ dalam kata sandi tersebut adalah $0$, dapat kita hitung untuk kasus ini banyaknya adalah $3^n$.

-) Jika banyak $a$ dalam kata sandi tersebut adalah $1$, dapat kita hitung untuk kasus ini banyaknya adalah $3^{n-1}\binom{n}{1}$.

-) Jika banyak $a$ dalam kata sandi tersebut adalah $2$, dapat kita hitung untuk kasus ini banyaknya adalah $3^{n-2}\binom{n}{2}$.

-) Jika banyak $a$ dalam kata sandi tersebut adalah $3$, dapat kita hitung untuk kasus ini banyaknya adalah $3^{n-3}\binom{n}{3}$.

dan seterusnya hingga

-) Jika banyak $a$ dalam kata sandi tersebut adalah $n$, dapat kita hitung untuk kasus ini banyaknya adalah $3^0\binom{n}{n}$.

Jadi, dengan menjumlahkan banyak cara dari semua kasus didapat banyaknya cara adalah $\sum_{k=0}^n3^k\binom{n}{k}$. Karena keduanya menghitung permasalahan yang sama maka dapat disimpulkan $\sum_{k=0}^n3^k\binom{n}{k}=4^n$.

3. Selesaikan relasi rekursif

$$\begin{equation*}a_0=1; a_n=8a_{n-1}+10^{n-1}\end{equation*}$$

Jawab : Relasi rekursif merupakan relasi rekursif tak homogen. Maka terlebih dahulu akan dicari solusi homogennya yaitu

$$\begin{align*}a_n&=8a_{n-1}\\ a_n-8a_{n-1}&=0\end{align*}$$

Persamaan karakteristiknya adalah $r-8=0$, maka $r=8$. Sehingga solusi homogennya mempunyai bentuk umum

$$\begin{equation*}h_n=c_1(8)^n\end{equation*}$$

untuk suatu $c_1\in \mathbb{R}$.

Kemudian dari bentuk $10^{n-1}$, kita bisa melihat bahwa solusi partikularnya berbentuk $p_n=A.10^{n-1}$ untuk suatu bilangan real $A$. Karena $p_n=A.10^{n-1}$ adalah solusi partikularnya, kita bisa substitusi ke relasi rekursifnya sehingga didapat

$$\begin{align*}A.10^{n-1}&=8A.10^{n-2}+10^{n-1}\\ 10A&=8A+10\\ A&=5\end{align*}$$

Sehingga solusi pertikularnya menjadi $p_n=5.10^{n-1}$.

Oleh karena itu, relasi rekursif

$$\begin{equation*}a_n=8a_{n-1}+10^{n-1}\end{equation*}$$

mempunyai solusi umum berbentuk $a_n=h_n+p_n=c_1(8)^n+5.10^{n-1}$. Dan dari nilai $a_0$ akan didapat nilai $c_1$ yaitu

$$\begin{align*} a_0&=c_1(8)^0+5.10^{-1}\\ 1&=c_1+\frac{1}{2}\\ c_1&=\frac{1}{2}\end{align*}$$

Jadi, solusi dari relasi rekursif

$$\begin{equation*}a_n=8a_{n-1}+10^{n-1}\end{equation*}$$

dengan $a_0=1$ adalah $a_n=\frac{1}{2}(8)^n+5.10^{n-1}$.

4. Misalkan $a_n$ menyatakan banyaknya barisan binair $n$ angka yang tidak memuat dua "0“ secara berurutan.

(a) Tuliskan relasi rekursif untuk $a_n$

(b) Selesaikan relasi rekursif pada soal (a).

Jawab : (a) Perhatikan bahwa berdasarkan definisi tersebut diperoleh $a_0=1$ dan $a_1=2$. Untuk $n\geq 2$, Diberikan barisan binair $n$ angka. Ada dua kasus, kasus pertama jika angka pertamanya adalah $0$ sedangkan kasus kedua jika angka pertamanya adalah $1$.

-) Jika angka pertamanya adalah $0$, maka angka selanjutnya haruslah angka $1$. Sehingga tersisa barisan binair $n-2$ angka, dimana tidak ada dua "0“ secara berurutan. Dalam kasus ini banyak caranya adalah $a_{n-2}$.

-) Jika angka pertamanya adalah $1$. Maka tersisa barisan binair $n-1$ angka, dimana tidak ada dua "0“ secara berurutan. Dalam kasus ini banyak caranya adalah $a_{n-1}$.

Sehingga relasi rekursif

$$\begin{equation*}\begin{cases}a_0=1\\ a_1=2\\a_n=a_{n-1}+a_{n-2} \ \forall n\geq 2\end{cases}\end{equation*}$$

(b) Kita punya relasi rekursif

$$\begin{align*}a_n&=a_{n-1}+a_{n-2}\\ a_n-a_{n-1}-a_{n-2}&=0\end{align*}$$

Karena relasi rekursif sudah homogen maka didapat persamaan karakteristiknya adalah $r^2-r-1=0$, maka $r=\frac{1\pm\sqrt{5}}{2}$. Sehingga solusi nya mempunyai bentuk umum

$$\begin{equation*}a_n=c_1\left(\frac{1+\sqrt{5}}{2}\right)^n+c_2\left(\frac{1-\sqrt{5}}{2}\right)^n\end{equation*}$$

Dari nilai $a_0=1$ dan $a_1=2$ didapat

$$\begin{align*}a_0&=c_1\left(\frac{1+\sqrt{5}}{2}\right)^0+c_2\left(\frac{1-\sqrt{5}}{2}\right)^0\\ &=c_1+c_2\\ a_1&=c_1\left(\frac{1+\sqrt{5}}{2}\right)^1+c_2\left(\frac{1-\sqrt{5}}{2}\right)^1\\ &=\frac{1}{2}(c_1+c_2)+\frac{\sqrt{5}}{2}(c_1-c_2)\end{align*}$$

Sehingga $c_1+c_2=1$ dan $\frac{1}{2}(c_1+c_2)+\frac{\sqrt{5}}{2}(c_1-c_2)=2$. Diperoleh $c_1=\frac{1}{2}+\frac{3}{10}\sqrt{5}$ dan $c_2=\frac{1}{2}-\frac{3}{10}\sqrt{5}$. Jadi penyelesaian dari relasi rekursif tersebut adalah

$$\begin{equation*}a_n=\left(\frac{1}{2}+\frac{3}{10}\sqrt{5}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1}{2}-\frac{3}{10}\sqrt{5}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n\end{equation*}$$

 5. Dengan menggunakan prinsip inklusi-eksklusi, tentukan banyaknya permutasi dari $\{1,2,3,4,5,6,7,8,9,10\}$ sedemikian sehingga tidak ada bilangan menempati tempat semula.

Jawab : Perhatikan bahwa banyak permutasi dari $\{1,2,3,4,5,6,7,8,9,10\}$ secara umum adalah $10!$.

Misalkan $A_i$ dengan $i\in\{1,2,3,4,5,6,7,8,9,10\}$, merupakan suatu himpunan semua permutasi dari $\{1,2,3,4,5,6,7,8,9,10\}$ sehingga bilangan $i$ menempati tempatnya semula. Dengan assumsi semua permutasi adalah himpunan yang berbeda. Sebagai contoh

$$\begin{align*}A_1=&\{\{1,2,3,4,5,6,7,8,9,10\},\{1,2,3,4,5,6,7,8,10,9\},\{1,2,3,4,5,6,7,10,8,9\},\\ &\{1,2,3,4,5,6,7,10,9,8\},\{1,2,3,4,5,6,10,7,8,9\},\cdots ,\{1,10,9,8,7,6,5,4,3,2\}\}\end{align*}$$

Dengan assumsi semua anggota tersebut berbeda. Sehingga bisa didapat $|A_1|=9!$. Secara umum $|A_i|=9!$ untuk setiap $i\in\{1,2,\cdots,10\}$. Kemudian kita juga bisa dapatkan $|A_i|\cap |A_j|,i\neq j$ yaitu himpunan permutasi dimana $i$ dan $j$ menempati tempatnya semula. Maka $|A_i|\cap |A_j|=8!$. Sehingga dapat kita lihat bahwa $|A_{i_1}|\cap |A_{i_2}|\cap |A_{i_3}|\cdots |A_{i_k}|,i_1\neq i_1\neq i_3\neq\cdots\neq i_k$, untuk sebarang $k\in\{1,2,3,4,5,6,7,8,9,10\}$ bernilai $(10-k)!$. Jadi, dengan prinsip inklusi-eksklusi banyaknya permutasi dari $\{1,2,3,4,5,6,7,8,9,10\}$ sedemikian sehingga tidak ada bilangan menempati tempat semula

$$\begin{align*}\binom{10}{0}10!-\binom{10}{1}9!+\cdots -\binom{10}{9}1!+\binom{10}{10}0!&=\sum\limits_{k=0}^{10}(-1)^k\binom{10}{k}(10-k)! \\ &=\sum\limits_{k=0}^{10}(-1)^k\frac{10!}{k!}\end{align*}$$ .