Materi, Soal, dan Pembahasan – Teorema Bintang dan Garis

Salah satu teorema yang mewarnai dunia kombinatorika dan sering dipakai untuk menyelesaikan soal terkait konfigurasi susunan objek adalah Teorema Bintang dan Garis (Stars and Bars Theorem). Teorema ini kadang-kadang juga menggunakan istilah “Sumpit dan Batu” atau “Bola dan Garis”. Teorema ini dipopulerkan oleh William Feller (matematikawan Kroasia-Amerika) dalam bukunya yang membahas tentang peluang (probability).

Contoh masalah yang membuat kita harus berpikir keras sebelum mengenal Teorema Bintang dan Garis adalah sebagai berikut.

Stimulus

Ada berapa banyak cara memasukkan 8 buah bola yang identik (sama persis) ke dalam 3 keranjang yang berbeda?

Masalah ini tidak bisa diselesaikan dengan cara biasa karena kita tidak tahu persis apa yang harus dipilih atau disusun karena keidentikan bola tersebut. Kemungkinan pertama yang dapat dilakukan adalah menuliskannya satu per satu. Misalkan $(a, b, c)$ menyatakan bahwa kita akan memasukkan $a$ bola pada kotak pertama, $b$ bola kotak kedua, dan $c$ bola pada kotak ketiga. Dengan demikian, beberapa cara berbeda yang dimaksud adalah $(8, 0, 0), (6, 2, 0),$ $(3, 4, 1),$ $(5, 1, 2),$ dan sebagainya. Banyak sekali! Tentu sangat tidak efisien bila kita menuliskannya satu per satu seperti tadi.

Apa lagi yang bisa dicoba? Bagaimana kalau menghitung banyak cara memasukkan bola ke masing-masing kotak, kemudian menggunakan aturan perkalian? Sayangnya, apa yang dimasukkan di satu kotak memengaruhi apa yang dimasukkan di kotak lain sehingga dapat kita katakan bahwa kejadian-kejadian tersebut tidak saling bebas (dependen). Oleh karena itu, aturan perkalian kurang tepat untuk dipakai dalam menyelesaikan masalah ini.

Teorema Bintang dan Garis hadir untuk menyelesaikannya. Bayangkan $8$ bola yang akan kita masukkan tadi kita jajarkan dalam satu baris, kemudian kita lambangkan dengan bintang $(\color{red}{\bigstar}).$ Gunakan satu lambang yang sama karena bolanya identik.
$$\color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar}$$Untuk menentukan bola mana yang masuk ke masing-masing kotak, kita gunakan suatu pemisah—seperti partisi buku-buku di perpustakaan—yang kita lambangkan sebagai garis vertikal $(\mid).$
$$\color{red}{\bigstar} \color{red}{\bigstar} \mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar}$$

Partisi buku-buku di perpustakaan

Karena kita akan menempatkan bola-bola ke dalam $3$ kotak, kita membutuhkan $2$ partisi yang diwakili oleh garis vertikal tersebut. Konfigurasi di atas menunjukkan bahwa kita akan memasukkan $2$ bola pada kotak pertama, $3$ bola pada kotak kedua, dan $3$ bola pada kotak ketiga.

Nah, kalau begitu idenya sudah dapat! Kita hanya perlu menggeser kedua partisi tersebut sehingga kita akan peroleh konfigurasi yang lain seperti contoh berikut.
$$\color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \mid \color{red}{\bigstar} \mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar}$$Itu berarti kita akan memasukkan $4$ bola pada kotak pertama, $1$ bola pada kotak kedua, dan $3$ bola pada kotak ketiga.

Jadi, banyak cara memasukkan $8$ buah bola identik ke dalam $3$ kotak berbeda sama dengan banyak cara menyusun $8$ bintang dan $2$ garis. Dengan kata lain, kita cukup mencari banyak cara menempatkan $2$ garis tersebut di $8 + 2 = 10$ tempat yang tersedia (anggap kita seperti mengisi 10 slot dengan menggunakan garis dan bintang itu)
$$\mid \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \color{red}{\bigstar} \mid$$Itu berarti kita akan memasukkan $0$ bola pada kotak pertama, $8$ bola pada kotak kedua, dan $0$ bola pada kotak ketiga.

Dengan menggunakan aturan kombinasi, kita peroleh
$$C(10,2) = \dfrac{10!}{8! \cdot 2!} = 45.$$

