Pembahasan Soal ON-MIPA PT Matematika
Hai teman teman semua kali ini kita akan membahas soal ON-Mipa PT khususnya bidang Matematika tahun 2018 mari kita simak pembahasan nya.
Jawab : Jika kita tidak memperhatikan syarat maka subset yg terdiri dari 3 bilangan sebanyak $\binom{25}{3}$. Jika sebuah subset terdapat tepat dua bilangan berurutan maka banyaknya adalah $21\times 22+22\times 2=22\times 23=506$. Jika sebuah subset tiga bilangannya berurutan banyaknya adalah $25$. Jadi, banyak subset dari himpunan tersebut yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalah $\binom{25}{3}-506-23=2300-529=1771$
2) Sebuah klub bulu tangkis mempunyai 35 anggota yang 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
Jawab : banyak cara memilih 10 anak laki-laki dari 15 anak laki-laki adalah $\binom{15}{10}$, sedang banyak cara memilih 10 anak perempuan dari 20 anak perempuan adalah $\binom{20}{10}$. banyak cara memasangkannya adalah $10!$. Jadi, Banyaknya cara yang mungkin untuk membentuk 10 pasangan ganda campuran adalah $10!\binom{15}{10}\binom{20}{10}$.
3) Sebuah toko roti memproduksi 8 jenis donat. Donat dikemas dalam kotak yang masing-masing berisi 12 buah donat. Banyaknya cara untuk mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis adalah
Jawab : Misalkan $j_1,j_2,j_3,\cdots ,j_8$ merupakan jenis 8 roti yang berbeda. Hal ini sama aja kita mencari banyak solusi dari persamaan $j_1+j_2+j_3+\cdots +j_8=12$, karena $j_n\in\mathbb{N}$ maka banyak solusi dari persamaan tersebut adalah $\binom{12-1}{8-1}=\binom{11}{7}=330$
4) Untuk bilangan bulat positif $n\geq 2$, nilai dari $\sum_{k=2}^n(-1)^kk\binom{n}{k}$ adalah
Jawab : Perhatikan bahwa
$\sum_{k=2}^n(-1)^kk\binom{n}{k}=\sum_{k=2}^n(-1)^kn\binom{n-1}{k-1}$
Karena $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ maka
$\sum_{k=2}^n(-1)^kk\binom{n}{k}=\sum_{k=2}^n(-1)^kn\binom{n-1}{k-1}\\=\sum_{k=2}^n(-1)^kn\binom{n}{k}-\sum_{k=2}^n(-1)^kn\binom{n-1}{k}\\ n\left(\sum_{k=2}^n(-1)^k\binom{n}{k}-\sum_{k=2}^n(-1)^k\binom{n-1}{k}\right)$
Perhatikan bahwa $\sum_{k=0}^n(-1)^kn\binom{n}{k}=0$
$n\left(\sum_{k=2}^n(-1)^k\binom{n}{k}-\sum_{k=2}^n(-1)^k\binom{n-1}{k}\right)=\\ n\left((n-1)-\sum_{k=2}^{n-1}(-1)^k\binom{n-1}{k}-(-1)^n\binom{n-1}{n}\right)$
Perlu diketahui bahwa $\binom{n-1}{n}=0$. Jadi, $\sum_{k=2}^n(-1)^kk\binom{n}{k}\\ =n\left((n-1)-\sum_{k=2}^{n-1}(-1)^kn\binom{n-1}{k}-0\right)\\ =n(n-1)-n(n-2)=n$
5) Misalkan $b_n$ adalah banyaknya untaian atas $n$ huruf yang dapat dibentuk dengan menggunakan huruf 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
Jawab : Jika huruf A menjadi huruf pertama maka huruf berikutnya adalah B, sehingga banyak untaian nya adalah $b_{n-2}$, Jika huruf B menjadi huruf pertama maka banyak untaian nya adalah $b_{n-1}$, Jika huruf C menjadi huruf pertama maka banyak untaian nya adalah $b_{n-1}$, Jadi $b_n=2b_{n-1}+b_{n-2}$ dengan kondisi $b_1=3$ yaitu $\{A,B, C\}$ dan $b_2=5$ yaitu $\{AB, BC, BA, CB, CA\}$
6) Diberikan permutasi $F=\left(\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right)$ atas
himpunan $\{1, 2, \cdots , n\}$ dengan $𝑛\geq 7$. Banyaknya permutasi $\pi$ sehingga $\pi(1) =5$ atau $\pi(3) = 7$ atau $\pi(6) = 2$ adalah
7) Dalam bentuk yang paling sederhana, fungsi pembangkit eksponensial (exponential generating function) dari barisan $(0!, 1!, 2!, 3!,\cdots , n!)$ adalah
Jawab :
$b(x)=\frac{a_0x^0}{0!}+\frac{a_1x^1}{1!}+\frac{a_2x^2}{2!}+\frac{a_3x^3}{3!}+\cdots $
$b(x)=1+x+x^2+x^3+x^4+x^5+\cdots $
$b(x)=\frac{1}{1-x}$
8) Diberikan sebuah graf sederhana $𝐺$ atas 6 titik $v_1 ,v_2 ,\cdots ,v_5$. Bila $𝐺$ mempunyai 8 sisi dan derajat dari titik $v_1, v_2, \cdots , v_5$ masing-masing adalah 1, 3, 3, 3, dan 2, maka derajat dari titik $v_6$ adalah
Jawab : Diketahui $G(V,E)=G(6,8)$. Perhatikan bahwa jumlah derajat semua titik suatu Graf sama dengan dua kali banyak sisinya. Jadi,
$\sum_{v\in V}deg(v)=2E$
$deg(v_1)+deg(v_2)+deg(v_3)+deg(v_4)+deg(v_5)+deg(v_6)=2\times 8$
$1+3+3+3+2+deg(v_6)=16$
Bagian Kedua
1) Perhatikan barisan Fibonacci dengan relasi rekurensi untuk $n\geq 2$, berlaku $f_n=f_{n-1}+f_{n-2}$, $f(0)=0$, dan $f(1)=1$. Definisikan matriks $F=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]=\left[\begin{array}{cc}f_2 & f_1\\ f_1 & f_0\end{array}\right]$
a. Buktikan bahwa $F^n=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^n=\left[\begin{array}{cc}f_{n+1} & f_n\\ f_n & f_{n-1}\end{array}\right]$
b. Buktikan bahwa $f_{n+1}f_{n-1}-f_n^2=\begin{cases}1 , & \text{bila}\ n\ \text{genap}\\ -1 , & \text{bila}\ n\ \text{ganjil}\end{cases}$
Jawab : a. Kita akan bukikan dengan menggunakan induksi
$f_2=f_1+f_0=1$
Untuk $n=1$ maka $F^1=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]=\left[\begin{array}{cc}f_2 & f_1\\ f_1 & f_0\end{array}\right]$
Jelas hal ini benar.
Claim bahwa untuk bilangan asli $k$ maka berlaku $F^k=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^k=\left[\begin{array}{cc}f_{k+1} & f_k\\ f_k & f_{k-1}\end{array}\right]$
Akan dibuktikan benar bahwa $F^{k+1}=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^{k+1}=\left[\begin{array}{cc}f_{k+2} & f_{k+1}\\ f_{k+1} & f_{k}\end{array}\right]$
3) Tentukan banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah.
Jawab : Jika kita mengabaikan syarat maka banyak cara mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru adalah $3n$. Perhatikan bahwa jika $n$ genap maka untuk suatu $k$ bilangan bulat dimana $2k<n$ maka banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah adalah $\begin{align*}\sum_{k=0}^{\frac{n}{2}}\left(\binom{n}{2k}+2\binom{n-2k}{n-2k}\right)&=2^{n-1}+n+2\end{align*}$.
Sedangkan jika $n$ ganjil maka banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah adalah $\begin{align*}\sum_{k=0}^{\frac{n-1}{2}}\left(2\binom{n}{2k+1}+\binom{n-2k-1}{n-2k-1}\right)&=2^{n}+\frac{n+1}{2}\end{align*}$.
Pembahasan Soal ON-MIPA PT Matematika Bidang Kombinatorika Tahun 2018
Bagian Pertama
1) Banyaknya subset dari himpunan $\{1, 2, \cdots , 25\}$ yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalahJawab : Jika kita tidak memperhatikan syarat maka subset yg terdiri dari 3 bilangan sebanyak $\binom{25}{3}$. Jika sebuah subset terdapat tepat dua bilangan berurutan maka banyaknya adalah $21\times 22+22\times 2=22\times 23=506$. Jika sebuah subset tiga bilangannya berurutan banyaknya adalah $25$. Jadi, banyak subset dari himpunan tersebut yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalah $\binom{25}{3}-506-23=2300-529=1771$
2) Sebuah klub bulu tangkis mempunyai 35 anggota yang 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
Jawab : banyak cara memilih 10 anak laki-laki dari 15 anak laki-laki adalah $\binom{15}{10}$, sedang banyak cara memilih 10 anak perempuan dari 20 anak perempuan adalah $\binom{20}{10}$. banyak cara memasangkannya adalah $10!$. Jadi, Banyaknya cara yang mungkin untuk membentuk 10 pasangan ganda campuran adalah $10!\binom{15}{10}\binom{20}{10}$.
3) Sebuah toko roti memproduksi 8 jenis donat. Donat dikemas dalam kotak yang masing-masing berisi 12 buah donat. Banyaknya cara untuk mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis adalah
Jawab : Misalkan $j_1,j_2,j_3,\cdots ,j_8$ merupakan jenis 8 roti yang berbeda. Hal ini sama aja kita mencari banyak solusi dari persamaan $j_1+j_2+j_3+\cdots +j_8=12$, karena $j_n\in\mathbb{N}$ maka banyak solusi dari persamaan tersebut adalah $\binom{12-1}{8-1}=\binom{11}{7}=330$
4) Untuk bilangan bulat positif $n\geq 2$, nilai dari $\sum_{k=2}^n(-1)^kk\binom{n}{k}$ adalah
Jawab : Perhatikan bahwa
$\sum_{k=2}^n(-1)^kk\binom{n}{k}=\sum_{k=2}^n(-1)^kn\binom{n-1}{k-1}$
Karena $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ maka
$\sum_{k=2}^n(-1)^kk\binom{n}{k}=\sum_{k=2}^n(-1)^kn\binom{n-1}{k-1}\\=\sum_{k=2}^n(-1)^kn\binom{n}{k}-\sum_{k=2}^n(-1)^kn\binom{n-1}{k}\\ n\left(\sum_{k=2}^n(-1)^k\binom{n}{k}-\sum_{k=2}^n(-1)^k\binom{n-1}{k}\right)$
Perhatikan bahwa $\sum_{k=0}^n(-1)^kn\binom{n}{k}=0$
$n\left(\sum_{k=2}^n(-1)^k\binom{n}{k}-\sum_{k=2}^n(-1)^k\binom{n-1}{k}\right)=\\ n\left((n-1)-\sum_{k=2}^{n-1}(-1)^k\binom{n-1}{k}-(-1)^n\binom{n-1}{n}\right)$
Perlu diketahui bahwa $\binom{n-1}{n}=0$. Jadi, $\sum_{k=2}^n(-1)^kk\binom{n}{k}\\ =n\left((n-1)-\sum_{k=2}^{n-1}(-1)^kn\binom{n-1}{k}-0\right)\\ =n(n-1)-n(n-2)=n$
5) Misalkan $b_n$ adalah banyaknya untaian atas $n$ huruf yang dapat dibentuk dengan menggunakan huruf 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
Jawab : Jika huruf A menjadi huruf pertama maka huruf berikutnya adalah B, sehingga banyak untaian nya adalah $b_{n-2}$, Jika huruf B menjadi huruf pertama maka banyak untaian nya adalah $b_{n-1}$, Jika huruf C menjadi huruf pertama maka banyak untaian nya adalah $b_{n-1}$, Jadi $b_n=2b_{n-1}+b_{n-2}$ dengan kondisi $b_1=3$ yaitu $\{A,B, C\}$ dan $b_2=5$ yaitu $\{AB, BC, BA, CB, CA\}$
6) Diberikan permutasi $F=\left(\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right)$ atas
himpunan $\{1, 2, \cdots , n\}$ dengan $𝑛\geq 7$. Banyaknya permutasi $\pi$ sehingga $\pi(1) =5$ atau $\pi(3) = 7$ atau $\pi(6) = 2$ adalah
7) Dalam bentuk yang paling sederhana, fungsi pembangkit eksponensial (exponential generating function) dari barisan $(0!, 1!, 2!, 3!,\cdots , n!)$ adalah
Jawab :
$b(x)=\frac{a_0x^0}{0!}+\frac{a_1x^1}{1!}+\frac{a_2x^2}{2!}+\frac{a_3x^3}{3!}+\cdots $
$b(x)=1+x+x^2+x^3+x^4+x^5+\cdots $
$b(x)=\frac{1}{1-x}$
8) Diberikan sebuah graf sederhana $𝐺$ atas 6 titik $v_1 ,v_2 ,\cdots ,v_5$. Bila $𝐺$ mempunyai 8 sisi dan derajat dari titik $v_1, v_2, \cdots , v_5$ masing-masing adalah 1, 3, 3, 3, dan 2, maka derajat dari titik $v_6$ adalah
Jawab : Diketahui $G(V,E)=G(6,8)$. Perhatikan bahwa jumlah derajat semua titik suatu Graf sama dengan dua kali banyak sisinya. Jadi,
$\sum_{v\in V}deg(v)=2E$
$deg(v_1)+deg(v_2)+deg(v_3)+deg(v_4)+deg(v_5)+deg(v_6)=2\times 8$
$1+3+3+3+2+deg(v_6)=16$
Bagian Kedua
1) Perhatikan barisan Fibonacci dengan relasi rekurensi untuk $n\geq 2$, berlaku $f_n=f_{n-1}+f_{n-2}$, $f(0)=0$, dan $f(1)=1$. Definisikan matriks $F=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]=\left[\begin{array}{cc}f_2 & f_1\\ f_1 & f_0\end{array}\right]$
a. Buktikan bahwa $F^n=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^n=\left[\begin{array}{cc}f_{n+1} & f_n\\ f_n & f_{n-1}\end{array}\right]$
b. Buktikan bahwa $f_{n+1}f_{n-1}-f_n^2=\begin{cases}1 , & \text{bila}\ n\ \text{genap}\\ -1 , & \text{bila}\ n\ \text{ganjil}\end{cases}$
Jawab : a. Kita akan bukikan dengan menggunakan induksi
$f_2=f_1+f_0=1$
Untuk $n=1$ maka $F^1=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]=\left[\begin{array}{cc}f_2 & f_1\\ f_1 & f_0\end{array}\right]$
Jelas hal ini benar.
Claim bahwa untuk bilangan asli $k$ maka berlaku $F^k=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^k=\left[\begin{array}{cc}f_{k+1} & f_k\\ f_k & f_{k-1}\end{array}\right]$
Akan dibuktikan benar bahwa $F^{k+1}=\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^{k+1}=\left[\begin{array}{cc}f_{k+2} & f_{k+1}\\ f_{k+1} & f_{k}\end{array}\right]$
Menurut assumsi $\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^k=\left[\begin{array}{cc}f_{k+1} & f_k\\ f_k & f_{k-1}\end{array}\right]$
Kalikan kedua ruas dengan $\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]$
$\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^{k+1}=\left[\begin{array}{cc}f_{k+1} & f_k\\ f_k & f_{k-1}\end{array}\right]\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]$
$\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^{k+1}=\left[\begin{array}{cc}f_{k+1}+f_k & f_{k+1}\\ f_k+f_{k-1} & f_{k}\end{array}\right]$
$\left[\begin{array}{cc}1 & 1\\ 1 & 0\end{array}\right]^{k+1}=\left[\begin{array}{cc}f_{k+2} & f_{k+1}\\ f_{k+1} & f_{k}\end{array}\right]$ (Q.E.D)
2) Andaikan $G$ adalah sebuah graf sederhana (simple graph). Bila $e$ adalah sebuah sisi yang menghubungkan titik $u$ dan titik $v$ di $G$, maka dikatakan bahwa titik $u$ bertetangga dengan titik $v$. Derajat dari sebuah titik $v$ di $G$ adalah banyaknya titik-titik yang bertetangga dengan $v$. Perlihatkan bahwa pada sebuah graf sederhana $G$ terdapat sedikitnya dua titik dengan derajat sama.3) Tentukan banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah.
Jawab : Jika kita mengabaikan syarat maka banyak cara mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru adalah $3n$. Perhatikan bahwa jika $n$ genap maka untuk suatu $k$ bilangan bulat dimana $2k<n$ maka banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah adalah $\begin{align*}\sum_{k=0}^{\frac{n}{2}}\left(\binom{n}{2k}+2\binom{n-2k}{n-2k}\right)&=2^{n-1}+n+2\end{align*}$.
Sedangkan jika $n$ ganjil maka banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah adalah $\begin{align*}\sum_{k=0}^{\frac{n-1}{2}}\left(2\binom{n}{2k+1}+\binom{n-2k-1}{n-2k-1}\right)&=2^{n}+\frac{n+1}{2}\end{align*}$.
