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

Pembahasan soal onmipa pt matematika kombinatorika tahun 2018 uraian

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. Sebelumnya, kita telah membahas soal isian Kombinatorika tahun 2018. Jadi, sebagai lanjutan tulisan tersebut, kita akan membahas tiga soal uraian yang tersisa.

Nomor 1

Perhatikan barisan Fibonacci dengan relasi rekurensi, untuk n \geq 2, f_n=f_{n-1}+f_{n-2}, f_0=0, 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 genap}\\ -1&, \text{bila n ganjil} \end{cases}\]

Pembahasan

Bagian a
Misalkan P(n) adalah pernyataan

    \[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]\]

Kita akan membuktikan bahwa P(n) bernilai benar, untuk setiap bilangan asli n, dengan induksi matematika.

Langkah Dasar
Kita akan menunjukkan bahwa P(1) bernilai benar.
Untuk n=1, diperoleh

    \[F^1 = \left[ \begin{array}{cc} 1&1\\ 1&0 \end{array} \right]^1 = \left[ \begin{array}{cc} f_2&f_1\\ f_1&f_0 \end{array} \right]\]

Jadi, P(1) bernilai benar.

Langkah Induksi
Asumsikan P(k) bernilai benar, yaitu

    \[F^k = \left[ \begin{array}{cc} f_{k+1}&f_k\\ f_k&f_{k-1} \end{array} \right]\]

Akan ditunjukkan bahwa P(k+1) juga bernilai benar.

Perhatikan bahwa

    \begin{align*} F^{k+1} &= F^kF &\text{[Pemangkatan matriks]} \\ &= \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] &\text{[Asumsi]} \\ &= \left[ \begin{array}{cc} f_{k+1}+f_k&f_{k+1}\\ f_k+f_{k-1}&f_k \end{array} \right] &\text{[Perkalian matriks]} \\ &= \left[ \begin{array}{cc} f_{k+2}&f_{k+1}\\ f_{k+1}&f_k \end{array} \right] &\text{[Definisi relasi rekurensi]} \end{align*}

Jadi, P(k+1) juga bernilai benar.

Berdasarkan induksi matematika, P(n) bernilai benar, untuk setiap bilangan asli n.

Pembahasan soal nomor 1a juga tersedia dalam bentuk video. Silakan tonton video berikut, untuk mendapatkan penjelasan yang lebih detail!

Bagian b
Misalkan P(n) adalah pernyataan

    \[f_{n+1}f_{n-1}-f_n^2 = \begin{cases} 1&, \text{bila n genap}\\ -1&, \text{bila n ganjil} \end{cases}\]

Kita akan membuktikan bahwa P(n) bernilai benar, untuk setiap bilangan asli n, dengan induksi matematika.

Langkah Dasar
Kita akan menunjukkan bahwa P(1) bernilai benar.
Untuk n=1, diperoleh

    \[f_2f_0-f_1^2=1\cdot0-1^2=-1\]

Karena 1 bilangan ganjil, maka P(1) bernilai benar.

Langkah induksi
Asumsikan P(k) bernilai benar, yaitu

    \[f_{k+1}f_{k-1}-f_k^2 = \begin{cases} 1&, \text{bila k genap}\\ -1&, \text{bila k ganjil} \end{cases}\]

Akan ditunjukkan bahwa P(k+1) juga bernilai benar.

Perhatikan bahwa

    \begin{align*} f_{k+2}f_k-f_{k+1}^2 &= (f_{k+1}+f_k)f_k-f_{k+1} \cdot f_{k+1} \\ &= f_{k+1}f_k+f_k^2-f_{k+1}(f_k+f_{k-1}) \\ &= f_{k+1}f_k+f_k^2-f_{k+1}f_k-f_{k+1}f_{k-1} \\ &= f_k^2-f_{k+1}f_{k-1} \\ &= -(f_{k+1}f_{k-1}-f_k^2) \end{align*}

Kasus I: Jika k bilangan ganjil, maka f_{k+1}f_{k-1}-f_k^2=-1 dan k+1 bilangan genap. Akibatnya

    \[f_{k+2}f_k-f_{k+1}^2 = -(-1) = 1\]

Jadi, P(k+1) bernilai benar, untuk k bilangan ganjil.