Sekarang, kita tinggal memperumum. Kita punya $n$ buah bola identik yang akan dimasukkan ke dalam $k$ kotak yang berbeda. Sama seperti tadi, bayangkan kita akan menyusun $n$ bintang. Karena ada $k$ kotak, kita membutuhkan $(k-1)$ partisi/garis. Ini berarti kita akan menyusun $(n+k-1)$ objek. Oleh karena itu, banyak cara menyusun $n$ buah bola ke dalam $k$ kotak yang berbeda sama aja dengan banyak cara memilihkan tempat bagi $(k-1)$ partisi tadi ke $(n+k-1)$ tempat yang tersedia, yakni
$$\boxed{{\large C(n+k-1, k-1)}}$$Bentuk terakhir inilah yang dikenal sebagai rumus dari Teorema Bintang dan Garis. Sekarang, kalian juga pasti sudah tahu alasan mengapa nama teorema tersebut seperti itu, ada bintang dan ada garisnya.

Baca Juga: Masalah Kombinatorika: Mencari Banyak Rute 

Di sisi lain, ternyata masalah kontekstual di atas dapat direpresentasikan oleh pertanyaan berikut: Ada berapa solusi bulat nonnegatif dari persamaan $$x_1 + x_2 + x_3 + \cdots + x_k = n?$$Solusi bulat nonnegatif artinya solusi yang melibatkan bilangan-bilangan bulat yang lebih besar atau sama dengan nol. Perhatikan bahwa ini sebenarnya sama saja dengan permasalahan penempatan bola ke dalam kotak tadi. Letakkan $n$ buah bola ke dalam $k$ kotak. Masing-masing variabel menyatakan banyaknya bola yang dimasukkan pada kotak tersebut. Sebagai contoh, $x_3$ menyatakan banyak bola yang akan dimasukkan pada kotak ketiga. Ketika mencari banyaknya cara memasukkan $8$ buah bola ke dalam $3$ kotak yang berbeda, kita sebenarnya sedang mencari banyak solusi bulat nonnegatif dari persamaan $$x_1+x_2+x_3 = 8$$dengan $x_1, x_2, x_3$ berturut-turut menyatakan banyak bola yang akan dimasukkan pada kotak pertama, kedua, dan ketiga.

Teorema Bintang dan Garis

Banyak cara memasukkan $n$ buah benda yang identik ke dalam $k$ kotak yang berbeda adalah
$$\boxed{{\large C(n+k-1, k-1)} = \displaystyle \binom{n+k-1}{k-1}}$$Secara ekuivalen, banyaknya solusi bulat nonnegatif untuk persamaan $$x_1+x_2+x_3+\cdots+x_k = n$$adalah $$\boxed{{\large C(n+k-1, k-1)} = \displaystyle \binom{n+k-1}{k-1}}$$

Berikut telah disediakan sejumlah soal dan pembahasan terkait penggunaan Teorema Bintang dan Garis yang dikumpulkan dari berbagai sumber. Semoga bermanfaat.

Today Quote

Ada yang sibuk berjuang sampai tidur terasa nikmat saking lelahnya. Ada juga yang sibuk tidur-tiduran sampai badan sakit semua. Kita sama-sama punya $24$ jam, tinggal bagaimana cara kita menghargainya.

Bagian Pilihan Ganda

Soal Nomor 1
Banyaknya solusi bulat tak negatif yang memenuhi persamaan $x_1 + x_2 + x_3 + x_4 = 15$ adalah $\cdots \cdot$
A. $136$                   D. $680$
B. $153$                   E. $816$
C. $455$

Pembahasan

Dengan menggunakan Teorema Bintang dan Garis, permasalahan di atas ekuivalen dengan mencari banyaknya cara menempatkan $n = 15$ bola identik ke dalam $k = 4$ kotak berbeda, yaitu sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{15+4-1}{4-1} \\ & = \binom{18}{3} \\ & = \dfrac{18!}{15! \cdot 3!} \\ & = 816 \end{aligned}$$Jadi, ada $\boxed{816}$ solusi bulat tak negatif yang memenuhi persamaan tersebut.
(Jawaban E)

[collapse]

