KimiaMath

Pembahasan Soal ON MIPA-PT Matematika Tahun 2006 Kombinatorika (Isian)

Oleh Aiz — 21 Juni 2019

Kategori: Olimpiade Matematika

Pembahasan Soal ON MIPA-PT Matematika Tahun 2006 Kombinatorika (Isian)

Dalam tulisan ini, kita akan membahas soal Kombinatorika dalam ON MIPA-PT Matematika Tahun 2006. Soal Kombinatorika terdiri dari delapan soal isian singkat dan tiga soal uraian. Dalam tulisan ini, kita akan membahas soal isian singkat.

Nomor 1

Hitung $\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+\cdots+n\binom{n}{n}=\cdots$

Pembahasan

Misalkan $$S=\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+\cdots+(n-1)\binom{n}{n-1}+n\binom{n}{n} \quad\cdots(1)$$ Ingat bahwa $\binom{n}{r}=\binom{n}{n-r}$, sehingga persamaan (1) menjadi $$S=\binom{n}{n-1}+2\binom{n}{n-2}+3\binom{n}{n-3}+\cdots+(n-1)\binom{n}{1}+n\binom{n}{0} \quad\cdots(2)$$

Jumlahkan persamaan (1) dan persamaan (2), sehingga diperoleh $$\begin{aligned} 2S &= n\binom{n}{0}+n\binom{n}{1}+n\binom{n}{2}+\cdots+n\binom{n}{n-1}+n\binom{n}{n} \\ &= n \left[ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+\binom{n}{n} \right] \end{aligned}$$ Berdasarkan teorema binomial, diperoleh $$\begin{aligned} 2S &= n\cdot(1+1)^n \\ 2S &= n\cdot2^n \\ S &= n\cdot2^{n-1} \end{aligned}$$

Nomor 2

Tentukan banyaknya bilangan bulat 7 digit yang disusun dari angka 2, 2, 3, 4, 4, 4, 0.

Pembahasan

Banyaknya susunan tujuh angka pada soal, dapat dihitung menggunakan permutasi dengan unsur berulang, yaitu $$\frac{7!}{2!1!3!1!}$$ Namun, dalam susunan tujuh angka di atas, angka 0 boleh menempati posisi pertama. Padahal, jika 0 berada pada posisi pertama, susunan tujuh angka tersebut membentuk bilangan bulat enam digit.

Banyaknya susunan tujuh angka dengan angka pertama 0 adalah $$\frac{6!}{2!1!3!}$$ Jadi, banyaknya bilangan bulat tujuh digit yang dapat terbentuk adalah $$\begin{aligned} \frac{7!}{2!1!3!1!}-\frac{6!}{2!1!3!} &= \frac{7\cdot6!}{2!3!}-\frac{6!}{2!3!} \\ &= 6\cdot\frac{6!}{2!3!} \\ &= 6\cdot60 \\ &= 360 \end{aligned}$$

Nomor 3

Tentukan solusi dari $a_n=2a_{n-1}+3^n$ dengan $a_1=5$.

Pembahasan

Relasi rekursif pada soal merupakan relasi rekursif non homogen. Untuk menyelesaikan relasi ini, kita perlu menentukan solusi relasi rekursif homogen yang bersesuian, yaitu $a_n^{(h)}$. Kemudian, kita menentukan solusi partikularnya, yaitu $a_n^{(p)}$. Nah, solusi relasi rekursif non homogen merupakan jumlah dari kedua solusi tersebut, yaitu $a_n=a_n^{(h)}+a_n^{(p)}$

Pertama, kita akan menentukan solusi homogen. Relasi rekursif homogen yang bersesuaian adalah $a_n-2a_{n-1}=0$, yang mempunyai solusi $a_n^{(h)}=c\cdot2^n$. Selanjutnya, kita akan menentukan solusi partikular. Diketahui $f(n)=3^n$, sehingga solusi $a_n{(p)}$ yang kita cari berbentuk $A\cdot3^n$. Substitusi $a_n{(p)}=A\cdot3^n$ pada relasi rekursif non homogen. $$A \cdot 3^n = 2 \cdot A \cdot 3^{n-1}+3^n$$ Bagi kedua ruas dengan $3^{n-1}$, sehingga $$A \cdot 3 = 2 \cdot A+3 \Rightarrow A=3$$ Diperoleh $A=3$, sehingga $a_n^{(p)}=3\cdot3^n=3^{n+1}$.

Solusi relasi rekursif non homogen adalah $$a_n=a_n^{(h)}+a_n^{(p)}=c \cdot 2^n+3^{n+1}$$ Terakhir, kita perlu menentukan nilai $c$. Diketahui $a_1=5$, sehingga $$\begin{aligned} a_n &= c \cdot 2^n+3^{n+1} \\ a_1 &= c \cdot 2^1+3^{1+1} \\ 5 &= 2 \cdot c+9 \\ 2 \cdot c &= -4 \\ c &= -2 \end{aligned}$$ Jadi, solusi relasi rekursif non homogen tersebut adalah $$a_n = -2 \cdot 2^n+3^{n+1} = -2^{n+1}+3^{n+1}$$