Kasus II: Jika k bilangan genap, maka f_{k+1}f_{k-1}-f_k^2=1 dan k+1 bilangan ganjil. Akibatnya

    \[f_{k+2}f_k-f_{k+1}^2 = -1\]

Jadi, P(k+1) bernilai benar, untuk k bilangan genap.

Berdasarkan induksi matematika, P(n) bernilai benar, untuk setiap bilangan asli n.

Pembahasan soal nomor 1b juga tersedia dalam bentuk video. Silakan tonton video berikut, untuk mendapatkan penjelasan yang lebih detail!
Nomor 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.

Pembahasan

Misalkan G graf sederhana dengan n titik. Derajat yang mungkin dimiliki oleh oleh titik pada G merupakan anggota himpunan

    \[\{ 0,1,2,\cdots,n-1 \}\]

Namun, graf G tidak mungkin memiliki titik dengan derajat 0 dan n-1 secara bersamaan.

Bukti: Andaikan terdapat graf G dengan n titik yang memiliki titik berderajat 0 dan n-1. Misalkan u titik pada G yang memiliki derajat n-1. Ini berarti u bertetangga dengan semua titik lain pada G. Akibatnya, titik-titik lain pada G berderajat minimal 1.
Kontradiksi dengan pengandaian bahwa terdapat titik dengan derajat 0.
Terbukti.

Akibatnya, derajat titik-titik pada graf G, termuat dalam salah satu himpunan berikut.

    \begin{align*} \{ 0,1,2,\cdots,n-2 \} \\ \{ 1,2,\cdots,n-1 \} \end{align*}

Kedua himpunan di atas, terdiri dari n-1 anggota. Ingat bahwa graf G terdiri dari n titik. Berdasarkan Prinsip Sangkar Burung (Pigeon Hole Principle), terdapat sedikitnya dua titik yang memiliki derajat sama.
Terbukti.

Nomor 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.

Pembahasan

Pewarnaan tersebut menggunakan warna merah, hijau, atau biru, dengan syarat banyaknya bujur sangkar merah merupakan bilangan genap.
Fungsi pembangkit eksponensial untuk penyusunan ini adalah

    \[f(x) = \left( 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots \right) \left( 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \right)^2\]

Banyaknya cara mewarnai bujur sangkar 1 \times 1 pada persegi panjang 1 \times n dengan syarat yang diberikan sama dengan koefisien \frac{x^n}{n} pada f(x).

Perhatikan bahwa

    \begin{align*} f(x) &= \left( 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots \right) \left( 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \right)^2 \\ &= \left( \frac{e^x+e^{-x}}{2} \right) \left( e^x \right)^2 \\ &= \left( \frac{e^x+e^{-x}}{2} \right)e^{2x} \\ &= \frac{1}{2} \left( e^{3x} + e^x \right) \\ &= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{(3x)^i}{i!} + \sum_{i=0}^{\infty} \frac{x^i}{i!} \right) \\ &= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{3^ix^i}{i!} + \sum_{i=0}^{\infty} \frac{x^i}{i!} \right) \\ &= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{3^ix^i + x^i}{i!} \right) \\ &= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{(3^i + 1) x^i}{i!} \right) \end{align*}

Suku yang memuat \frac{x^n}{n!} adalah

    \[\frac{1}{2} \cdot \frac{(3^n + 1) x^n}{n!} = \frac{3^n + 1}{2} \cdot \frac{x^n}{n!}\]

dengan koefisien

    \[\frac{3^n + 1}{2}\]

Jadi, banyaknya cara mewarnai bujur sangkar 1 \times 1 pada persegi panjang 1 \times n dengan syarat yang diberikan adalah \frac{3^n + 1}{2}.

Semoga bermanfaat! Jika ada yang perlu diperbaiki atau anda punya solusi yang berbeda, silakan beritahu melalui komentar. 🙂

3 thoughts on “Pembahasan Soal ON MIPA-PT Matematika Tahun 2018 Kombinatorika (Uraian)”

  1. Untuk pembahasan isian dan uraian untuk ONMIPA-PT 2018 bidang matematika bagian Aljabar Linier, Struktur Aljabar, Analisis Real dan Analisis Kompleks apakah mas punya? Terima kasih

Leave a Comment

Your email address will not be published. Required fields are marked *