Pembahasan Soal ON-MIPA PT Matematika

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

Pembahasan Soal ON-MIPA PT Matematika Bidang Kombinatorika Tahun 2015

                             

Bagian Pertama

1) Pada babak final sebuah turnamen, tim pemenang adalah tim yang pertama sekali memenangkan dua pertandingan secara berurutan atau tim yang pertama sekali memenangkan empat pertandingan. Banyaknya cara turnamen dapat terjadi adalah...

 Jawab : kita abaikan terlebih dahulu tim mana yang menang ataupun yang kalah. Banyak pertandingan yang mungkin akan terjadi.
-)$MM$
-)$KMM$
-)$MKMM$
-)$KMKMM$
-)$MKMKMM$
-)$KMKMKMM$
Jika ada 8 pertandingan maka pasti ada yang sudah menang 2 kali berurutan atau sudah menang 4 pertandingan.
Sehingga banyak cara turnamen dapat terjadi adalah $6\times 2=12$

2) Banyaknya cara mengisi persegi panjang berukuran $2\times 6$ dengan persegi panjang berukuran $2\times 2, 2\times 3, 2\times 4$ adalah...

 Jawab : Banyak cara yaitu :
-) Dengan sebuah persegi panjang berukuran $2\times 2$ dan sebuah persegi panjang berukuran $2\times 4$. Ada $2$ cara.
-) Dengan 3 buah persegi panjang berukuran $2\times 2$. Ada $1$ cara.
-) Dengan 2 buah persegi panjang berukuran $2\times 3$. Ada $1$ cara.
Jadi, total cara mengisi persegi panjang berukuran $2\times 6$ dengan persegi panjang berukuran $2\times 2, 2\times 3, 2\times 4$ adalah $4$ cara

3) Enam komite akan dibentuk dari 14 orang. Bila 2 komite dari 6 komite ini terdiri atas 3 orang dan sisanya terdiri atas masing masing 2 orang, maka banyaknya komite yang dapat dibentuk adalah...

 Jawab : Banyak komite yang dapat dibentuk adalah $\binom{14}{3}\binom{11}{3}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}=\frac{14!}{3!3!2!2!2!2!}\\=14.13.11.10.9.7.5.4.3.2.1\\=182.990.7.120=151351200$

4) Sebuah password terdiri atas 7 huruf dibentuk dengan menggunakan huruf kapital. Sebuah password dikatakan legal bila memenuhi kondisi: (i) Tidak terdapat huruf berulang, (ii) huruf $X$ dan $Y$ tidak saling berdekatan. Besarnya peluang untuk membentuk password legal adalah... 

 Jawab : Banyak susunan password yang terdiri dari 7 huruf kapital yang tidak berulang adalah $26\times 25\times 24\times 23\times 22\times 21\times 20$. Sedangkan jika $X$ dan $Y$ berdekatan maka banyak susunan adalah $2\times 6\times 24\times 23\times 22\times 21\times 20$. Sehingga banyak password yang legal adalah $26\times 25\times 24\times 23\times 22\times 21\times 20-2\times 6\times 24\times 23\times 22\times 21\times 20\\=24\times 23\times 22\times 21\times 20(26\times 25-12)\\=24\times 23\times 22\times 21\times 20\times 638$.
Jadi peluang untuk membentuk password legal adalah $\frac{24\times 23\times 22\times 21\times 20\times 638}{26^7}$

5) Diberikan barisan $(x_n)$ dengan suku ke $n$ adalah $x_n=\frac{1}{\sqrt{5}}(a^n-b^n)$ dimana $a=\frac{1+\sqrt{5}}{2}$ dan $b=\frac{1-\sqrt{5}}{2}$. Relasi rekursif yang memenuhi barisan $(x_n)$ adalah...

 Jawab : Perhatikan bahwa
$x_0=0$
$x_1=1$
$x_2=1=x_1+x_0$
$x_3=2=x_2+x_1$
$x_4=3=x_3+x_2$
Akan dibuktikan $x_n=x_{n-1}+x_{n-2}$, untuk $n\geq 2$
Bukti :
$x_n=\frac{1}{\sqrt{5}}(a^2.a^{n-2}-b^2.b^{n-2})$
$x_n=\frac{1}{\sqrt{5}}((\frac{3}{2}+\frac{\sqrt{5}}{2}).a^{n-2}-(\frac{3}{2}-\frac{\sqrt{5}}{2}).b^{n-2})$
$x_n=\frac{3}{2\sqrt{5}}(a^{n-2}-b^{n-2})+\frac{1}{2}(a^{n-2}+b^{n-2})$
$x_n=\frac{3}{2}x_{n-2}+\frac{1}{2}(a^{n-2}+b^{n-2})$
$x_n=\frac{1}{2}x_{n-2}+\frac{1}{2}(a^{n-2}+b^{n-2})+x_{n-2}$
$x_n=\frac{1}{2}(\frac{1}{\sqrt{5}}+1)a^{n-2}+\frac{1}{2}(-\frac{1}{\sqrt{5}}+1)b^{n-2}+x_{n-2}$
$x_n=\frac{1}{2\sqrt{5}}(2a)a^{n-2}+\frac{1}{2\sqrt{5}}(-2b)b^{n-2}+x_{n-2}$
$x_n=\frac{1}{\sqrt{5}}a^{n-1}+\frac{1}{\sqrt{5}}(-b^{n-1})+x_{n-2}$
$x_n=x_{n-1}+x_{n-2}$

6) Lima buah dadu (enam sisi) digulirkan. Peluang bahwa mata dadu yang muncul berjumlah 14 adalah...

 Jawab : Perhatikan banyak kemungkinannya yaitu
