Materi, Soal, dan Pembahasan – Teorema Bintang dan Garis

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)}$

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}$

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}$

Misalkan $\overline{k_1k_2k_3}$ merupakan bilangan tiga angka dengan $k_1 \neq 0.$ Kita akan mencari banyak bilangan berbentuk $\overline{k_1k_2k_3}$ sehingga $k_1 + k_2 + k_3 = 5m$ untuk suatu bilangan asli $m.$
Kasus 1: $k_1 + k_2 + k_3 = 5(1) = 5.$
Karena $k_1 \neq 0,$ kita memiliki syarat $k_1 \ge 1, k_2 \ge 0,$ dan $k_3 \ge 0.$ Masalah ini analog dengan menempatkan $5$ bola ke dalam $3$ kotak berbeda $k_1, k_2,$ dan $k_3.$ Pertama, masukkan $1$ bola ke dalam kotak $k_1.$ Selanjutnya, kita tinggal mencari cara untuk memasukkan $4$ bola sisanya ke dalam $3$ kotak ini secara bebas.
Dengan menggunakan teorema bintang dan garis, banyak cara melakukannya adalah $\displaystyle \binom{4+3-1}{3-1} = \binom{6}{2} = 15.$
Ini berarti ada $15$ bilangan tiga angka yang jumlah digit-digitnya merupakan kelipatan $5.$
Kasus 2: $k_1 + k_2 + k_3 = 5(1) = 10.$
Karena $k_1 \neq 0,$ kita memiliki syarat $k_1 \ge 1, k_2 \ge 0,$ dan $k_3 \ge 0.$ Dengan cara yang serupa, banyak bilangan tiga angka yang jumlah digit-digitnya merupakan kelipatan $10$ adalah $\displaystyle \binom{9+3-1}{3-1} = \binom{11}{2} = 55.$
Kasus 3: $k_1 + k_2 + k_3 = 5(1) = 15.$
Karena $k_1 \neq 0,$ kita memiliki syarat $k_1 \ge 1, k_2 \ge 0,$ dan $k_3 \ge 0.$ Dengan cara yang serupa, banyak bilangan tiga angka yang jumlah digit-digitnya merupakan kelipatan $15$ adalah $\displaystyle \binom{14+3-1}{3-1} = \binom{16}{2} = 120.$
Kasus 4: $k_1 + k_2 + k_3 = 5(1) = 20.$
Karena $k_1 \neq 0,$ kita memiliki syarat $k_1 \ge 1, k_2 \ge 0,$ dan $k_3 \ge 0.$ Dengan cara yang serupa, banyak bilangan tiga angka yang jumlah digit-digitnya merupakan kelipatan $20$ adalah $\displaystyle \binom{19+3-1}{3-1} = \binom{21}{2} = 210.$
Kasus 5: $k_1 + k_2 + k_3 = 5(1) = 25.$
Karena $k_1 \neq 0,$ kita memiliki syarat $k_1 \ge 1, k_2 \ge 0,$ dan $k_3 \ge 0.$ Dengan cara yang serupa, banyak bilangan tiga angka yang jumlah digit-digitnya merupakan kelipatan $25$ adalah $\displaystyle \binom{24+3-1}{3-1} = \binom{26}{2} = 325.$
Jumlah digit maksimum adalah $3 \times 9 = 27.$ Jadi, kasus kita selesai. Dengan demikian, banyak bilangan tiga angka yang jumlah digit-digitnya merupakan kelipatan 5 adalah $\boxed{10 + 55 + 120 + 210 + 325 = 720}$