Pembahasan Soal ON-MIPA PT Matematika

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

Pembahasan Soal ON-MIPA PT Matematika Bidang Kombinatorika Tahun 2014

Bagian Pertama

1) Pada suatu daerah, setiap nomor telepon terdiri dari 6 angka yang diawali dengan angka 6. Jika anda mengajukan pemasangan untuk mendapatkan nomor telepon yang memuat tidak lebih dari 4 angka berbeda, besarnya peluang Anda mendapat nomor dimaksud adalah...
   Jawab : misalkan $a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}$ adalah nomor telepon yang mungkin yang memuat tidak lebih dari 4 angka berbeda dengan $a_{1}=6$. Lebih mudah kita cari komplemennya yaitu nomor telepon yang memuat 5 atau 6 angka berbeda.
-) Kasus ada 2 angka yang sama
   Kalau yang sama adalah angka 6 maka banyaknya adalah $\binom{5}{1}.9.8.7.6=15120$
   Kalau yang sama bukan angka 6 maka banyaknya adalah $\binom{5}{2}.9.8.7.6=30240$
-) Kasus semuanya berbeda banyaknya adalah $9.8.7.6.5=15120$
Sehingga banyak nomor telepon yang memuat 5 atau 6 angka berbeda adalah $15120+30240+15120=60480$. Banyak nya keseluruhan nomor telepon adalah $10^5=100000$. Peluang untuk mendapatkan nomor telepon yang memuat tidak lebih dari 4 angka berbeda yaitu $1-\frac{60480}{100000}=\frac{247}{625}$
2) Solusi dari fungsi rekursif $f(n+1)=f(n)+2f(n-1) \forall n>2$ dimana $f(1)=1, f(2)=5$, adalah...
   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}+1f(n)=2^n+(-1)^n$3) Koefisien dari$x^{128}$dalam ekspansi$\left(\frac{x}{2}-\frac{2}{7x}\right)^{236}$adalah...    Jawab : perhatikan bahwa$\left(\frac{x}{2}-\frac{2}{7x}\right)^{236}=\sum\limits_{k=1}^{236}\binom{236}{k}\left(\frac{x}{2}\right)^{236-k}\left(-\frac{2}{7x}\right)^{k}$Koefisien$x^{128}$diperoleh dari$x^{236-k}.\left(\frac{1}{x}\right)^k=x^{128}$Sehingga$236-k-k=128$atau$k=54\binom{236}{54}\left(\frac{x}{2}\right)^{236-54}\left(-\frac{2}{7x}\right)^{54}=\binom{236}{54}\left(\frac{x}{2}\right)^{182}\left(-\frac{2}{7x}\right)^{54}$Jadi koefisien dari$x^{128}$dalam ekspansi$\left(\frac{x}{2}-\frac{2}{7x}\right)^{236}$adalah$\binom{236}{54}\left(\frac{1}{2}\right)^{128}\left(\frac{1}{7}\right)^{54}$4) Banyaknya semua susunan huruf yang terdiri dari tujuh huruf berbeda sedemikian sehingga huruf pertama, huruf di tengah, dan huruf terakhir adalah sebuah huruf vokal, sedangkan empat huruf lainnya adalah huruf konsonan adalah...    Jawab : banyak huruf vokal ada$5$, banyak huruf konsonan$26-5=21$Jadi banyak semua susunan huruf yang terdiri dari tujuh huruf berbeda sedemikian sehingga huruf pertama, huruf di tengah, dan huruf terakhir adalah sebuah huruf vokal, sedangkan empat huruf lainnya adalah huruf konsonan adalah$^5P_3\times ^21P_4=5.4.3.21.20.19.18=8618400$5) Pada sebuah wahana permainan terdapat 4 jenis koin bernilai 1.000, 5.000, 10.000, dan 25.000. Banyaknya cara untuk mendapatkan 7 koin dengan total nilai 49.000 adalah...   Jawab : perhatikan persamaan$1.000a+5.000b+10.000c+25.000d=49.000$dengan$a+b+c+d=7$Persamaan bisa disederhanakan menjadi$a+5b+10c+25d=49$
