Dalam tulisan ini, kita akan membahas soal Kombinatorika dalam ON MIPA-PT Matematika Tahun 2019. Soal kombinatorika tahun ini terbagi ke dalam dua hari. Pada hari pertama dan kedua, terdapat masing-masing satu soal isian dan satu soal uraian. Berikut adalah keempat soal kombinatorika beserta pembahasannya.

Tulisan ini adalah bagian dari seri Pembahasan Soal ON MIPA-PT Matematika. Jadi, setelah membaca tulisan ini, pastikan anda mengetuk tautan tersebut. Di sana tersedia pembahasan soal-soal ON MIPA-PT lainnya.

Isian Nomor 6 (Hari 1)

Sebuah toko menjual empat jenis kembang gula rasa: mangga, jeruk, durian, dan kopi. Untuk keperluan sampel akan dipilih paling banyak 3 rasa mangga, paling banyak 3 rasa jeruk, paling banyak 2 rasa durian, dan paling banyak 2 rasa kopi. Banyaknya cara untuk memilih sampel berukuran 5 adalah....

Pembahasan

Kita akan menyelesaikan soal ini dengan menggunakan fungsi pembangkit. Karena pemilihan sampel tidak memperhatikan urutan, maka kita akan menggunakan fungsi pembangkit biasa.

Sebelum melangkah lebih jauh, berikut beberapa sifat yang akan kita gunakan dalam penyelesaian ini.

Sifat

Untuk setiap $n \in \mathbb{Z}^{+}$, berlaku:
Sifat 1
$$(1+x+x^2+ \cdots +x^n)=\frac{1-x^{n+1}}{1-x}$$
Sifat 2
$$\frac{1}{(1-x)^n} = \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k$$

Kita akan memilih paling banyak 3 rasa mangga, sehingga faktor yang bersesuaian adalah $1+x+x^2+x^3$. Dengan melakukan hal yang sama pada tiga jenis kembang gula lainnya, kita memperoleh fungsi pembangkit berikut.$$f(x)=(1+x+x^2+x^3)^2(1+x+x^2)^2$$

Banyak sampel berukuran 5 sama dengan koefisien $x^5$ pada fungsi pembangkit $f(x)$. Berdasarkan Sifat 1, fungsi pembangkit $f(x)$ menjadi$$\begin{aligned}f(x) &= \left( \frac{1-x^4}{1-x} \right)^2 \left( \frac{1-x^3}{1-x} \right)^2 \\&= \frac{(1-x^4)^2(1-x^3)^2}{(1-x)^2(1-x)^2} \\&= \frac{(1-2x^4+x^8)(1-2x^3+x^6)}{(1-x)^4} \\&= (1-2x^3-2x^4+x^6+4x^7+x^8-2x^{10}-2x^{11}+x^{14}) \frac{1}{(1-x)^4}\end{aligned}$$

Berikutnya, berdasarkan Sifat 2 diperoleh$$f(x) = (1-2x^3-2x^4+x^6+4x^7+x^8-2x^{10}-2x^{11}+x^{14}) \sum_{k=0}^{\infty} \binom{k+3}{k} x^k$$

Misalkan $y=\sum_{k=0}^{\infty} \binom{k+3}{k} x^k$. Berdasarkan sifat distributif, kita dapat mengalikan setiap suku pada polinomial di atas dengan $y$. Namun, kita tidak perlu memperhatikan suku yang memuat variabel $x$ dengan pangkat lebih dari 5, karena kita ingin menentukan koefisien $x^5$ pada $f(x)$. Kita akan meninjau suku-suku yang memuat variabel $x$ dengan pangkat kurang dari atau sama dengan 5, yaitu $1, \: -2x^3, \: \text{dan } -2x^4$.

Tinjau suku $-2x^4$.
Untuk suku $-2x^4$, kita memperoleh bentuk berikut.$$-2x^4 \cdot y = -2x^4 \cdot \sum_{k=0}^{\infty} \binom{k+3}{k} x^k$$Agar $x^5$ muncul, kita perlu memilih nilai $k=1$. Sehingga suku yang memuat $x^5$ pada bagian ini adalah$$-2x^4 \cdot \binom{1+3}{1} x^1 = -2\binom{4}{1} x^5$$

Tinjau suku $-2x^3$.
Pilih $k=2$, sehingga suku yang memuat $x^5$ pada bagian ini adalah$$-2x^3 \cdot \binom{2+3}{2} x^2 = -2\binom{5}{2} x^5$$

