KimiaMath

Dalam tulisan ini, kita akan membahas soal Kombinatorika dalam ON MIPA-PT Matematika Tahun 2009. Biasanya, soal Kombinatorika terdiri dari delapan soal isian singkat dan tiga soal uraian. Namun, dalam naskah soal yang saya unduh di internet, hanya tersedia dua soal uraian. Dalam tulisan ini, kita akan membahas soal isian singkat.

INFORMASI
Pembahasan soal uraian kombinatorika telah tersedia. Silakan kunjungi link berikut.
Pembahasan Soal ON MIPA-PT Matematika Tahun 2009 Kombinatorika (Uraian)
Nomor 1

Banyaknya himpunan bagian dari \{ a,b,c,d,e,f,g,h \} yang memuat ketiga elemen a, b, dan f adalah….

PEMBAHASAN
Misalkan X=\{ a,b,c,d,e,f,g,h \}, Y=\{ c,d,e,g,h \}, dan Z adalah sebarang himpunan bagian dari Z. Himpunan bagian dari X yang memuat a, b, dan f dapat ditulis sebagai Z \cup \{ a,b,f \}. Sehingga banyaknya himpunan bagian yang demikian sama dengan banyaknya himpunan bagian dari Y, yaitu sebanyak 2^5=32.

Nomor 2

Pada setiap titik sudut segitiga ABC diletakkan sebuah titik. Kemudian pada sisi AB diletakkan 4 buah titik, pada sisi BC diletakkan 5 buah titik, dan pada sisi AC diletakkan 7 buah titik. Banyaknya segitiga yang dapat dibentuk dari titik-titik tersebut adalah….

PEMBAHASAN
Secara keseluruhan, terdapat sebanyak 19 titik. Untuk membentuk sebuah segitiga, kita memerlukan tiga titik. Banyak cara memilih 3 titik dari 19 titik yang ada adalah

    \[\binom{19}{3}=969\]

Namun, cara tadi juga menghitung tiga titik yang segaris. Padahal segitiga tidak dapat terbentuk dari tiga titik seperti ini. Pada sisi AB terdapat 6 titik (termasuk titik sudut A dan B), sehingga banyaknya triple titik yang segaris adalah

    \[\binom{6}{3}=20\]

Dengan cara yang sama, diperoleh 84 triple titik yang segaris pada sisi AC dan 35 pada sisi BC.

Jadi, banyaknya segitiga yang dapat dibentuk adalah

    \[969-20-84-35=830\]

Nomor 3

Untuk bilangan bulat n \geq 1,

    \[\sum_{k=n}^{2n} \binom{k}{n} 2^{-k}=\cdots\]

PEMBAHASAN

Pertama, kita coba untuk beberapa nilai n.
Untuk n=1, diperoleh

    \[\sum_{k=1}^{2} \binom{k}{1} 2^{-k}= \binom{1}{1} 2^{-1} + \binom{2}{1} 2^{-2}=1\]

Untuk n=2, diperoleh

    \[\sum_{k=2}^{4} \binom{k}{1} 2^{-k}= \binom{2}{2} 2^{-2} + \binom{3}{2} 2^{-3} + \binom{4}{2} 2^{-4}=1\]

Ternyata diperoleh hasil 1. Agar lebih yakin, pembaca dapat melanjutkan untuk beberapa nilai n lainnya. Jadi, kita menduga bahwa

    \[\sum_{k=n}^{2n} \binom{k}{n} 2^{-k}=1\]

Kita perlu membuktikan apakah dugaan ini benar atau hanya berlaku untuk beberapa nilai n pertama.

Perhatikan bahwa

    \begin{align*} \sum_{k=n}^{2n} \binom{k}{n} 2^{-k} &= \sum_{k=0}^{n} \binom{n+k}{n} 2^{-n-k} \\ &= \sum_{k=0}^{n} \binom{n+k}{k} 2^{-n} \cdot 2^{-k} \\ &= 2^{-n} \sum_{k=0}^{n} \binom{k+n}{k} 2^{-k} \end{align*}