Soal Nomor 2
Pada persamaan $x_1 + x_2 + x_3 = 12,$ $x_i$ adalah bilangan bulat nonnegatif. Banyak kemungkinan solusinya adalah $\cdots \cdot$
A. $78$                      D. $220$
B. $91$                      E. $495$
C. $165$

Pembahasan

Dengan menggunakan Teorema Bintang dan Garis, permasalahan di atas ekuivalen dengan mencari banyaknya cara menempatkan $n = 12$ bola identik ke dalam $k = 3$ kotak berbeda, yaitu sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{12+3-1}{3-1} \\ & = \binom{14}{2} \\ & = \dfrac{14!}{12! \cdot 2!} \\ & = 91 \end{aligned}$$Jadi, banyak kemungkinan solusi persamaan tersebut adalah $\boxed{91}$
(Jawaban B)

[collapse]

Baca Juga: Soal dan Pembahasan – Peluang dan Kombinatorika (Tingkat SMA) 

Soal Nomor 3
Banyaknya cara memasukkan $9$ bunga yang identik ke dalam $3$ vas yang berbeda dengan syarat setiap vasnya minimal terdapat $1$ bunga adalah $\cdots \cdot$
A. $15$               C. $24$              E. $36$
B. $20$               D. $28$

Pembahasan

Pertama, masukkan $1$ bunga ke masing-masing vas sehingga sekarang tersisa $6$ bunga. Sekarang kita tinggal menempatkan $6$ bunga ini ke masing-masing vas tersebut dengan kondisi syarat nonnegatif telah terpenuhi sehingga Teorema Bintang dan Garis dapat kita terapkan.
Banyak cara membagikan $n = 6$ bunga yang identik ke dalam $k = 3$ vas yang berbeda adalah sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n+k-1}{k-1} & = \binom{6+3-1}{3-1} \\ & = \binom{8}{2} \\ & = \dfrac{8!}{6! \cdot 2!} \\ & = 28 \end{aligned}$$Jadi, banyak cara memasukkan bunga-bunga tersebut ke dalam vas adalah $\boxed{28}$
(Jawaban D)

[collapse]

Soal Nomor 4
Dari sejumlah besar koin 25-an, 50-an, 100-an, dan 500-an, dalam berapa banyak cara $5$ koin dapat diambil?
A. $21$                      D. $56$
B. $27$                      E. $81$
C. $48$

Pembahasan

Masalah di atas ekuivalen dengan mencari banyaknya solusi bulat nonnegatif yang memenuhi persamaan
$$x_1 + x_2 + x_3 + x_4 = 5$$dengan $x_1, x_2, x_3, x_4$ berturut-turut menyatakan banyaknya koin 25-an, koin 50-an, koin 100-an, dan koin 500-an yang terambil.
Dengan menggunakan Teorema Bintang dan Garis untuk $n = 5$ dan $k = 4,$ diperoleh
$$\begin{aligned} \displaystyle \binom{n+k-1}{k-1} & = \binom{5+4-1}{4-1} \\ & = \binom{8}{3} \\ & = \dfrac{8!}{5! \cdot 3!} \\ & = 56. \end{aligned}$$Jadi, banyak cara pengambilan $5$ koin adalah $\boxed{56}$
(Jawaban D)

[collapse]

Soal Nomor 5
Banyaknya pasangan tripel terurut dari bilangan bulat positif $(a, b, c)$ sedemikian sehingga $a+b+c=8$ adalah $\cdots \cdot$
A. $15$                 C. $21$                 E. $35$
B. $18$                 D. $28$

Pembahasan

Perhatikan bahwa ketiga variabel tersebut memiliki nilai terkecil $1.$ Untuk menerapkan Teorema Bintang dan Garis, kita harus membuat persamaan dengan variabel dengan nilai terkecil $0.$
Sekarang misalkan $a’ = a-1,$ $b’ = b-1,$ dan $c’ = c-1$ sedemikian sehingga kita ingin mencari pasangan terurut $(a’, b’, c’)$ dengan syarat $a’ \ge 0, b’ \ge 0, c’ \ge 0.$ Kita peroleh persamaan yang baru sebagai berikut.
$$\begin{aligned} (a’ + 1) + (b’ + 1) + (c’ + 1) & = 8 \\ a’ + b’ + c’ & = 5 \end{aligned}$$Syarat nonnegatif telah terpenuhi oleh tiga variabel tersebut sehingga kita bisa menerapkan Teorema Bintang dan Garis untuk $n = 5$ dan $k = 3.$
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{5+3-1}{3-1} \\ & = \binom{7}{2} \\ & = \dfrac{7!}{5! \cdot 2!} \\ & = 21 \end{aligned}$$Jadi, banyak pasangan terurut yang dimaksud adalah $\boxed{21}$
(Jawaban C)