Tinjau suku $1$.
Pilih $k=5$, sehingga suku yang memuat $x^5$ pada bagian ini adalah$$1 \cdot \binom{5+3}{5} x^5 = \binom{8}{5} x^5$$

Dengan demikian, koefisien $x^5$ pada $f(x)$ adalah$$\binom{8}{5}-2\binom{5}{2}-2\binom{4}{1} = 56-2 \cdot 10-2 \cdot 4=28$$Jadi, banyaknya cara untuk memilih sampel berukuran 5 adalah 28.

Uraian Nomor 4 (Hari 1)

Misalkan $n$ merupakan bilangan bulat positif yang tidak habis dibagi oleh 2 dan 5. Perlihatkan bahwa terdapat bilangan bulat $q$ yang merupakan kelipatan dari $n$ sedemikian sehingga semua digit dari $q$ adalah 1. (Contoh: Bila $n=3$, maka $q=111$ adalah kelipatan dari 3 yang semua digitnya adalah 1).

Pembahasan

Misalkan $n$ adalah bilangan bulat positif yang tidak habis dibagi 2 dan 5. Berdasarkan syarat ini, diperoleh $n$ tidak habis dibagi 10, atau dalam kata lain $n$ dan 10 relatif prima.

Kita akan membuktikan pernyataan pada soal dengan Prinsip Sangkar Burung (Pigeonhole Principle). Namun, sebelum itu, saya akan menuliskan sebuah teorema yang akan digunakan dalam bukti ini.

Teorema A

Misalkan $a,b,c \in \mathbb{Z}$, dengan $a \neq 0$.
Jika $a \mid bc$ dan $\text{FPB}(a,b)=1$ maka $a \mid c$

Himpunan sisaan terkecil modulo $n$ adalah $\{0,1,2, \cdots ,n-1 \}$ yang terdiri dari $n$ anggota. Misalkan $R(d)$ menyatakan bilangan $d$ digit yang seluruhnya terdiri dari angka 1. Perhatikan$$R(1),R(2),R(3), \cdots,R(n),R(n+1)$$yang terdiri dari $n+1$ bilangan. Berdasarkan prinsip sangkar burung, terdapat dua bilangan berbeda yang memiliki sisaan sama jika dibagi $n$. Kita misalkan bilangan itu $R(a)$ dan $R(b)$. Tanpa mengurangi keumuman, kita misalkan pula $a>b$.

Karena memiliki sisaan sama, kita dapat menulisnya sebagai$$\begin{aligned}R(a) &\equiv R(b) \pmod{n} \\R(a)-R(b) &\equiv 0 \pmod{n}\end{aligned}$$

Bentuk terakhir ini diperoleh jika $n \mid R(a)-R(b)$. Perhatikan bahwa $R(a)-R(b)=R(a-b) \cdot 10^b$. Sehingga$$n \mid R(a-b) \cdot 10^b$$

Pada awal pembahasan, kita tahu bahwa $n$ dan 10 relatif prima. Hal ini berakibat $n$ juga relatif prima dengan $10^b$, atau dapat ditulis $\text{FPB}(n,10^b)=1$. Berdasarkan teorema A, diperoleh $n \mid R(a-b)$. Dengan kata lain, $R(a-b)$ merupakan kelipatan dari $n$.

Jadi, terdapat bilangan bulat kelipatan $n$ yang semua digitnya adalah 1. Terbukti.

Isian Nomor 6 (Hari 2)

Sebuah tes terdiri atas 10 soal. Setiap soal diberi nilai bulat dan paling sedikit diberi nilai 5. Bila soal pertama hanya boleh diberi nlai 10 atau 15 dan total nilai tes adalah 100, banyaknya cara memberi nilai pada tes tersebut adalah....

Pembahasan

Banyaknya cara memberi nilai pada tes tersebut sama dengan banyaknya solusi bilangan bulat tak negatif dari persamaan$$x_1+x_2+x_3+ \cdots + x_{10}=100$$dengan syarat $x_1=10$ atau $x_1=15$, dan $x_i \geq 5$ untuk $i=2,3, \cdots 10$.

Misalkan $y_i=x_i-5$ untuk $i=2,3, \cdots 10$, sehingga $y_i \geq 0$ dan persamaan semula menjadi$$x_1+y_2+y_3+ \cdots + y_{10}=55 \quad \ast$$dengan syarat $x_1=10$ atau $x_1=15$, dan $y_i \geq 0$ untuk $i=2,3, \cdots 10$.