Nomor 4

Berapa banyaknya permutasi dari huruf-huruf ABCDEFG yang memuat string BA dan GF.

Pembahasan

Banyaknya permutasi huruf-huruf ABCDEFG yang memuat string BA dan GF sama dengan banyaknya permutasi 5 objek berbeda (BA, GF, C, D, dan E), yaitu $5!$.

Nomor 5

Saudara memilih 7 bilangan (tanpa pengembalian) dari himpunan $\{1,2,3,\cdots,14,15\}$. Berapa peluang bahwa jumlah dari 7 bilangan yang terpilih tadi genap?

Pembahasan

Misalkan $A$ adalah kejadian terambilnya tujuh bilangan dari himpunan $\{1,2,3,\cdots,14,15\}$ dengan jumlah genap. Pada himpunan tersebut, terdapat delapan bilangan ganjil dan tujuh bilangan genap.

Agar jumlah ketujuh bilangan tersebut genap, maka di antara tujuh bilangan tersebut harus ada sebanyak genap bilangan ganjil. Sehingga banyaknya bilangan ganjil yang mungkin adalah 0, 2, 4, atau 6.

Kasus I: Terdapat tujuh bilangan genap. Banyaknya cara hal ini dapat terjadi adalah $\binom{8}{0}\binom{7}{7}=1$.

Kasus II: Terdapat dua bilangan ganjil dan lima bilangan genap. Banyaknya cara hal ini dapat terjadi adalah $\binom{8}{2}\binom{7}{5}=588$.

Kasus III: Terdapat empat bilangan ganjil dan tiga bilangan genap. Banyaknya cara hal ini dapat terjadi adalah $\binom{8}{4}\binom{7}{3}=2450$.

Kasus IV: Terdapat enam bilangan ganjil dan satu bilangan genap. Banyaknya cara hal ini dapat terjadi adalah $\binom{8}{6}\binom{7}{1}=196$.

Dengan demikian, $$n(A)=1+588+2450+196=3235$$ Adapun $n(S)$ pada masalah ini adalah $\binom{15}{7}=6435$, sehingga $$P(A)=\frac{n(A)}{n(S)}=\frac{3235}{6435}$$

Nomor 6

Berapa banyak solusi bilangan bulat dari persamaan $x_1+x_2+x_3 = 20$ dengan $2 < x_1 < 6$, $6 < x_2 < 10$, dan $0 < x_3 < 5$.

Pembahasan

Nilai maksimum $x_1$, $x_2$, dan $x_3$ secara berturut-turut adalah 5, 9, dan 4. Karena $5+9+4=18 < 20$, maka banyaknya solusi bilangan bulat dari persamaan tersebut adalah 0 (persamaan tersebut tidak mempunyai solusi).

Nomor 7

Kartu bridge dengan 52 kartu dibagi kepada 4 orang pemain sehingga masing-masing pemain menerima 13 kartu. Banyaknya cara yang dapat dilakukan....

Pembahasan

Misalkan keempat pemain tersebut adalah A, B, C, dan D. Notasi ACDB... menyatakan kartu pertama diterima oleh A, kartu kedua oleh C, dan seterusnya. Dengan demikian, masalah pada soal ini dapat dipandang sebagai banyaknya susunan 52 huruf dalam satu baris, yang terdiri dari masing-masing 13 huruf A, B, C, dan D.

Banyaknya susunan huruf yang mungkin dapat dihitung menggunakan permutasi dengan unsur berulang, yaitu $$\frac{52!}{13!13!13!13!}$$

Nomor 8

Berikan koefisien dari $x^{80}$ dalam ekspansi $\left( x-\frac{1}{x} \right)^{100}$.

Pembahasan

Kita akan menentukan koefisien dari $x^{80}$ dalam ekspansi $\left( x-\frac{1}{x} \right)^{100}$. Perhatikan bahwa $$\begin{aligned} \left( x-\frac{1}{x} \right)^{100} &= \left( \frac{x^2-1}{x} \right)^{100} \\ &= \frac{\left( x^2-1 \right) ^{100}}{x^{100}} \end{aligned}$$ Sehingga koefisien $x^{80}$ dalam ekspansi semula sama dengan koefisien $x^{180}$ dalam ekspansi $(x^2-1)^{100}$.

Berdasarkan teorema binomial, suku yang memuat $x^{180}$ pada $(x^2-1)^{100}$ adalah $$\binom{100}{90}(x^2)^{90}(-1)^{10}=\binom{100}{90}x^{180}$$ Akibatnya, koefisien $x^{180}$ pada $(x^2-1)^{100}$ adalah $\binom{100}{90}$. Jadi, koefisien $x^{80}$ dalam ekspansi $\left( x-\frac{1}{x} \right)^{100}$ adalah $\binom{100}{90}$.

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

Komentar