Pembahasan Soal ON-MIPA PT Matematika

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

Pembahasan Soal ON-MIPA PT Matematika Bidang Kombinatorika Tahun 2017

                             

Bagian Pertama

1. Pada sebuah pesta pernikahan terdapat enam orang (termasuk pengantin) yang hendak berfoto. Banyak cara menata pose foto dalam satu baris dari keenam orang tersebut sedemikian sehingga pengantin berdiri tidak saling berdekatan adalah
Jawab : Andaikan kita buat pengantin berdekatan maka banyaknya adalah $5!=120$. Jadi, Banyak cara menata pose foto dalam satu baris dari keenam orang tersebut sedemikian sehingga pengantin berdiri tidak saling berdekatan adalah $6!-5!=720-120=600$
2. Sebuah rangkaian digit biner adalah sebuah barisan yang terdiri dari $1$ dan $0$. Banyaknya rangkaian digit biner yang terdiri atas tepat delapan digit $0$ dan tepat sepuluh digit $1$ sedemikian sehingga setiap kemunculan digit $0$ segera diikuti oleh digit $1$ adalah
Jawab : Karena setiap kemunculan digit $0$ segera diikuti oleh digit $1$ maka kita hanya menempatkan 2 digit $1$ pada $\_ 01\_ 01\_ 01\_ 01\_ 01\_ 01\_ 01\_ 01\_ $ sehingga terdapat $9\times 9=81$ rangkaian.
3. Pada sebuah lemari terdapat $25$ helai baju yang terdiri atas 4 ukuran. $5$ helai baju berukuran S, $4$ helai baju berukuran M, $9$ helai baju berukuran L, dan $7$ helai baju berukuran XL. Untuk menjamin telah terambil $7$ helai baju berukuran sama, maka sedikitnya total helai baju yang harus diambil dari lemari adalah
Jawab : Jika kita mengambil $21$ helai baju kita dapat mengatur sehingga tidak ada $7$ helai baju berukuran sama. yaitu $5$ ukuran S, $4$ ukuran M, $6$ ukuran L, dan $6$ ukuran XL. Jadi, menurut PHP untuk memastikan bahwa telah terambil $7$ helai baju berukuran sama kita harus mengambil $22$ helai baju.
4. Sebuah keluarga besar beranggotakan $14$ orang anak yang terdiri dari dua kelahiran kembar tiga identik, tiga kelahiran kembar dua identik, dan dua anak yang lain. Bila kembar identik tak dapat dibedakan, maka banyak pose foto berdiri dalam satu baris dari $14$ orang anak tersebut adalah
Jawab : Kita bisa menggunakan prinsip permutasi dengan unsur yang sama yaitu $\frac{14!}{3!3!2!2!2!1!1!}=302702400$
5. Solusi dari relasi rekurensi $a_n=2a_{n−1}+3a_{n−2}$ dengan $a_0 = 1$ dan $a_1 = 2$ adalah
Jawab : $a_n-2a_{n-1}-3a_{n-2}=0$
$r^2-2r-3=0$
$(r-3)(r+1)=0$
$r_1=3$ dan $r_2=-1$
sehingga $a_n=c_1.3^n+c_2.(-1)^n$
Substitusi $n=0$ maka $a_0=c_1+c_2$
$c_1+c_2=1$
Substitusi $n=1$ maka $a_1=3c_1-c_2$
$3c_1-c_2=2$
Sehingga didapat $c_1=\frac{3}{4}$ dan $c_2=\frac{1}{4}$
$a_n=\frac{3^{n+1}+(-1)^n}{4}$
6. Banyak cara menugaskan 5 pekerjaan berbeda ke 4 orang pegawai berbeda sedemikian sehingga setiap pegawai ditugaskan ke paling sedikit satu pekerjaan adalah
Jawab : Perhatikan ada tepat satu pegawai mendapatkan 2 pekerjaan, cara memilih satu pegawai yang mendapat 2 pekerjaan adalah $4$. Dan banyak menyusun 5 pekerjaan ke dalam 1,1,1,2 adalah $C(5,1)C(4,1)C(3,1)C(2,2)=5\times 4\times 3\times 1=60$. Jadi, Banyak cara menugaskan 5 pekerjaan berbeda ke 4 orang pegawai berbeda sedemikian sehingga setiap pegawai ditugaskan ke paling sedikit satu pekerjaan adalah $4\times 60=240$
7. Dalam bentuk yang paling sederhana fungsi pembangkit biasa (ordinary generating function), $g(x)$, dari barisan $(0,1,0,1,0,1,. . .)$ adalah
Jawab : $g(x)=\frac{a_0x^0}{0!}+\frac{a_1x^1}{1!}+\frac{a_2x^2}{2!}+\frac{a_3x^3}{3!}+\cdots $
$g(x)=\frac{x}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots $
$g(x)=sinh(x)$
8. Tentukan semua solusi $(a, b, c)$ dari Persamaan Diophantine $2^a + 5^b = c^2$



Bagian Kedua
1. Seorang petinju mempunyai waktu $75$ minggu untuk mempertahan gelar. Untuk itu pelatih menjadwalkan program latih tanding. Pelatih merencanakan sedikitnya terdapat satu latih tanding dalam satu minggu, tetapi tidak lebih dari total $125$ latih tanding dalam periode $75$ minggu. Perlihatkan ada periode waktu yang terdiri atas beberapa minggu berturutan sehingga terdapat tepat $24$ latih tanding dalam periode waktu tersebut.
2. Diberikan bilangan bulat $n\geq 5$ Tuliskan sebuah argumentasi kombinatorial untuk memperlihatkan bahwa
$\binom{2n}{5}=2\binom{n}{5}+2n\binom{n}{4}+(n^2-n)\binom{n}{3}$
Jawab : Jika kita punya $2n$ objek, kita pisah menjadi 2 di $A$ dan $B$ masing-masing berisikan $n$ objek, ruas kiri menyatakan kita memilih $5$ buah objek dari $2n$ objek, itu sama halnya kita bisa memilih $5$ objek sekaligus di $A$ atau kita bisa memilih $5$ objek sekaligus di $B$ yang nilainya adalah $2\binom{n}{5}$ atau juga kita bisa memilih $4$ objek di $A$ dan $1$ objek di $B$ atau $1$ objek di $A$ dan $4$ objek di $B$ yang nilainya adalah $2\binom{n}{4}\binom{n}{1}=2n\binom{n}{4}$ atau juga kita bisa memilih $3$ objek di $A$ dan $2$ objek di $B$ atau $2$ objek di $A$ dan $3$ objek di $B$ yang nilainya adalah $2\binom{n}{3}\binom{n}{2}=(n^2-n)\binom{n}{3}$. Jadi $\binom{2n}{5}=2\binom{n}{5}+2n\binom{n}{4}+(n^2-n)\binom{n}{3}$
3. Suatu sisi $e$ di graf $G$ dikatakan suatu cut edge jika jumlah komponen dari $G\backslash e$ lebih dari jumlah komponen dari $G$. Buktikan bahwa, suatu sisi $e$ adalah cut edge di $G$ jika dan hanya jika $e$ tidak termuat di setiap lingkaran di $G$.