Pembahasan Soal ON-MIPA PT Matematika

Hai teman teman semua kali ini kita akan membahas soal ON-Mipa PT khususnya bidang Matematika tahun 2016 mari kita simak pembahasan nya.

Pembahasan Soal ON-MIPA PT Matematika Bidang Kombinatorika Tahun 2016

                             

Bagian Pertama

1. Sepotong kawat berukuran 1 meter dipotong secara acak menjadi tiga bagian. Besarnya peluang ketiga bagian ini membentuk sebuah segitiga adalah
   Jawab : Berdasarkan ketaksamaan segitiga dalam $\triangle ABC$ berlaku $a+b>c$, $b+c>a$ dan $a+c>b$. Assumsikan bahwa $a\leq b\leq c$. Banyak kasus adalah $a+b<c$, $a+b=c$, dan $a+b>c$. Maka peluang ketiga bagian ini membentuk sebuah segitiga adalah $\frac{1}{3}$
2. Sebuah palindrome adalah sebuah barisan berhingga karakter sehingga dapat dibaca dengan cara yang sama baik dari kiri maupun kanan. SIKAPAKIS adalah sebuah palindrome. Banyaknya bilangan palindrome yang terdiri atas 7 digit sedemikian sehingga tidak terdapat digit yang muncul lebih dari dua kali adalah
   Jawab : Perhatikan bilangan tersebut jika kita lambangkan dengan suatu karakter maka membentuk $abcdcba$. Jadi kita sama saja mencari banyak nya bilangan 4 digit yang semua digitnya berbeda yaitu $9\times 9\times 8\times 7=4536$
3. Dari himpunan 26 huruf $A=\{a, b, c, ⋯ , y , z\}$ dibentuk susunan empat huruf berbeda (susunan tak perlu bermakna) sedemikian sehingga huruf pertama dan huruf terakhir adalah huruf konsonan. Jika huruf $b$ selalu muncul pada susunan dan berdampingan dengan huruf $c$, maka banyaknya susunan yang mungkin adalah
   Jawab : Pada pernyataan terakhir tersebut artinya $bc$ atau $cb$ selalu muncul. Artinya kita menyisakan dua tempat pada huruf ini. Jika kedua huruf ini ditengah maka banyak susunan yang mungkin adalah $2\times 19\times 18=684$. Jika kedua huruf tersebut bukan ditengah maka banyak susunannya menjadi $2\times 2\times 19\times 23=1748$. Jadi, total susunannya sebanyak $684+1748=2432$
4. Banyaknya cara memfaktorkan bilangan $441.000$ menjadi dua faktor positif $m$ dan $n$ yang saling prima relatif adalah
   Jawab : Perhatikan bahwa $441.000=3^2\times 7^2\times 2^3\times 5^3$. Agar $m$ dan $n$ relatif prima karena banyak faktor yang prima sebanyak 4 yaitu $3$, $7$ ,$2$, dan $5$ banyak cara memfaktorkannya sama dengan $\binom{4}{0}+\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=1+4+6+4+1=16$
5. Banyaknya bilangan antara $1$ dan $500$ yang tidak habis dibagi oleh 3, 4, dan 6 adalah

   Jawab : Bilangan yang tidak habis dibagi $3$ pasti tidak habis dibagi $6$. Jadi, kita hanya mencari bilangan yang tidak habis dibagi $3$ dan $4$.
Bilangan yang tidak habis dibagi $3$ sebanyak $500-\lfloor \frac{500}{3}\rfloor =500-166=334$
Bilangan yang tidak habis dibagi $4$ sebanyak $500-\lfloor \frac{500}{4}\rfloor =500-125=375$
Bilangan yang tidak habis dibagi $12$ sebanyak $500-\lfloor \frac{500}{12}\rfloor =500-41=459$
Jadi menurut prinsip inklusi-eksklusi banyak bilangan yang tidak habis dibagi $3$ dan $4$ adalah $334+375-459=250$.
6. Banyaknya graf sederhana berlabel atas $n$ titik yang memiliki sedikitnya dua sisi adalah

