Command Palette

Search for a command to run...

Kelas 11Kelas 12mathKombinatorika

x1, x2, x3 ..., x9 merupakan angka yang diambil dari {0, 1,

Pertanyaan

Berapa banyak pasangan (x1, x2, x3, ..., x9) yang memenuhi persamaan x1 + x2 + x3 + ... + x9 = 15, di mana setiap xi diambil dari {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}?

Solusi

Verified

478.731

Pembahasan

Untuk menyelesaikan soal ini, kita menggunakan konsep kombinasi dengan pengulangan (stars and bars). Kita memiliki 9 variabel (x1 hingga x9) yang masing-masing dapat mengambil nilai dari 0 hingga 9, dan jumlah totalnya harus 15. Rumus kombinasi dengan pengulangan adalah C(n+k-1, k-1), di mana n adalah jumlah total dan k adalah jumlah variabel. Namun, ada batasan bahwa setiap variabel tidak boleh lebih dari 9. Pendekatan langsung dengan stars and bars akan menghasilkan jumlah solusi tanpa batasan. Kita perlu menggunakan Prinsip Inklusi-Eksklusi untuk memperhitungkan batasan tersebut. Langkah 1: Hitung total solusi tanpa batasan. Jumlah variabel (k) = 9 Jumlah total (n) = 15 Total solusi = C(15 + 9 - 1, 9 - 1) = C(23, 8) C(23, 8) = 23! / (8! * (23-8)!) = 23! / (8! * 15!) = (23 * 22 * 21 * 20 * 19 * 18 * 17 * 16) / (8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) = 490314 Langkah 2: Hitung solusi di mana setidaknya satu variabel lebih dari atau sama dengan 10. Misalkan x1 >= 10. Ganti x1 dengan y1 + 10, di mana y1 >= 0. (y1 + 10) + x2 + ... + x9 = 15 y1 + x2 + ... + x9 = 5 Jumlah solusi = C(5 + 9 - 1, 9 - 1) = C(13, 8) C(13, 8) = 13! / (8! * 5!) = (13 * 12 * 11 * 10 * 9) / (5 * 4 * 3 * 2 * 1) = 1287 Karena ada 9 variabel, kita kalikan dengan 9 (karena setiap variabel bisa saja >= 10). Jumlah solusi dengan setidaknya satu variabel >= 10 = 9 * 1287 = 11583. Langkah 3: Hitung solusi di mana setidaknya dua variabel lebih dari atau sama dengan 10. Misalkan x1 >= 10 dan x2 >= 10. Ganti x1 dengan y1 + 10 dan x2 dengan y2 + 10. (y1 + 10) + (y2 + 10) + x3 + ... + x9 = 15 y1 + y2 + x3 + ... + x9 = -5 Jumlah solusi = 0 (karena tidak mungkin jumlahnya negatif). Ini berarti kita tidak perlu mempertimbangkan kasus di mana dua atau lebih variabel lebih dari atau sama dengan 10, karena jumlah totalnya hanya 15. Langkah 4: Terapkan Prinsip Inklusi-Eksklusi. Jumlah solusi yang memenuhi batasan = Total solusi - (Solusi dengan setidaknya satu variabel >= 10) Jumlah solusi = 490314 - 11583 = 478731. Jadi, banyak pasangan (x1, x2, x3, ..., x9) yang memenuhi persamaan x1 + x2 + x3 + ... + x9 = 15 adalah 478.731.
Topik: Prinsip Inklusi Eksklusi, Kombinasi Dengan Pengulangan
Section: Aplikasi Kombinasi

Apakah jawaban ini membantu?

On This Page

Loading Related Questions...