Sehingga untuk membuktikan dugaan kita tadi, kita cukup membuktikan bahwa

    \[\sum_{k=0}^{n} \binom{k+n}{k} 2^{-k} = 2^n\]

Kita akan membuktikan pernyataan ini dengan induksi matematika. Pertama, kita misalkan pernyataan ini dengan p(n).

Langkah Dasar
Kita akan menunjukkan bahwa p(1) bernilai benar.
Untuk n=1, diperoleh

    \begin{align*} \sum_{k=0}^n \binom{k+1}{k} 2^{-k} &= \binom{1}{0} 2^{-0} + \binom{2}{1} 2^{-1} \\ &= 1 \cdot 1 + 2 \cdot 2^{-1} \\ &= 2 \\ &= 2^1 \end{align*}

Jadi, p(1) bernilai benar.

Langkah Induksi
Asumsikan p(m) bernilai benar, dengan m suatu bilangan asli, yaitu

    \[\sum_{k=0}^{m} \binom{k+m}{k} 2^{-k} = 2^m\]

Kita akan menunjukkan bahwa p(k+1) juga bernilai benar. Perhatikan bahwa

    \begin{align*} \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k} &= \sum_{k=0}^{m+1} \left[ \binom{k+m}{k} + \binom{k+m}{k-1} \right] 2^{-k} \\ &= \sum_{k=0}^{m+1} \binom{k+m}{k} 2^{-k} + \sum_{k=0}^{m+1} \binom{k+m}{k-1} 2^{-k} \\ &= \sum_{k=0}^m \binom{k+m}{k} 2^{-k} + \binom{2m+1}{m+1} 2^{-m-1} + \sum_{k=0}^m \binom{k+m+1}{k} 2^{-k-1} \\ &= 2^m + \binom{2m+1}{m+1} 2^{-m-1} + \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k-1}-\binom{2m+2}{m+1} 2^{-m-2} \\ &= 2^m + \binom{2m+1}{m+1} 2^{-m-1} + \frac{1}{2} \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k}-\binom{2m+2}{m+1} 2^{-m-2} \end{align*}

Kurangkan kedua ruas dengan

    \[\frac{1}{2} \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k}\]

sehingga diperoleh

    \[\frac{1}{2} \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k} = 2^m + \binom{2m+1}{m+1} 2^{-m-1}-\binom{2m+2}{m+1} 2^{-m-2} \quad \ldots\text{(1)}\]

Berikutnya, perhatikan bahwa

    \begin{align*} \binom{2m+1}{m+1} 2^{-m-1}-\binom{2m+2}{m+1} 2^{-m-2} &= \binom{2m+1}{m+1} 2^{-m-1}-\left[ \binom{2m+1}{m+1} + \binom{2m+1}{m} \right] 2^{-m-2} \\ &= \binom{2m+1}{m+1} 2^{-m-1}-\left[ \binom{2m+1}{m+1} + \binom{2m+1}{m+1} \right] 2^{-m-2} \\ &= \binom{2m+1}{m+1} 2^{-m-1}-2 \cdot \binom{2m+1}{m+1} 2^{-m-2} \\ &= \binom{2m+1}{m+1} 2^{-m-1}-\binom{2m+1}{m+1} 2^{-m-1} \\ &= 0 \end{align*}

Sehingga persamaan (1) menjadi

    \begin{align*} \frac{1}{2} \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k} &= 2^m + 0 \\ 2 \cdot \frac{1}{2} \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k} &= 2 \cdot 2^m \\ \sum_{k=0}^{m+1} \binom{k+m+1}{k} 2^{-k} &= 2^{m+1} \end{align*}

Jadi, p(m+1) juga bernilai benar.
Berdasarkan prinsip induksi matematika, pernyataan p(n) bernilai benar untuk setiap bilangan asli n. Akibatnya

    \[\sum_{k=n}^{2n} \binom{k}{n} 2^{-k} = 2^{-n} \sum_{k=0}^{n} \binom{k+n}{k} 2^{-k} = 2^{-n} \cdot 2^n=1\]