[collapse]

Soal Nomor 6
Diberikan persamaan $x_1 + x_2 + x_3 + x_4 = 13$ dengan syarat $x_1 > 0,$ $x_2 > 1,$ $x_3 > 2,$ dan $x_4 \geq 0$ dengan $x_i$ berupa bilangan bulat. Banyak kemungkinan solusinya adalah $\cdots \cdot$
A. $80$                    D. $150$
B. $100$                  E. $180$
C. $120$

Pembahasan

Perhatikan bahwa nilai minimum variabel $x_1, x_2, x_3,$ dan $x_4$ berturut-turut adalah $1, 2, 3,$ dan $0.$ Dengan menganalogikan masalah ini sebagai masalah bola dan kotak, kita punya $13$ bola identik dan $4$ kotak berbeda. Tempatkan $1$ bola pada kotak pertama, $2$ bola pada kotak kedua, dan $3$ bola pada kotak ketiga sehingga sekarang tersisa $13-(1+2+3) = 7$ bola.
Selanjutnya, kita tinggal mencari banyak cara menempatkan $n = 7$ bola tersebut ke dalam $k = 4$ kotak dengan menggunakan Teorema Bintang dan Garis.
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{7+4-1}{4-1} \\ & = \binom{10}{3} \\ & = \dfrac{10!}{7! \cdot 3!} \\ & = 120 \end{aligned}$$Jadi, banyak kemungkinan solusi persamaan tersebut adalah $\boxed{120}$
(Jawaban C)

[collapse]

Baca Juga: Materi, Soal, dan Pembahasan – Prinsip Inklusi-Eksklusi

Soal Nomor 7
Berapa banyak cara memilih $5$ huruf dari $26$ huruf alfabet Inggris $(A, B, C, \cdots, Z)$ dengan syarat: huruf kecil dan kapital tidak dipermasalahkan, kemunculan huruf boleh berulang, dan kata yang termasuk anagram dianggap sama (contohnya: KURSI dianggap sama dengan RUKIS)?
A. $14.950$
B. $27.405$
C. $65.780$
D. $142.506$
E. $169.911$

Pembahasan

Kita punya $26$ pilihan huruf dan akan ditempatkan pada $5$ posisi berbeda. Kemunculan huruf boleh lebih dari sekali, atau mungkin tidak sama sekali. Andaikan $C_A, C_B, C_C, \cdots, C_Z$ berturut-turut menyatakan banyak kemunculan huruf $A, B, C, \cdots Z$ sehingga kita peroleh persamaan berikut.
$$C_A + C_B + C_C + \cdots + C_Z = 5$$Fokus kita hanya mengatur seberapa banyak kemunculan 26 huruf tersebut. Menurut Teorema Bintang dan Garis untuk $n = 5$ dan $k = 26,$ kita peroleh
$$\begin{aligned} \displaystyle \binom{n+k-1}{k-1} & = \binom{5+26-1}{26-1} \\ & = \binom{30}{25} \\ & = \dfrac{30!}{25! \cdot 5!} \\ & = 142.506 \end{aligned}$$Jadi, banyak cara memilih $5$ huruf tersebut adalah $\boxed{142.506}$
(Jawaban D)

[collapse]

Soal Nomor 8
Sebanyak $20$ buah apel dan $15$ buah jeruk dibagikan kepada $5$ orang anak. Tiap anak boleh mendapat lebih dari $1$ buah apel atau jeruk, atau tidak sama sekali. Banyak cara pembagian yang dapat dilakukan adalah $\cdots \cdot$
A. $C(24, 19)$
B. $C(19, 14)$
C. $C(24, 19) + C(19, 14)$
D. $C(24, 19) \times C(19, 14)$
E. $C(20, 5) \times C(15, 5)$

Pembahasan

