Berikut ini adalah beberapa soal mengenai kombinatorika beserta penyelesaiannya yang diambil dari soal-soal tingkat olimpiade seperti ON MIPA-PT dan OSN-Pertamina. Selamat belajar! Show
Baca Juga: Soal dan Pembahasan – Peluang (Tingkat SMP/Sederajat) Quote by Bill GatesDon’t compare yourself with anyone in this world.If you do so, you are insulting yourself. Soal Nomor 1Enam dadu (dengan $6$ sisi) dilempar satu kali. Probabilitas munculnya jumlah mata dadu $9$ adalah $\cdots \cdot$
Ada $P(S) = 6^6$ susunan untuk kasus ini. $1~1~1~1~1~4$ sebanyak $\dfrac{6!}{5!} = 6$ susunan. $1~1~1~1~2~3$ sebanyak $\dfrac{6!}{4!} = 30$ susunan. $1~1~1~2~2~2$ sebanyak $\dfrac{6!}{3! \cdot 3!} = 20$ susunan. Semua susunan yang mungkin adalah $6 + 30 + 20 = 56$ susunan sehingga probabilitas munculnya jumlah mata dadu $9$ adalah $\boxed{P(9) = \dfrac{56}{6^6}}$ Baca Juga: Soal dan Pembahasan – Faktorial Soal Nomor 2Banyak cara mengisi persegi panjang berukuran $2 \times 16$ dengan persegi panjang berukuran $2 \times 2, 2 \times 3$, dan $2 \times 4$ adalah $\cdots \cdot$
Karena setiap persegi panjang yang diberikan memiliki ukuran panjang yang sama, yaitu $2$, maka kita hanya perlu meninjau ukuran lebarnya. Untuk mengisi persegi panjang berukuran $2 \times 16$ tersebut, kita perlu menentukan nilai $a, b, c \in \mathbb{N}$ sedemikian sehingga persamaan berikut berlaku. Soal Nomor 3Pada babak final sebuah turnamen, tim pemenang adalah tim yang pertama sekali memenangkan $2$ pertandingan secara berurutan atau tim yang pertama sekali memenangkan $4$ pertandingan. Banyak cara turnamen dapat terjadi adalah $\cdots \cdot$
Misalkan pada turnamen tersebut, dua tim yang bertanding adalah Tim A dan Tim B. Tabel berikut menyatakan kemungkinan yang dapat terjadi agar tim A menang ($M$ = menang, $K$ = kalah). Soal Nomor 4Pada sebuah lemari terdapat $25$ helai baju yang terdiri atas $4$ ukuran, yaitu $5$ helai baju berukuran S, $4$ helai baju berukuran M, $9$ helai baju berukuran L, dan $7$ helai baju berukuran XL. Tentukan jumlah baju paling sedikit yang dapat diambil agar selalu diperoleh $7$ helai baju berukuran sama.
Gunakan Prinsip Sarang Burung Merpati untuk menyelesaikan kasus ini. Baca Juga: Materi, Soal, dan Pembahasan – Teorema Bintang dan Garis Soal Nomor 5Pada sebuah pesta pernikahan terdapat $6$ orang (termasuk pengantin) yang hendak berfoto. Banyak cara menata pose foto dalam satu baris dari keenam orang tersebut sedemikian sehingga pengantin berdiri tidak saling berdekatan/bersampingan adalah $\cdots \cdot$
Banyak cara menata pose foto $6$ orang berdiri dalam satu baris adalah Soal Nomor 6Sebuah password terdiri atas $7$ huruf kapital. Password dikatakan legal bila memenuhi dua kondisi: (i) tidak terdapat huruf yang sama, (ii) huruf X dan Y tidak saling berdekatan. Besar peluang membentuk password yang legal adalah $\cdots \cdot$
Semua kemungkinan ketika huruf X dan Y saling berdekatan dinyatakan dalam bagan berikut. $$\begin{array}{|c|c|c|c|c|c|c|} \hline X & Y & & & & & \\ \hline & X & Y & & & & \\ \hline & & X & Y & & & \\ \hline & & & X & Y & & \\ \hline & & & & X & Y & \\ \hline & & & & & X & Y \\ \hline \end{array}$$Ada $6$ posisi, dan $XY \neq YX$, berarti total semuanya ada $12$ posisi untuk memenuhi syarat kedua. Masing-masing kotak putih pada setiap baris memiliki pemilihan huruf yang sama dan tak boleh berulang, yaitu $24 \times 23 \times 22 \times 21 \times 20$ (dimulai dari $24$, karena ada $26$ huruf dan huruf XY telah terpakai). Jadi, banyak cara membentuk password tanpa pengulangan huruf dan huruf X dan Y berdekatan adalah $12 \times 24 \times 23 \times 22 \times 21 \times 20.$
Dengan kata lain, banyak cara membentuk password tanpa pengulangan huruf dan huruf X dan Y tidak berdekatan adalah Soal Nomor 7Berapa banyak cara membentuk sebuah panitia yang beranggotakan $5$ orang yang dipilih dari $7$ orang pria dan $5$ orang wanita, jika di dalam panitia tersebut paling sedikit beranggotakan $2$ orang wanita?
Jumlah wanita di dalam panitia: $2, 3, 4,$ atau $5$ orang. Soal Nomor 8Enam komite akan dibentuk dari $14$ orang. Bila $2$ komite dari $6$ komite ini terdiri atas $3$ orang dan sisanya terdiri atas masing-masing $2$ orang, maka banyaknya komite yang dapat dibentuk adalah $\cdots \cdot$
Kasus di atas dapat dianalogikan sebagai kasus penyusunan huruf-huruf (dalam hal ini, orang). Dalam satu komite, apabila orang yang dipilih sama, tetapi tidak sesuai urutan, tetap akan dianggap sama (analoginya seperti menyusun kata yang memuat sejumlah huruf yang sama). Dengan demikian, ini merupakan kasus permutasi berulang dari $14$ objek. Banyak cara penyusunannya adalah Soal Nomor 9Diberikan persamaan $x_1 + x_2 + x_3 + x_4 = 12$, dengan $x_i$ adalah bilangan cacah. Berapa jumlah kemungkinan solusinya?
Ini merupakan kasus kombinasi dengan pengulangan dengan $n = 4$ (dianalogikan sebanyak $4$ kotak) dan $r = 12$ (dianalogikan sebanyak 12 bola). Setiap kotak bisa diisi $0, 1, 2, \cdots, 12$ bola, dengan syarat jumlah bola pada seluruh kotak yang ada adalah $12$ bola. Contoh penyelesaiannya adalah Soal Nomor 10Berapa banyak solusi bilangan bulat dari $x_1 +x_2 +x_3 = 10$ jika diberi syarat $0 \leq x_1 \leq 2, x_2 > 1$, dan $x_3 \geq 0$?
Analogikan dengan membagi $10$ buah bola yang identik ke dalam $3$ buah kotak, sebut saja kotak $x_1, x_2$, dan $x_3$. Jadi, $x_1$ ada kemungkinan berisi $0$ (tak berisi), $1$, atau $2$. Untuk masing-masing nilai $x_1$, kita perinci perhitungannya sebagai berikut.
Jumlah solusi seluruhnya adalah $$\boxed{C(9,8) +C(8,7) +C(7,6) = 9 + 8 + 7 = 24}$$ Soal Nomor 11Dari $100.000$ buah bilangan bulat positif pertama, berapa banyak bilangan yang mengandung tepat $1$ buah angka $3$, $1$ buah angka $4$, dan $1$ buah angka $5$?
Bilangan $100.000$ jelas tidak memenuhi untuk kasus ini sehingga kita hanya perlu meninjau bilangan dengan $5$ digit (untuk kasus bilangan ratusan, anggap posisi puluh ribuan dan ribuannya $0$, begitu juga untuk kasus bilangan ribuan). Berarti, ada $5$ cara mengisi angka $5, 4$ cara mengisi angka $4$, dan $3$ angka mengisi angka $3.$ Dua tempat kosong lainnya bisa diisi angka lain yaitu $0, 1, 2, 6, 7, 8$, dan $9$ (ada $7$ angka dan boleh berulang). Jadi, banyak bilangan yang demikian adalah $\boxed{5 \times 4 \times 3 \times 7 \times 7 = 2940~\text{cara}}$ Soal Nomor 12Dari sejumlah besar koin 25-an, 50-an, 100-an, dan 500-an, berapa banyak cara lima koin dapat diambil?
Kasus ini adalah kasus kombinasi dengan pengulangan (karena koin tertentu dapat diambil lebih dari sekali). Di sini $n = 4$ dan $r = 5$, berarti banyak cara yang dimaksud adalah $C(4 + 5-1, 5) = C(8,5)$ cara. Soal Nomor 13Tentukan banyaknya cara agar $4$ buku matematika, $3$ buku sejarah, $3$ buku kimia, dan $2$ buku sosiologi (jenis bukunya berbeda) dapat disusun dalam satu baris sedemikian sehingga (untuk masing-masing soal):
(Jawaban a) Pandang setiap topik buku sebagai satu kesatuan (karena harus bersebelahan). Karena ada $4$ topik, jadi kita peroleh $4!$ untuk mengatur susunannya. Di lain sisi, setiap topik memiliki jenis buku yang berbeda pula. Untuk topik matematika, ada $4!$ cara mengatur susunannya, $3!$ cara mengatur susunan buku sejarah, $3!$ cara mengatur susunan buku kimia, dan $2!$ mengatur susunan buku sosiologi. Jadi, totalnya ada Soal Nomor 14Misalkan $|A| = m$ dan $|B|=n$. Berapa banyak fungsi yang dapat dibuat dari himpunan $A$ ke himpunan $B$?
Ingatlah kembali definisi fungsi bahwa setiap elemen pada himpunan $A$ (domain) harus mempunyai pasangan tepat satu di himpunan $B$ (kodomain). Elemen pertama di $A$ mempunyai $n$ kemungkinan peta di $B,$ begitu juga elemen kedua, elemen ketiga, sampai elemen ke-$m$ sehingga jumlah fungsi yang dapat dibuat dari $A$ ke $B$ (terapkan aturan perkalian) adalah $\underbrace{n \times n \times\cdots \times n} _{\text{sebanyak}~m} = n^m$ buah. Soal Nomor 15Berapa banyak string yang dibentuk dari permutasi huruf-huruf pada kata “SARUNG” sedemikian sehingga huruf-huruf vokal terletak pada posisi yang bersebelahan?
Huruf vokal pada kata $SARUNG$ adalah $A$ dan $U$. Hal yang ditanyakan dalam soal ini adalaah string yang mengandung $UA$ atau $AU$. Karena $UA$ atau $AU$ harus muncul pada satu blok, maka kita harus menghitung jumlah permutasi blok $AU$ atau $UA$ dengan huruf-huruf $S, R, N$, dan $G$. Untuk $AU,S, R, N$, dan $G$, jumlah kata yang dapat dibentuk adalah $P(5,5)=5!$, begitu juga untuk $UA, S, R, N$, dan $G$. Soal Nomor 16Kartu remi seluruhnya ada $52$ buah kartu dalam satu pak. Keseluruhan kartu ini terdiri dari $13$ jenis kartu, setiap jenis terdiri atas $4$ buah kartu. Tiga belas kartu tersebut adalah: $2, 3, \cdots, 10$, joker, ratu, raja, dan as. Setiap pemain remi mendapatkan $5$ buah kartu sebagai bentuk dimulainya permainan. Berapa peluang dari $5$ kartu tersebut mengandung $4$ kartu dari jenis yang sama?
Jumlah cara mengambil $5$ kartu sembarang dari $52$ kartu yang ada adalah $C(52,5)$ (jumlah titik contoh). Soal Nomor 17Berapa peluang dari $5$ kartu remi mengandung $4$ kartu as?
Pada soal ini, jenis kartu sudah ditentukan, yaitu kartu as, jadi hanya ada satu cara (pilihan) untuk mengambilnya. Soal Nomor 18Di perpustakaan FKIP Untan terdapat $3$ jenis buku berbeda: buku Matematika Diskrit, buku Struktur Aljabar, dan buku Analisis Real. Perpustakaan menyediakan sedikitnya $10$ buah buku untuk masing-masing jenisnya. Berapa banyak cara memilih $10$ buah buku?
Soal ini termasuk kasus kombinasi dengan pengulangan ketika $n = 3$ dan $r = 10$. Jumlah cara memilih buku adalah Soal Nomor 19Sebuah rangkaian digit biner adalah sebuah barisan yang terdiri dari angka $0$ dan $1$. Banyaknya rangkaian digit biner yang terdiri atas tepat delapan angka $0$ dan tepat sepuluh angka $1$ sedemikian sehingga setiap kemunculan angka $0$ segera diikuti oleh digit $1$ adalah $\cdots \cdot$
Langkah pertama adalah memasangkan setiap angka $0$ dengan angka $1$. Berdasarkan informasi pada soal, kita akan memperoleh tepat $8$ pasangan yang mungkin (angka $01$ sebanyak $8$ kali kemunculan) dan sisanya adalah angka $1$ sebanyak $2$ buah. Perhatikan ilustrasi tabel berikut. Baca Juga: Materi, Soal, dan Pembahasan – Prinsip Inklusi-Eksklusi Soal Nomor 20Sebuah keluarga besar beranggotakan $14$ orang anak yang terdiri dari dua kelahiran kembar tiga identik, tiga kelahiran kembar dua identik, dan dua anak yang lain. Bila kembar identik tak dapat dibedakan, maka banyak pose foto berdiri dalam satu baris pada $14$ anak tersebut adalah $\cdots \cdot$
Kasus ini ekuivalen dengan kasus penyusunan string/kata yang mengandung sejumlah huruf yang sama. Gunakan permutasi berulang untuk kasus ini, yaitu $\dfrac{14!}{(3!)^2\times (2!)^3}.$ Soal Nomor 21Banyak cara menugaskan $5$ pekerjaan berbeda ke $4$ orang pegawai berbeda sedemikian sehingga setiap pegawai ditugaskan ke paling sedikit satu pekerjaan adalah $\cdots \cdot$
Berdasarkan syarat yang diberikan, akan ada $1$ pegawai yang mendapat $2$ pekerjaan, sedangkan $3$ pegawai lainnya mendapatkan $1$ pekerjaan. Kondisinya diberikan oleh tabel di bawah dengan angka-angkanya mewakili banyak pekerjaan yang diambil. Baca Juga: Masalah Kombinatorika: Mencari Banyak Rute Soal Nomor 22Untuk setiap bilangan asli $n \in \mathbb{N}$ dengan $n \geq 2$, nilai dari
Misalkan Soal Nomor 23Seorang petinju mempunyai waktu $75$ minggu untuk mempertahankan gelar. Untuk itu pelatih menjadwalkan program latih tanding. Pelatih merencanakan sedikitnya terdapat satu latih tanding dalam satu minggu, tetapi tidak boleh lebih dari $125$ latih tanding dalam periode $75$ minggu. Perlihatkan bahwa ada periode waktu yang terdiri atas beberapa minggu berurutan sehingga terdapat tepat $24$ latih tanding.
Misalkan $a_1$ adalah banyaknya latih tanding yang telah dilakukan petinju sampai hari ke-$i$ dengan $i = 1,2,3,\cdots, 75$ sehingga diperoleh Soal Nomor 24Diberikan bilangan bulat $n \geq 5$. Tuliskan argumentasi kombinatorik untuk memperlihatkan bahwa
Anggap terdapat $2n$ dalam suatu grup yang terdiri dari $n$ pria dan $n$ wanita, dan kita hendak memilih $5$ orang perwakilan dari grup tersebut sehingga banyak cara memilihnya adalah $\displaystyle \binom{2n} {5}.$ Soal Nomor 25Misalkan $m, n$ bilangan bulat positif. Dengan menggunakan argumentasi kombinatorik, buktikan identitas berikut.
Tuliskan dulu persamaan kombinatorialnya sebagai berikut dengan menggunakan sifat kesimetrisan binomial. Soal Nomor 26Diberikan $8$ bilangan bulat. Tunjukkan bahwa terdapat $2$ bilangan di antaranya yang jumlah atau selisihnya habis dibagi $12$.
Jika kedelapan bilangan bulat tersebut dibagi $12$, maka kemungkinan sisanya adalah $\{0,1,2,\cdots, 12\}$. Sekarang siapkan $7$ buah “kotak” dan beri label seperti berikut. Baca Juga: Prinsip Sarang Merpati – Materi, Soal, dan Pembahasan Soal Nomor 27Untuk semua bilangan bulat positif $n \geq 2$, nilai dari $\displaystyle \sum_{k=2}^{n}k(k-2)\binom{n} {k} $ adalah $\cdots \cdot$
Ingat identitas binomial berikut. Soal Nomor 28Tentukan banyaknya permutasi dari $0,1,2,\cdots, 9$ yang diawali dengan digit $987$ atau memuat digit $45$ pada posisi ke-$5$ dan $6$ atau diakhiri dengan digit $123$.
Misalkan Soal Nomor 29Pada acara seminar matematika yang dihadiri oleh $n$ orang peserta seminar. Tunjukkan bahwa di antara para peserta seminar tersebut, senantiasa terdapat dua orang peserta seminar yang mempunyai jumlah kenalan yang sama.
Andaikan ada $n$ peserta seminar, yaitu $k_0, k_1, k_2, \cdots, k_{n-1}$, dengan $k_i$ menyatakan peserta seminar yang memiliki $i$ kenalan dan berbeda-beda. Ini berarti, $k_0$ adalah peserta seminar yang tidak memiliki kenalan sama sekali, $k_1$ adalah peserta seminar yang hanya memiliki $1$ kenalan, dan seterusnya, sampai $k_{n-1}$ adalah peserta seminar yang memiliki $n-1$ kenalan. Jelas ini kontradiksi karena $k_{n-1}$ memiliki kenalan dengan semua peserta seminar yang ada, termasuk dengan $k_0$, padahal $k_0$ tidak memiliki kenalan. Jadi, pengandaian diingkari. Terbukti bahwa selalu terdapat setidaknya dua orang peserta seminar yang memiliki jumlah kenalan yang sama. Soal Nomor 30Dua bilangan bulat positif $a$ dan $b$ dikatakan relatif prima bila pembagi sekutu terbesar $a$ dan $b$ adalah $1$. Banyaknya bilangan bulat positif $k < 210$ yang relatif prima terhadap $210$ adalah $\cdots \cdot$
Gunakan Euler’s Totient Function. Misalkan suatu bilangan bulat positif $n$ dapat dituliskan dalam bentuk faktorisasi prima, yaitu Soal Nomor 31Banyak pasangan bilangan $(a, b, c)$ yang memenuhi $a! + b! = c!$ adalah $\cdots \cdot$
Nilai $(a, b, c)$ pada persamaan $a! +b! =c!$ dipenuhi oleh $(0,0,2), (1,0,2),$ $(0,1,2),$ dan $(1,1,2).$ Misalkan $c$ adalah bilangan bulat positif yang lebih dari dua, sebutlah $n,$ dengan $n > 2$. Sekarang, ambil $a = b = n -1,$ yang merupakan pasangan bilangan terbesar agar bila dijumlahkan dapat mencapai nilai di ruas kanan. Jadi, dapat ditulis $\begin{aligned} & (n-1)! + (n-1)! = n! \\ & 2(n-1)! < n(n-1)! = n!. \end{aligned}$ Jadi, tidak ada nilai $c$ yang dipenuhi oleh $a$ dan $b$ sehingga persamaan itu benar. Dengan demikian, hanya ada $4$ pasangan bilangan $(a, b, c)$ yang memenuhi persamaan $a! + b! = c!$. Soal Nomor 32Titik latis adalah titik dengan koordinat bulat. Misalkan $(w_i, x_i, y_i, z_i)$ dengan $1 \leq i \leq 17$ adalah tujuh belas titik latis berbeda di ruang $\mathbb{R}^4$. Tunjukkan bahwa terdapat sepasang titik latis (dari ketujuh belas titik latis itu) yang titik tengah dari garis yang menghubungkannya juga titik latis.
Berdasarkan prinsip paritasnya (genap-ganjil), terdapat $2^4 = 16$ jenis kombinasi paritas untuk koordinat $(w_i, x_i, y_i, z_i)$. Karena terdapat $17$ titik, berdasarkan Pigeonhole Principle ada dua titik yang paritasnya berjenis sama. Misal kedua titik ini adalah $A = (w_i, x_i, y_i, z_i)$ dan $B = (w_j, x_j, y_j, z_j)$. Akibatnya, $w_i + w_j, x_i + x_j, y_i + y_j$, dan $z_i + z_j$ adalah bilangan genap (ganjil + ganjil = genap, begitu juga genap + genap = genap). Dengan demikian, titik tengah dari garis lurus yang menghubungkan $A$ dan $B$, sebut saja $C$, memiliki koordinat $$C = \left(\dfrac{w_i + w_j} {2},\dfrac{x_i + x_j} {2},\dfrac{y_i + y_j} {2}, \dfrac{z_i + z_j} {2}\right)$$ adalah titik latis (karena bilangan genap bila dibagi $2$ hasilnya adalah bilangan bulat). $\blacksquare$ Soal Nomor 33Hitunglah $\displaystyle \sum_{k=0}^{r} \binom{n+k-1}{k}$.
Ingatlah identitas binomial berikut. $\boxed{\begin{aligned} & \displaystyle \binom{n} {0} = \binom{n-1}{0} = 1 \\ & \binom{n} {k} + \binom{n} {k+1}= \binom{n+1}{k+1} \end{aligned}}$ Dengan menguraikannya dalam bentuk jumlah, diperoleh $$\begin{aligned}\displaystyle \sum_{k=0}^{r} \binom{n+k-1}{k} & = \binom{n-1}{0} + \binom{n} {1} + \binom{n+1}{2} + \cdots + \binom{n+r-1}{r} \\ & = \binom{n+1}{1} + \binom{n+1}{2} + \binom{n+2}{3} + \cdots + \binom{n+r-1}{r} \\ & = \binom{n+2}{2} + \binom{n+2}{3} + \cdots + \binom{n+r-1}{r} \\ & = \binom{n+r} {r}. \end{aligned} $$Jadi, didapat $\boxed{\displaystyle \sum_{k=0}^{r} \binom{n+k-1}{k} = \binom{n+r}{r}} $ |