Perhatikan bahwa $\frac{a}{5}+b+2c+5d=9+\frac{4}{5}$. Jelas $a=4$
$b+c+d=3$ dan $b+2c+5d=9$
Dengan begitu $2b+3c+6d=12$
Perhatikan juga $\frac{2b}{3}+c+2d=4$. Jelas $b= 3$ tidak memenuhi maka $b=0$ dan $c+2d=4$
Dari persamaan sebelumnya kita bisa mendapatkan $c+4d=6$ maka dari itu $d=1$ dan $c=1$
Jadi banyaknya cara untuk mendapatkan 7 koin dengan total nilai 49.000 adalah 1
6) Barisan $(a_n)$ diperoleh dari barisan bilangan asli 1,2,3,... dengan menghapus suku berbentuk kuadrat dan kubik. Suku $a_{1.000.000}$ adalah...
   Jawab : Jelas $a_{1.000.000}>1.000.000$. Kita coba saja untuk $1.001.000$
Karena $\lfloor\sqrt{1.001.000}\rfloor=1000 , \lfloor\sqrt[3]{1.001.000}\rfloor=100 \text{dan} \lfloor\sqrt[6]{1.001.000}\rfloor=10$. Maka $1.001.000$ terletak pada urutan $1.001.000-(1000+100-10)=999910$ Jadi $a_{999.910}=1.001.000$. Perhatikan bahwa $1001^2=1002001$ dan $101^3=1030301$ maka $a_{1.000.000}=1.001.000+90=1.001.090$
7) Diberikan bilangan ganjil $n\geq 5$. Banyaknya permutasi atas himpunan $\{1, 2, 3, \cdots, n\}$ sedemikian sehingga tidak terdapat dua bilangan ganjil yang berurutan adalah...
   Jawab : Untuk kasus n bilangan ganjil maka banyak susunannya jelas $\frac{n+1}{2}.\frac{n-1}{2}=\frac{n^2-1}{4}$ yaitu perkalian banyaknya bilangan ganjil dan genap.
               Untuk kasus n bilangan genap maka banyak susunannya yaitu $\frac{n}{2}.\frac{n}{2}.(2+\frac{n}{2}-1)=\frac{n^2}{4}\left(\frac{n}{2}+1\right)$
8) Untuk bilangan asli $n$ nilai dari $3.2\binom{n}{3}+4.3\binom{n}{4}+\cdots +n(n-1)\binom{n}{n}$ adalah...

   Jawab : Seharusnya untuk $n\geq 2 , n\in\mathbb{N}$
  Lemma $k.\binom{n}{k}=n\binom{n-1}{k-1}$
  Bukti :
             $\begin{align}k.\binom{n}{k} &=k.\frac{n!}{k!(n-k)!}\\               &=n.\frac{(n-1)!}{(k-1)!(n-k)!}\\               &=n.\frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}\\               &=n.\binom{n-1}{k-1}\end{align}$
Sehingga
$\begin{align}3.2\binom{n}{3}+4.3\binom{n}{4}+\cdots +n(n-1)\binom{n}{n} &=2n\binom{n-1}{2}+3n\binom{n-1}{3}+\cdots+(n-1)n\binom{n-1}{n-1}\\ &=n(n-1)\binom{n-2}{1}+n(n-1){n-2}{2}+\cdots+n(n-1)\binom{n-2}{n-2}\\ &=n(n-1)\binom{n-2}{0}+n(n-1)\binom{n-2}{1}+n(n-1){n-2}{2}+\cdots+n(n-1)\binom{n-2}{n-2}-n(n-1)\\ &=n(n-1)2^{n-2}-n(n-1)\\ &=n(n-1)(2^{n-2}-1)\end{align}$

Bagian Kedua

1) Sebuah titik $(a_1,a_2,\cdots ,a_k)\in\mathbb{R}^k$ dikatakan sebuah titik lattice jika $a_i$ adalah bilangan bulat untuk semua $i=1,2,\cdots ,k$. Perlihatkan bahwa setiap himpunan $L_k$ yang terdiri dari $2^k+1$ buah titik lattices, terdapat dua titik lattice $l_1,l_2\in L_k$ sedemikian sehingga titik tengah dari $l_1$ dan $l_2$ adalah sebuah titik lattice.
2) Misalkan $G$ adalah sebuah graf dengan $n$ titik $\{v_1,v_2,\cdots,v_n\}$ sebuah matriks ketetanggaan $A=(a_{ij})$ dari graf $G$ didefinisikan sebagai sebuah matriks bujursangkar berordo $n$ dengan entri $a_{ij}=\begin{cases} 1 &, \text{ bila } {v_i,v_j} \text{ adalah sebuah sisi di } G\\ 0 &, \text{ bila } {v_i,v_j} \text{ bukan sebuah sisi di } G. \end{cases}$
Buktikan bahwa entri $a_{ij}^{(m)}$ dari $A^m$ menyatakan banyaknya jalan $(walk)$ dengan panjang $m$ yang menghubungkan titik $v_i$ dan titik $v_j$.