Pada persoalan ini, nilai $n = 5,$ $r_1 = 20$ (apel), dan $r_2 = 15$ (jeruk). Perhatikan bahwa setiap anak boleh tidak mendapatkan apel/jeruk sama sekali sehingga syarat nonnegatif telah terpenuhi.
Dengan menggunakan Teorema Bintang dan Garis, banyak cara membagikan $20$ buah apel (identik) kepada $5$ orang anak adalah sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n+r_1-1}{r_1-1} & = \binom{5+20-1}{20-1} \\ & = \binom{24}{19} \\ & = C(24, 19) \end{aligned}$$Dengan cara yang sama, banyak cara membagikan $15$ buah jeruk (identik) kepada $5$ orang anak adalah sebagai berikut.
$$\begin{aligned} \displaystyle \binom{n+r_2-1}{r_2-1} & = \binom{5+15-1}{15-1} \\ & = \binom{19}{14} \\ & = C(19, 14) \end{aligned}$$Jadi, banyak cara pembagian yang dapat dilakukan secara keseluruhan dapat dicari dengan menggunakan aturan perkalian (karena kejadiannya saling bergantung/dependen), yakni $\boxed{C(24, 19) \times C(19, 14)}$ cara.
(Jawaban D)

[collapse]

Baca Juga: Soal dan Pembahasan – Kombinatorika (Tingkat Lanjut) 

Soal Nomor 9
Banyaknya pasangan tripel terurut dari bilangan bulat $(a, b, c)$ dengan $a \ge -2, b \ge -2,$ dan $c \ge 0$ sedemikian sehingga $a+b+c=12$ adalah $\cdots \cdot$
A. $121$                    D. $149$
B. $133$                    E. $153$
C. $147$

Pembahasan

Perhatikan bahwa ketiga variabel tersebut memiliki nilai terkecil yang bukan $0$ sehingga Teorema Bintang dan Garis belum dapat diterapkan. Kita harus membuat persamaan yang variabelnya bernilai paling kecil $0.$
Sekarang misalkan $a’ = a+2,$ $b’ = b+2,$ dan $c’ = c$ sedemikian sehingga kita ingin mencari pasangan terurut $(a’, b’, c’)$ dengan syarat $a’ \ge 0, b’ \ge 0, c’ \ge 0.$ Kita peroleh persamaan yang baru sebagai berikut.
$$\begin{aligned} (a’-2) + (b’-2) + c’ & = 12 \\ a’ + b’ + c’ & = 16 \end{aligned}$$Syarat nonnegatif telah terpenuhi oleh tiga variabel tersebut sehingga kita bisa menerapkan Teorema Bintang dan Garis untuk $n = 16$ dan $k = 3.$
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{16+3-1}{3-1} \\ & = \binom{18}{2} \\ & = \dfrac{18!}{16! \cdot 2!} \\ & = 153 \end{aligned}$$Jadi, banyak pasangan tripel terurut yang dimaksud adalah $\boxed{153}$
(Jawaban E)

[collapse]

Soal Nomor 10
Banyaknya solusi dari $x + 2y + z = 8$ dengan $x, y, z$ merupakan bilangan bulat nonnegatif adalah bilangan dua digit $\overline{ab}.$ Nlai dari $a + b = \cdots \cdot$
A. $3$                 C. $6$                 E. $8$
B. $5$                 D. $7$

Pembahasan

Tinjau persamaan $x + y + z = 8.$
Dengan menerapkan Teorema Bintang dan Garis untuk $n = 8$ dan $k = 3,$ banyak solusi bulat nonnegatif dari persamaan itu adalah $C(8+3-1, 3-1) = C(10, 2).$
Sekarang tinjau persamaan $x + 2y + z = 8.$ Misalkan $Y = 2y$ sehingga terdapat $5$ bilangan bulat nonnegatif yang mungkin sebagai nilai $Y,$ yaitu $0, 2, 4, 6, 8$ dari total $9$ bilangan $(0, 1, 2, \cdots, 8).$ Jadi, banyak solusinya dinyatakan sebagai berikut.
$$\begin{aligned} \dfrac{5}{9} \cdot C(10, 2) & = \dfrac{5}{9} \cdot \dfrac{10!}{8! \cdot 2!} \\ & = \dfrac{5}{9} \cdot \dfrac{10 \cdot 9}{2} \\ & = 25 \end{aligned}$$Jadi, banyaknya solusi dari persamaan tersebut adalah $25.$ Berarti nilai $a = 2$ dan $b = 5$ sehingga $\boxed{a + b = 2 + 5 = 7}$
(Jawaban D)