Nomor 4

Banyaknya solusi bulat dari persamaan a+b+c+d=20 dengan a \geq 3, b \geq 1, c \geq 1, dan d \geq 5 adalah ….

PEMBAHASAN
Tulis ulang persamaan pada soal menjadi

    \[(a-3)+(b-1)+(c-1)+(d-5)=10\]

dengan a-3 \geq 0, b-1 \geq 0, c-1 \geq 0, dan d-5 \geq 0.

Misalkan w=a-3, b-1=x, c-1=y, dan d-5=z, sehingga banyaknya solusi bulat persamaan pada soal sama dengan banyaknya solusi bulat dari persamaan w+x+y+z=10, dengan w,x,y,z \geq 0, yaitu

    \[\binom{10+4-1}{10}=\binom{13}{10}=286\]

Nomor 5

Solusi dari relasi rekurensi a_{n+1}=\frac{a_n}{1+na_n} dengan a_0=1 adalah….

PEMBAHASAN
Misalkan a_n=\frac{1}{b_n}, sehingga b_0=\frac{1}{a_0}=\frac{1}{1}=1 dan

    \begin{align*} a_{n+1} &= \frac{a_n}{1+na_n} \\ \frac{1}{b_{n+1}} &= \frac{\frac{1}{b_n}}{1+n \cdot \frac{1}{b_n}} \\ \frac{1}{b_{n+1}} &= \frac{1}{b_n+n} \\ b_{n+1} &= b_n + n \end{align*}

Perhatikan bahwa

    \begin{align*} b_0 &= 1 \\ b_1 &= b_0+0=1+0=1 \\ b_2 &= b_1+1=1+1 \\ b_3 &= b_2+2=1+1+2 \\ b_4 &= b_3+3=1+1+2+3 \\ &\vdots \\ b_n &= 1+1+2+3+\cdots+(n-1) \\ &= 1+\frac{n-1}{2} \cdot [1+(n-1)] \\ &= 1+\frac{n-1}{2} \cdot n \\ &= \frac{2+n(n-1)}{2} \end{align*}

Jadi, solusi dari relasi rekurensi a_{n+1}=\frac{a_n}{1+na_n} dengan a_0=1 adalah

    \[a_n=\frac{1}{b_n}=\frac{2}{2+n(n-1)}\]

Nomor 6

Bilangan bulat positif n terbesar agar 2^n membagi koefisien dari y^{10} pada ekspansi (7y+5)^{100} adalah….

PEMBAHASAN
Berdasarkan teorema binomial, suku yang memuat y^{10} dalam ekspansi (7y+5)^{100} adalah

    \[\binom{100}{10} (7y)^{10} \cdot 5^{90} = \frac{100!}{90!10!} \cdot 5^{90} \cdot 7^{10} \cdot y^{10}\]

Kita akan meninjau faktor pada koefisien y^{10} yang habis dibagi 2, yaitu \frac{100!}{90!10!}. Perhatikan bahwa

    \begin{align*} \frac{100!}{90!10!} &= \frac{100 \cdot 99 \cdot 98 \cdot 97 \cdot 96 \cdot 95 \cdot 94 \cdot 93 \cdot 92 \cdot 91}{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} \\ &= \frac{(2^2 \cdot 25) \cdot 99 \cdot (2 \cdot 49) \cdot 97 \cdot (2^5 \cdot 3) \cdot 95 \cdot (2 \cdot 47) \cdot 93 \cdot (2^2 \cdot 23) \cdot 91}{(2 \cdot 5) \cdot 9 \cdot 2^3 \cdot 7 \cdot (2 \cdot 3) \cdot 5 \cdot 2^2 \cdot 3 \cdot 2} \\ &= 2^3 \cdot \frac{25 \cdot 99 \cdot 49 \cdot 97 \cdot 3 \cdot 95 \cdot 47 \cdot 93 \cdot 23 \cdot 91}{5 \cdot 9 \cdot 7 \cdot 3 \cdot 5 \cdot 3} \end{align*}