7. Didefinisikan suatu fungsi rekursif, $\forall n\in Z$ berlaku $f(1) = 1$, $f(2) = 5$, dan $f(n + 1) = f(n) + 2f(n − 1), \forall n > 2$. Nilai dari $f(n) =$
   Jawab : Perhatikan bahwa $f(n+1)+f(n)=2(f(n)+f(n-1))$
                $f(n+2)+f(n+1)=2(f(n+1)+f(n))=2^2(f(n)+f(n-1))$
                $f(n+k)+f(n+k-1)=2^k(f(n)+f(n-1))$ dengan $k$ bilangan asli
                $f(k+2)+f(k+1)=2^k(f(2)+f(1))=2^k\times 6=3\times 2^{k+1}$
                $f(k+3)=f(k+2)+f(k+1)+f(k+1)=3\times 2^{k+1}+f(k+1)$
                $f(k+3)-f(k+1)=3\times 2^{k+1}$
Substitusi $k=2m-3$ kita akan peroleh
                $f(2m)-f(2(m-1))=3\times 2^{2(m-1)}$
                $\sum\limits_{m=2}^x f(2m)-f(2(m-1))=3\sum\limits_{m=2}^x 2^{2(m-1)}$
                $f(2x)-f(2)=3\times\frac{2^2(2^{2(x-1)}-1)}{2^2-1}$
                $f(2x)-5=2^{2x}-4$
                $f(2x)=2^{2x}+1$
                $f(n)=2^n+(-1)^n$
8. Dalam bentuk yang paling sederhana, fungsi pembangkit biasa (ordinary generating function), $g(x)$, dari barisan $(1, 2, 3, 4, \cdots )$ adalah
   Jawab : Misalkan $F(x)$ adalah fungsi pembangkit biasa dari barisan $(1, 2, 3, 4, \cdots )$ maka
$F(x)=a_0x^0+a_1x^1+a_2x^2+a_3x^3+\cdots$
$F(x)=1+2x+3x^2+4x^3+\cdots$

$xF(x)=x+2x^2+3x^3+4x^4+\cdots$
$F(x)-xF(x)=1+x+x^2+x^3+x^4+\cdots$
$(1-x)F(x)=\frac{1}{1-x}$
$F(x)=\frac{1}{(x-1)^2}$

Bagian Kedua

1. Perlihatkan bahwa untuk setiap himpunan yang terdiri dari 7 bilangan bulat berbeda, maka terdapat dua bilangan $x$ dan $y$ pada himpunan tersebut sedemikian sehingga $x + y$ atau $x − y$ berkelipatan $10$.
Jawab : Perhatikan jika $x$ dan $y$ bersisa sama jika di bagi $10$ maka jelas $x-y$ habis dibagi $10$ dan kita selesai. Jika tidak maka setiap bilangan bulat pasti bisa dinyatakan dalam bentuk $10m+n$ untuk suatu bilangan bulat $m,n$ jika $n_1$ menyatakan sisa bilangan $x$ dibagi $10$ dan $n_2$ menyatakan sisa $y$ dibagi $10$ kita hanya bisa membuat $6$ bilangan sehingga $x+y$ tidak habis dibagi $10$. Contoh $10k, 10k+1, 10k+2, 10k+3, 10k+4, 10k+5$. Sehingga jika ada $7$ bilangan menurut PHP maka ada dua bilangan $x$ dan $y$ pada himpunan tersebut sedemikian sehingga $x + y$ berkelipatan $10$. Dan kita selesai.
2. Tuliskan sebuah argumentasi kombinatorial untuk memperlihatkan
$\binom{2n}{n}=2\binom{n}{2}+n^2$
dimana $n\geq 2$
Jawab : Harusnya ruas kiri $\binom{2n}{2}$. Jika kita punya $2n$ objek, kita pisah menjadi 2 di $A$ dan $B$ masing-masing berisikan $n$ objek, ruas kiri menyatakan kita memilih $2$ buah objek dari $2n$ objek, itu sama halnya kita bisa memilih $1$ objek di $A$ dan $1$ objek di $B$ atau kita bisa memilih $2$ objek sekaligus di $A$ atau juga kita bisa memilih $2$ objek sekaligus di $B$. Jadi $\binom{2n}{2}=2\binom{n}{2}+n^2$
3. Diberikan sembarang bilangan bulat positif $a$ dan $b$. Bilangan $r(a, b) = t$ adalah suatu bilangan bulat positif terkecil sedemikian sehingga setiap perwarnaan merah-biru pada semua sisi dari graf lengkap dengan $t$ titik senantiasa akan memuat subgraf lengkap $a$ titik dengan semua sisi berwarna merah atau memuat subgraf lengkap $b$ titik dengan semua sisi berwarna biru. Jika bilangan $t$ ada dan $a, b \geq 2$, buktikan bahwa
$r(a-1,b)+r(a,b-1)=\binom{a+b-2}{a-1}$