[collapse]

Baca Juga: Materi, Soal, dan Pembahasan – Prinsip Inklusi-Eksklusi

Soal Nomor 11
Banyaknya solusi dari $3x + y + z = 24$ dengan $x, y, z$ merupakan bilangan bulat nonnegatif adalah $\cdots \cdot$
A. $91$                   D. $117$
B. $93$                   E. $121$
C. $111$

Pembahasan

Tinjau persamaan $x + y + z = 24.$
Dengan menerapkan Teorema Bintang dan Garis untuk $n = 24$ dan $k = 3,$ banyak solusi bulat nonnegatif dari persamaan itu adalah $C(24+3-1, 3-1) = C(26, 2).$

Sekarang tinjau persamaan $3x + y + z = 24.$
Misalkan $X = 3x$ sehingga terdapat $9$ bilangan bulat nonnegatif yang mungkin sebagai nilai $X,$ yaitu $0, 3, 6, \cdots, 24$ dari total $25$ bilangan $(0, 1, 2, \cdots, 24).$ Jadi, banyak solusinya dinyatakan sebagai berikut.

$$\begin{aligned} \dfrac{9}{25} \cdot C(26, 2) & = \dfrac{9}{25} \cdot \dfrac{26!}{24! \cdot 2!} \\ & = \dfrac{9}{25} \cdot \dfrac{26 \cdot 25}{2} \\ & = 117 \end{aligned}$$Jadi, banyaknya solusi dari persamaan tersebut adalah $\boxed{117}$
(Jawaban D)

[collapse]

Baca Juga: Soal dan Pembahasan – Peluang (Tingkat SMP/Sederajat) 

Soal Nomor 12
Berapa banyak solusi bilangan bulat nonnegatif dari pertidaksamaan $x_1+x_2+x_3 \le 10$?
A. $66$                       D. $254$
B. $78$                       E. $286$
C. $152$

Pembahasan

Misalkan terdapat bilangan $x_4 \ge 0$ sedemikian sehingga berlaku persamaan
$$x_1 + x_2 + x_3 + \color{red}{x_4} = 10.$$Oleh karena itu, banyak solusi bulat nonnegatif dari persamaan $x_1+x_2+x_3 \le 10$ sama dengan banyak solusi bulat nonnegatif dari persamaan $x_1+x_2+x_3+x_4 = 10.$
Dengan menggunakan Teorema Bintang dan Garis untuk $n = 10$ dan $k = 4,$ diperoleh
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{10+4-1}{4-1} \\ & = \binom{13}{3} \\ & = \dfrac{13!}{10! \cdot 3!} \\ & = 286. \end{aligned}$$Jadi, banyak solusi pertidaksamaan tersebut adalah $\boxed{286}$
(Jawaban E)

[collapse]

Soal Nomor 13
Berapa banyak pasangan terurut bilangan bulat positif $(a_1, a_2, a_3, a_4, a_5, a_6)$ dengan $a_i \geq i$ untuk $i = 1, 2, 3, 4, 5, 6$ yang memenuhi persamaan $$a_1 + a_2 + a_3 + a_4 + a_5 + a_6 \le 100?$$
A. $C(105, 6)$                  D. $C(79, 6)$
B. $C(100, 6)$                  E. $C(79, 5)$
C. $C(85, 6)$

Pembahasan

Perhatikan bahwa kita punya beberapa kondisi berikut.
$$\begin{cases} a_1 & \ge 1 \\ a_2 & \ge 2 \\ a_3 & \ge 3 \\ a_4 & \ge 4 \\ a_5 & \ge 5 \\ a_6 & \ge 6 \end{cases}$$Misalkan terdapat bilangan $c \geq 0$ sedemikian sehingga berlaku persamaan
$$a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + c = 100.$$Sekarang misalkan $b_i = a_i-i$ untuk $i = 1, 2, \cdots, 6$ sedemikian sehingga kita ingin mencari pasangan terurut $(b_1, b_2, b_3, b_4, b_5, b_6, c)$ dengan syarat $b_i \ge 0, c \ge 0.$ Kita peroleh persamaan yang baru sebagai berikut.
$$\begin{aligned} (b_1 + 1) + (b_2 + 2) + (b_3 + 3) + (b_4 + 4) + (b_5 + 5) + (b_6 + 6) + c & = 100 \\ b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c & = 100-(1+2+3+4+5+6) \\ b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c & = 79 \end{aligned}$$Syarat nonnegatif telah terpenuhi oleh tujuh variabel tersebut sehingga kita bisa menerapkan Teorema Bintang dan Garis untuk $n = 79$ dan $k = 7.$
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{79+7-1}{7-1} \\ & = \binom{85}{6} \\ & = C(85, 6) \end{aligned}$$Jadi, banyak pasangan terurut yang dimaksud adalah $\boxed{C(85, 6)}$
(Jawaban C)