Jadi, bilangan bulat positif n terbesar agar 2^n membagi koefisien dari y^{10} pada ekspansi (7y+5)^{100} adalah 3.

Nomor 7

Pada suatu pesta akan dibuat satu rangkaian hiasan buah yang terdiri dari buah salak, apel, dan jeruk. Paling sedikit berapa buah yang harus disediakan untuk menjamin pada rangkaian buah tersebut terdapat 8 salak atau 6 apel atau 9 jeruk?

PEMBAHASAN
Kemungkinan terburuknya adalah kita telah menyediakan sebanyak 20 buah, yang terdiri dari 7 salak, 5 apel, dan 8 jeruk, namun syarat yang diberikan masih belum terpenuhi. Dengan menambahkan satu buah lagi, apapun jenisnya, syarat pada soal akan terpenuhi. Jadi, kita perlu menyediakan paling sedikit 21 buah untuk menjamin pada rangkaian buah tersebut terdapat 8 salak atau 6 apel atau 9 jeruk.

Nomor 8

Banyaknya cara memilih 4 bilangan berbeda dari himpunan \{1,2,3,4,5,6,7,8,9,10\} sehingga dari 4 bilangan terpilih tidak terdapat 2 bilangan berurutan adalah….

PEMBAHASAN
Misalkan A=\{1,2,3,4,5,6,7,8,9,10\}.
Tinjau salah satu kemungkinan bilangan yang terpilih pada A, misalnya \{ 1,3,6,8 \}, dan bentuk ketaksamaan 0<1<3<6<8<11. Perhatikan banyaknya bilangan bulat di antara setiap pasangan bilangan berurutan pada ketaksamaan tersebut. Kita memperoleh 0, 1, 2, 1, 2: 0 karena tidak ada bilangan bulat di antara 0 dan 1, 1 untuk banyaknya bilangan bulat di antara 1 dan 3, 2 untuk banyaknya bilangan bulat di antara 3 dan 6, dan seterusnya. Kelima bilangan bulat tersebut memiliki jumlah 6.

Tinjau kemungkinan lainnya, misalnya \{ 2,4,7,10 \} dengan ketaksamaan 0<2<4<7<10<11. Dari sini, kita memperoleh 1, 1, 2, 2, 0 yang juga berjumlah 6.

Berikutnya, tinjau bilangan bulat non negatif 0, 3, 1, 2, 0 yang memiliki jumlah 6. Bilangan ini dapat dipandang sebagai banyaknya bilangan bulat di antara setiap pasangan bilangan berurutan pada ketaksamaan 0<1<5<7<10<11, yang bersesuaian dengan terpilihnya \{ 1,5,7,10 \} pada himpunan A.

Dari sini, kita dapat melihat adanya korespondensi satu-satu antara banyaknya cara memilih empat bilangan pada A dengan banyaknya solusi bulat dari persamaan x_1+x_2+x_3+x_4+x_5=6, dengan x_1,x_5 \geq 0 dan x_2,x_3,x_4 \geq 1. Syarat x_2,x_3,x_4 \geq 1 diberikan untuk menjamin tidak adanya bilangan berurutan di antara keempat bilangan yang terpilih.

Banyaknya solusi bulat dari persamaan di atas sama dengan banyaknya solusi bulat dari persamaan y_1+y_2+y_3+y_4+y_5=3, dengan y_1,y_2,y_3,y_4,y_5 \geq 0, yaitu

    \[\binom{3+5-1}{3}=\binom{7}{3}=35\]

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

Terdapat 2 Komentar

Tina

25 Januari 2019 pada 20:34

MaasyaaAllah…

Mirza

22 Januari 2019 pada 09:04

Pak. Bapak bantu selesaikan dan Post pembahasaan bagian analisis real jg pak .

Tinggalkan Komentar