KimiaMath

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

Oleh Aiz — 07 Juni 2019

Kategori: Olimpiade Matematika

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

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.

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 ini 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{aligned} \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{aligned}$$ 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{aligned} \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{aligned}$$ 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{aligned} \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{aligned}$$

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{aligned} \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{aligned}$$ Sehingga persamaan $(1)$ menjadi $$\begin{aligned} \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{aligned}$$ 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{aligned} 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{aligned}$$

Perhatikan bahwa $$\begin{aligned} 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{aligned}$$ 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{aligned} \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{aligned}$$ 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.

Komentar