-) $1,1,1,5,6 =\frac{5!}{3!}=20$
-) $1,1,2,4,6 =\frac{5!}{2!}=30$
-) $1,1,2,5,5 =\frac{5!}{2!2!}=15$
-) $1,1,3,3,6 =\frac{5!}{2!2!}=15$
-) $1,1,3,4,5 =\frac{5!}{2!}=30$
-) $1,1,4,4,4 =\frac{5!}{2!3!}=10$
-) $1,2,2,3,6 =\frac{5!}{2!}=30$
-) $1,2,2,4,5 =\frac{5!}{2!}=30$
-) $1,2,3,3,5 =\frac{5!}{2!}=30$
-) $1,2,3,4,4 =\frac{5!}{2!}=30$
-) $1,3,3,3,4 =\frac{5!}{3!}=20$
-) $2,2,2,2,6 =\frac{5!}{4!}=5$
-) $2,2,2,3,5 =\frac{5!}{3!}=20$
-) $2,2,2,4,4 =\frac{5!}{3!2!}=10$
-) $2,2,3,3,4 =\frac{5!}{2!2!}=15$
-) $2,3,3,3,3 =\frac{5!}{4!}=5$
Total kemungkinan yang berjumlah $14$ yaitu sebanyak $315$, dan ruang sampel nya adalah $6^5=7776$. Peluangnya yaitu $\frac{315}{7776}=\frac{35}{864}$

7) Setiap bujursangkar pada persegi panjang berukuran $1\times n$ diwarnai dengan menggunakan satu dari tiga warna merah, putih, atau biru. Banyak cara mewarnai persegi panjang $1\times n$ dengan merah, putih, atau biru sehingga terdapat genap buah bujursangkar berwarna putih adalah...

 Jawab : Perhatikan bahwa sama saja kita memilih semua nilai $k$ bilangan genap yang kurang dari atau sama dengan $n$ lalu kita kalikan dengan $2^{n-k}$ karena ada 2 warna yang bukan putih. Sehingga banyak cara mewarnai persegi panjang $1\times n$ sehingga terdapat genap buah bujursangkar berwarna putih adalah $\binom{n}{0}2^{n}+\binom{n}{2}2^{n-2}+\binom{n}{4}2^{n-4}+\cdots+\binom{n}{k}2^{n-k}$
Perhatikan jika $n$ bilangan genap maka $k=n$ maka
$\binom{n}{0}2^{n}+\binom{n}{2}2^{n-2}+\binom{n}{4}2^{n-4}+\cdots+\binom{n}{n}2^{0}\\=\sum_{r=0}^{\frac{n}{2}}\binom{n}{2r}2^{n-2r}1^{2r}$
Jika \(n\) ganjil maka $k=n-1$
$\binom{n}{0}2^{n}+\binom{n}{2}2^{n-2}+\binom{n}{4}2^{n-4}+\cdots+\binom{n}{n-1}2^{1}\\=\sum_{r=0}^{\frac{n-1}{2}}\binom{n}{2r}2^{n-2r}1^{2r}$

8) Untuk setiap bilangan asli $n\in \mathbb{N}$ dengan $n\geq 2$, nilai dari

   $\frac{1}{n}\binom{n}{1}+\frac{2}{n}\binom{n}{2}+\frac{3}{n}\binom{n}{3}+\cdots +\frac{n-1}{n}\binom{n}{n-1}$

adalah...

 Jawab : Perhatikan lemma berikut
$\frac{k}{n}\binom{n}{k}=\binom{n-1}{k-1}$
Bukti : $\frac{k}{n}\binom{n}{k}=\frac{k}{n}\frac{n!}{k!(n-k)!}$
$\frac{k}{n}\binom{n}{k}=\frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}$
$\frac{k}{n}\binom{n}{k}=\binom{n-1}{k-1}$
Jadi, $\frac{1}{n}\binom{n}{1}+\frac{2}{n}\binom{n}{2}+\frac{3}{n}\binom{n}{3}+\cdots +\frac{n-1}{n}\binom{n}{n-1}\\=\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\cdots+\binom{n-1}{n-2}\\=2^{n-1}-1$

Bagian Kedua

1) Suatu graf $A$ disebut komplemen dari graf $\Gamma$ jika $V(a)=V(\Gamma)$ dan sisi $e=(u,v)\in  E(A)$ jika dan hanya jika sisi $e=(u,v)\notin E(\Gamma)$. Komplemen dari graf $\Gamma$ ditulis $\bar{\Gamma}$. Tentukan bilangan bulat positif terkecil $N$ sedemikian sehingga untuk setiap sebarang graf $\Gamma$ dengan $N$ titik senantiasa memuat graf lengkap $K_3$ sebagai subgraf. Kemudian, buktikan!

2) Sebuah papan catur $C$ terdiri dari $i$ baris dan $j$ lajur. Misalkan $b$ menyatakan banyaknya meksimal benteng yang dapat diletakkan pada $C$ sehingga tidak ada dua benteng yang saling menyerang. Tentukan banyaknya cara meletakkan $b$ buah benteng pada $C$ sedemikian sehingga tidak ada dua benteng yang saling menyerang. [Catatan: Pada permainan catur, gerak benteng adalah berarah horisontal (pada baris) atau vertikal (pada lajur).]

3) Misalkan $n$ adalah bilangan bulat positif. Buktikan bahwa

     $\sum_{k=1}^n \frac{(-1)^{k-1}}{k}\binom{n}{k}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$