Dari sini, kita dapat membagi menjadi dua kasus, yaitu untuk $x_1=10$ dan $x_1=15$.

KASUS I
Jika $x_1=10$ maka persamaan $\ast$ menjadi$$\begin{aligned}10+y_2+y_3+ \cdots + y_{10} &= 55 \\y_2+y_3+ \cdots + y_{10} &= 45\end{aligned}$$dengan syarat $y_i \geq 0$ untuk $i=2,3, \cdots 10$.

Banyaknya solusi bulat tak negatif dari persamaan ini adalah$$\binom{45+9-1}{45}=\binom{53}{45}$$

KASUS 2
Jika $x_1=15$ maka persamaan $\ast$ menjadi$$\begin{aligned}15+y_2+y_3+ \cdots + y_{10} &= 55 \\y_2+y_3+ \cdots + y_{10} &= 40\end{aligned}$$dengan syarat $y_i \geq 0$ untuk $i=2,3, \cdots 10$.

Banyaknya solusi bulat tak negatif dari persamaan ini adalah$$\binom{40+9-1}{40}=\binom{48}{40}$$

Berdasarkan kedua kasus di atas, banyaknya solusi bulat tak negatif dari $\ast$ adalah $\binom{53}{45}+\binom{48}{40}$.
Jadi, banyaknya cara memberi nilai pada tes tersebut adalah $\binom{53}{45}+\binom{48}{40}$.

Uraian Nomor 4 (Hari 2)

Diberikan bilangan bulat $n \geq 4$. Tuliskan sebuah argumentasi kombinatorial untuk memperlihatkan$$\sum_{k=4}^n k \binom{n-4}{n-k} \binom{n+4}{k} = (n+4) \binom{2n-1}{n-1}$$

Pembahasan

Misalkan terdapat $2n$ orang ($n \geq 4$), yang terdiri dari $n-4$ perempuan dan $n+4$ laki-laki. Akan dibentuk sebuah kelompok yang terdiri dari $n$ orang. Salah seorang laki-laki dalam kelompok tersebut ditunjuk sebagai ketua kelompok. Hal ini dapat dilakukan melalui dua cara.

CARA I
Di antara $n$ orang yang terpilih, terdapat minimal 4 orang laki-laki (karena banyaknya perempuan adalah $n-4$) dan maksimal $n$ orang laki-laki. Misalkan $k$ menyatakan banyaknya laki-laki di antara $n$ orang yang terpilih, sehingga perempuan yang terpilih sebanyak $n-k$. Banyak cara melakukan hal ini adalah$$\binom{n-4}{n-k} \binom{n+4}{k}$$

Berikutnya, di antara $k$ laki-laki yang terpilih, akan ditunjuk satu orang sebagai ketua kelompok. Banyak cara memilih ketua adalah $\binom{k}{1}=k$. Berdasarkan aturan perkalian, banyak cara membentuk kelompok yang terdiri dari $n-k$ perempuan dan $k$ laki-laki, dimana salah seorang laki-laki menjadi ketua adalah$$k\binom{n-4}{n-k} \binom{n+4}{k}$$

Karena nilai $k$ yang mungkin adalah bilangan bulat dari 4 sampai $n$, maka secara keseluruhan, banyaknya cara adalah$$\sum_{k=4}^n k \binom{n-4}{n-k} \binom{n+4}{k}$$

CARA II
Pertama, kita memilih seorang laki-laki sebagai ketua kelompok. Karena terdapat $n+4$ laki-laki, maka banyaknya cara adalah $\binom{n+4}{1}=n+4$. Berikutnya, kita perlu melengkapi kelompok tersebut, dengan memilih sebanyak $n-1$ anggota dari $2n-1$ orang yang tersisa (karena telah dipilih 1 orang sebagai ketua). Berdasarkan aturan perkalian, banyak cara membentuk kelompok yang terdiri dari $n-k$ perempuan dan $k$ laki-laki, dimana salah seorang laki-laki menjadi ketua adalah$$(n+4) \binom{2n-1}{n-1}$$

Berdasarkan kedua cara di atas, diperoleh$$\sum_{k=4}^n k \binom{n-4}{n-k} \binom{n+4}{k} = (n+4) \binom{2n-1}{n-1}$$Terbukti.

Semoga bermanfaat! Jika ada yang perlu diperbaiki atau anda punya solusi yang berbeda, silakan beritahu melalui komentar.