Terdapat empat kotak yang dinomori 1 sampai 4. Setiap kotak

Banyak cara pengisian koin yang mungkin adalah 70.

Pembahasan

Ini adalah soal kombinatorik yang melibatkan pendistribusian objek (koin) ke dalam wadah (kotak) dengan batasan tertentu. Masalah ini dapat diselesaikan dengan menggunakan konsep 'stars and bars' yang dimodifikasi untuk mengakomodasi batasan.

Misalkan $x_1, x_2, x_3, x_4$ adalah jumlah koin dalam kotak 1, 2, 3, dan 4.

Kondisi yang diberikan adalah:
1. Setiap kotak dapat diisi maksimum 5 koin: $0 \le x_i \le 5$ untuk $i = 1, 2, 3, 4$.
2. Kotak yang bernomor lebih besar tidak boleh berisi koin lebih banyak dari kotak yang bernomor lebih kecil: $x_1 \ge x_2 \ge x_3 \ge x_4$.
3. Tidak boleh ada kotak yang kosong: $x_i \ge 1$ untuk $i = 1, 2, 3, 4$.

Mengkombinasikan kondisi 1 dan 3, kita mendapatkan batasan: $1 \le x_i \le 5$.

Mengkombinasikan dengan kondisi 2, kita memiliki urutan non-meningkat: $5 \ge x_1 \ge x_2 \ge x_3 \ge x_4 \ge 1$.

Untuk mencari banyak cara pengisian koin yang mungkin, kita perlu menghitung berapa banyak kombinasi $(x_1, x_2, x_3, x_4)$ yang memenuhi kondisi $5 \ge x_1 \ge x_2 \ge x_3 \ge x_4 \ge 1$.

Ini setara dengan memilih 4 angka dari himpunan {1, 2, 3, 4, 5} dengan pengulangan, di mana urutan tidak penting (karena kita akan mengurutkannya dari terbesar ke terkecil).

Cara lain untuk memvisualisasikan ini adalah dengan menggunakan transformasi. Misalkan:
$y_1 = x_1 - x_2 \ge 0$
$y_2 = x_2 - x_3 \ge 0$
$y_3 = x_3 - x_4 \ge 0$
$y_4 = x_4 - 1 \ge 0$ (karena $x_4 \ge 1$)

Dari $x_1 \ge x_2 \ge x_3 \ge x_4 \ge 1$, kita punya:
$x_4 = y_4 + 1$
$x_3 = y_3 + x_4 = y_3 + y_4 + 1$
$x_2 = y_2 + x_3 = y_2 + y_3 + y_4 + 1$
$x_1 = y_1 + x_2 = y_1 + y_2 + y_3 + y_4 + 1$

Sekarang kita gunakan batasan $x_1 \le 5$:
$y_1 + y_2 + y_3 + y_4 + 1 \le 5$
$y_1 + y_2 + y_3 + y_4 \le 4$

Kita perlu mencari jumlah solusi non-negatif untuk persamaan $y_1 + y_2 + y_3 + y_4 = k$ di mana $k$ bisa 0, 1, 2, 3, atau 4. Ini adalah masalah 'stars and bars'.
Jumlah solusi untuk $y_1 + y_2 + y_3 + y_4 = k$ adalah $\binom{k+n-1}{n-1}$, di mana $n=4$ (jumlah variabel).

- Untuk k=0: $\binom{0+4-1}{4-1} = \binom{3}{3} = 1$ (solusi: 0,0,0,0)
- Untuk k=1: $\binom{1+4-1}{4-1} = \binom{4}{3} = 4$
- Untuk k=2: $\binom{2+4-1}{4-1} = \binom{5}{3} = 10$
- Untuk k=3: $\binom{3+4-1}{4-1} = \binom{6}{3} = 20$
- Untuk k=4: $\binom{4+4-1}{4-1} = \binom{7}{3} = 35$

Total cara = 1 + 4 + 10 + 20 + 35 = 70.

Alternatif: Ini adalah masalah menghitung partisi dari bilangan 4 ke dalam paling banyak 4 bagian, di mana setiap bagian tidak lebih dari 5. Atau, menghitung partisi dari bilangan $N$ ke dalam $k$ bagian, di mana setiap bagian dibatasi.

Lebih tepatnya, ini adalah masalah menghitung kombinasi dengan pengulangan. Kita memilih 4 angka dari himpunan {1, 2, 3, 4, 5} dengan pengulangan, dan urutannya tidak masalah karena kita bisa mengaturnya dari besar ke kecil. Rumusnya adalah $\binom{n+k-1}{k}$, di mana $n$ adalah jumlah item yang bisa dipilih (5 angka: 1, 2, 3, 4, 5) dan $k$ adalah jumlah item yang dipilih (4 kotak).

$n = 5$ (angka yang bisa dipilih: 1, 2, 3, 4, 5)
$k = 4$ (jumlah kotak yang akan diisi)

Banyak cara = $\binom{5+4-1}{4} = \binom{8}{4} = \frac{8!}{4!(8-4)!} = \frac{8!}{4!4!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = \frac{1680}{24} = 70$.

Jadi, banyak cara pengisian koin yang mungkin ke dalam keempat kotak tersebut adalah 70.