[collapse]

Bagian Uraian

Soal Nomor 1
Toko roti “Enaks” menjual $8$ jenis roti. Berapa banyak cara mengambil $1$ lusin roti (1 lusin = 12 buah)? Nyatakan jawaban Anda dalam notasi kombinasi.

Pembahasan

Analogikan $8$ jenis roti tersebut sebagai $8$ kotak berbeda. Kita akan mendistribusikan $12$ roti ke dalam $8$ kotak. Masing-masing kotak boleh berisi lebih dari satu jenis roti, atau mungkin tidak sama sekali. Dengan menggunakan Teorema Bintang dan Garis untuk $n = 12$ dan $k = 8,$ kita peroleh
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{12+8-1}{8-1} \\ & = \binom{19}{7} \\ & = C(19,7). \end{aligned}$$Jadi, banyak cara mengambil selusin roti adalah $\boxed{C(19,7)}$ atau sama dengan $\boxed{C(19,12)}$

[collapse]

Soal Nomor 2
Dari sejumlah besar CD (compact disc) di dalam kotak yang berisi program-program aplikasi A, B, C, D, dan E, berapa banyak cara 10 CD dapat diambil?

Pembahasan

Masalah di atas ekuivalen dengan mencari banyaknya solusi bulat nonnegatif yang memenuhi persamaan
$$x_1 + x_2 + x_3 + x_4 + x_5 = 10$$dengan $x_1, x_2, x_3, x_4, x_5$ berturut-turut menyatakan banyaknya CD yang memuat aplikasi A, B, C, D, dan E.
Dengan menggunakan Teorema Bintang dan Garis untuk $n = 10$ dan $k = 5,$ diperoleh
$$\begin{aligned} \displaystyle \binom{n+k-1}{k-1} & = \binom{10+5-1}{5-1} \\ & = \binom{14}{4} \\ & = \dfrac{14!}{10! \cdot 4!} \\ & = 1.001. \end{aligned}$$Jadi, banyak cara pengambilan $10$ CD adalah $\boxed{1.001}$

[collapse]

Soal Nomor 3
Andaikan terdapat kumpulan bola yang berwarna merah, biru, dan hijau, yang masing-masingnya identik satu sama lain. Jumlah bola dari masing-masing warna paling sedikit berjumlah $8$ buah.

  1. Berapa banyak cara memilih $8$ buah bola (tanpa ada batasan warna)?
  2. Berapa banyak cara memilih $8$ buah bola jika paling sedikit $1$ bola dari masing-masing warna terwakili?

Pembahasan

Jawaban a)
Dengan menggunakan Teorema Bintang dan Garis untuk $n = 8$ dan $k = 3,$ diperoleh
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{8+3-1}{3-1} \\ & = \binom{10}{2} \\ & = \dfrac{10!}{8! \cdot 2!} \\ & = 45. \end{aligned}$$Jadi, banyak cara memilih $8$ buah bola (tanpa ada batasan warna) adalah $\boxed{45}$
Jawaban b)
Ambil terlebih dahulu $1$ bola untuk masing-masing warna sehingga sekarang kita hanya perlu mengambil $5$ bola dari $3$ pilihan warna yang ada.
Dengan menggunakan Teorema Bintang dan Garis untuk $n = 5$ dan $k = 3,$ diperoleh
$$\begin{aligned} \displaystyle \binom{n + k-1}{k-1} & = \binom{5+3-1}{3-1} \\ & = \binom{7}{2} \\ & = \dfrac{7!}{5! \cdot 2!} \\ & = 21. \end{aligned}$$Jadi, banyak cara memilih $8$ buah bola jika paling sedikit $1$ bola dari masing-masing warna terwakili adalah $\boxed{21}$

[collapse]