Naskah Soal & Pembahasan ONMIPA PT 2018 — Kombinatorika

🏆 ONMIPA PT 2018 • ← Direktori Utama ONMIPA

← 2017 2018 2019 →

📍 Navigasi Bidang (2018):

📐 Analisis Real 📊 Aljabar Linear 🔍 Struktur Aljabar 🌀 Analisis Kompleks 🎲 Kombinatorika

Halaman ini berisi naskah soal dan pembahasan ONMIPA-PT 2018 Seleksi Wilayah untuk bidang Kombinatorika.

Bagian I: Soal Isian Singkat

Soal Isian Singkat #1 Kombinatorika

Banyaknya subset dari himpunan ${1, 2, \dots, 25}$ yang terdiri dari $3$ bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

1771

Lihat Pembahasan

Banyaknya subset beranggota $k$ dari ${1, 2, \dots, n}$ tanpa dua bilangan berurutan diberikan oleh rumus $(k n - k + 1)$ .

Untuk $n = 25$ dan $k = 3$ :

$(3 25 - 3 + 1) = (3 23) = \frac{23 \times 22 \times 21}{3 \times 2 \times 1} = 1771.$

Soal Isian Singkat #2 Kombinatorika

Sebuah klub bulu tangkis mempunyai $35$ anggota terdiri $15$ anak laki-laki dan $20$ anak perempuan. Klub akan membentuk $10$ pasangan ganda campuran. Banyaknya cara yang mungkin untuk membentuk $10$ pasangan ganda campuran adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

\frac{20! 15!}{5! 10! 10!}

Lihat Pembahasan

Pilih 10 anak laki-laki dari 15: $(10 15)$ cara. Pilih 10 anak perempuan dari 20: $(10 20)$ cara. Pasangkan 10 anak laki-laki dan 10 anak perempuan terpilih: $10!$ cara.

Total cara:

$(10 15) \times (10 20) \times 10! = \frac{15 !}{10 ! 5 !} \times \frac{20 !}{10 ! 10 !} \times 10! = \frac{20 ! 15 !}{5 ! 10 ! 10 !} .$

Soal Isian Singkat #3 Kombinatorika

Sebuah toko roti memproduksi 8 jenis donat. Donat dikemas dalam kotak berisi $12$ buah donat. Banyaknya cara untuk mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk meciptakan setiap jenis adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

330

Lihat Pembahasan

Karena setiap jenis 8 donat harus ada minimal 1 buah, terpakai 8 donat. Sisa 4 donat bebas dipilih dari 8 jenis donat.

Banyaknya cara dengan pengulangan (Stars and Bars):

$(4 4 + 8 - 1) = (4 11) = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1} = 330.$

Soal Isian Singkat #4 Kombinatorika

Untuk bilangan bulat positif $n \geq 2$ , nilai dari $k = 2 \sum n (- 1)^{k} k (k n)$ adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

n

Lihat Pembahasan

Dari Teorema Binomial: $\sum_{k = 2}^{n} (k n) x^{k} = (1 + x)^{n} - n x - 1$ .

Turunkan terhadap $x$ lalu kalikan dengan $x$ :

$\sum_{k = 2}^{n} k (k n) x^{k} = n x (1 + x)^{n - 1} - n x .$

Substitusi $x = - 1$ :

$\sum_{k = 2}^{n} (- 1)^{k} k (k n) = n (- 1) (1 - 1)^{n - 1} - n (- 1) = 0 + n = n .$

Soal Isian Singkat #5 Kombinatorika

Misalkan $b_{n}$ adalah banyaknya untaian atas $n$ huruf yang dapat dibentuk dengan menggunakan $A, B,$ dan $C$ sedemikian sehingga bila huruf $A$ muncul bukan sebagai huruf akhir pada untaian, maka $A$ harus segera diikuti oleh $B$ . Relasi rekurensi dari barisan ${b_{n}}$ untuk $n \geq 3$ adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

b_n = 2b_{n-1} + b_{n-2}

Lihat Pembahasan

Bagi kasus berdasarkan huruf pertama untaian berpanjang $n$ :

Jika diawali huruf $B$ atau $C$ ( $2$ pilihan), sisa untaian berpanjang $n - 1 ⟹ 2 b_{n - 1}$ .
Jika diawali huruf $A$ , huruf berikutnya harus $B$ (diikuti pasangan $A B$ ), sisa untaian berpanjang $n - 2 ⟹ b_{n - 2}$ .

Maka relasi rekurensinya adalah $b_{n} = 2 b_{n - 1} + b_{n - 2}$ untuk $n \geq 3$ dengan kondisi awal $b_{1} = 3, b_{2} = 7$ .

Soal Isian Singkat #6 Kombinatorika

Diberikan permutasi $π = (1 π (1) 2 π (2) \dots \dots n π (n))$ dengan $n \geq 7$ . Banyaknya permutasi $π$ sehingga $π (1) = 5$ atau $π (3) = 7$ atau $π (6) = 2$ adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

3(n - 1)! - 3(n - 2)! + (n - 3)!

Lihat Pembahasan

Definisikan himpunan kejadian $A = {π ∣ π (1) = 5}$ , $B = {π ∣ π (3) = 7}$ , dan $C = {π ∣ π (6) = 2}$ .

$∣ A ∣ = ∣ B ∣ = ∣ C ∣ = (n - 1)!$
$∣ A \cap B ∣ = ∣ A \cap C ∣ = ∣ B \cap C ∣ = (n - 2)!$
$∣ A \cap B \cap C ∣ = (n - 3)!$

Berdasarkan Prinsip Inklusi-Eksklusi:

$∣ A \cup B \cup C ∣ = 3 (n - 1)! - 3 (n - 2)! + (n - 3)! .$

Soal Isian Singkat #7 Kombinatorika

Dalam bentuk paling sederhana, fungsi pembangkit eksponensial (exponential generating function) dari barisan $(0!, 1!, 2!, \dots, n!, \dots)$ adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

\frac{1}{1 - x}

Lihat Pembahasan

Fungsi pembangkit eksponensial dari barisan $h_{n} = n!$ adalah:

$g^{(e)} (x) = \sum_{n = 0}^{\infty} n! \frac{x ^{n}}{n !} = \sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x} .$

Soal Isian Singkat #8 Kombinatorika

Diberikan sebuah graf sederhana $G$ atas $6$ titik $v_{1}, v_{2}, \dots, v_{6}$ . Bila $G$ mempunyai $8$ sisi dan derajat dari titik-titik $v_{1}, v_{2}, \dots, v_{5}$ masing-masing adalah $1, 3, 3, 3,$ dan $2$ , maka derajat titik $v_{6}$ adalah $\dots$

Lihat Jawaban

Kunci Jawaban:

4

Lihat Pembahasan

Berdasarkan Lemma Jabat Tangan (Handshaking Lemma):

$\sum_{i = 1}^{6} deg (v_{i}) = 2 \cdot ∣ E ∣$

$1 + 3 + 3 + 3 + 2 + deg (v_{6}) = 2 (8) = 16$

$12 + deg (v_{6}) = 16 ⟹ deg (v_{6}) = 4.$

Bagian II: Soal Uraian / Esai

Soal Uraian / Esai #1 Kombinatorika

Perhatikan barisan Fibonacci dengan relasi $f_{n} = f_{n - 1} + f_{n - 2}$ untuk $n \geq 2$ , dengan $f_{0} = 0, f_{1} = 1$ . Definisikan matriks $F = [1110] = [f_{2} f_{1} f_{1} f_{0}] .$

(a) Buktikan bahwa $F^{n} = [1110]^{n} = [f_{n + 1} f_{n} f_{n} f_{n - 1}]$

(b) Buktikan bahwa $f_{n + 1} f_{n - 1} - f_{n}^{2} = {1, - 1, bila n genap bila n ganjil$ .

Lihat Pembahasan

(a) Bukti dengan induksi matematika:

Basis $n = 1$ : $F^{1} = [1110] = [f_{2} f_{1} f_{1} f_{0}]$ (benar).
Langkah induksi: Andaikan $F^{n} = [f_{n + 1} f_{n} f_{n} f_{n - 1}]$ . $F^{n + 1} = F \cdot F^{n} = [1110] [f_{n + 1} f_{n} f_{n} f_{n - 1}] = [f_{n + 1} + f_{n} f_{n + 1} f_{n} + f_{n - 1} f_{n}] = [f_{n + 2} f_{n + 1} f_{n + 1} f_{n}] .$

(b) Hitung determinan kedua ruas dari persamaan (a): $det (F^{n}) = (det F)^{n} = (1 (0) - 1 (1))^{n} = (- 1)^{n}$ $det [f_{n + 1} f_{n} f_{n} f_{n - 1}] = f_{n + 1} f_{n - 1} - f_{n}^{2}$ Maka $f_{n + 1} f_{n - 1} - f_{n}^{2} = (- 1)^{n}$ , bernilai $1$ untuk $n$ genap dan $- 1$ untuk $n$ ganjil.

Soal Uraian / Esai #2 Kombinatorika

Andaikan $G$ adalah sebuah graf sederhana. Perlihatkan bahwa pada sebuah graf sederhana $G$ terdapat sedikitnya dua titik dengan derajat sama.

Lihat Pembahasan

Misalkan $G$ memiliki $n$ buah titik. Derajat dari setiap titik di $G$ berkisar di ${0, 1, 2, \dots, n - 1}$ .

Jika $G$ memiliki titik berderajat $0$ (titik terisolasi), maka tidak ada titik yang berderajat $n - 1$ (sebab tidak bisa bertetangga dengan titik terisolasi). Maka pilihan derajat hanya ${0, 1, \dots, n - 2}$ ( $n - 1$ kemungkinan untuk $n$ titik).
Jika $G$ tidak memiliki titik berderajat $0$ , maka pilihan derajat hanyalah ${1, 2, \dots, n - 1}$ ( $n - 1$ kemungkinan untuk $n$ titik).

Berdasarkan Prinsip Sarang Burung Merpati (Pigeonhole Principle), karena terdapat $n$ titik dan hanya $n - 1$ kemungkinan nilai derajat, haruslah terdapat sedikitnya 2 titik yang memiliki derajat sama.

Soal Uraian / Esai #3 Kombinatorika

Tentukan banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah.

Lihat Pembahasan

Gunakan Fungsi Pembangkit Eksponensial (Exponential Generating Function):

Merah (genap): $M (x) = \sum_{k = 0}^{\infty} \frac{x ^{2 k}}{( 2 k )!} = \frac{e ^{x} + e ^{- x}}{2}$ .
Hijau & Biru (bebas): $H (x) = B (x) = \sum_{k = 0}^{\infty} \frac{x ^{k}}{k !} = e^{x}$ .

Fungsi pembangkit total $g (x) = M (x) H (x) B (x)$ :

$g (x) = \frac{e ^{x} + e ^{- x}}{2} \cdot e^{x} \cdot e^{x} = \frac{e ^{3 x} + e ^{x}}{2} = \sum_{n = 0}^{\infty} \frac{3 ^{n} + 1}{2} \frac{x ^{n}}{n !}$

Banyaknya cara mewarnai persegi panjang $1 \times n$ adalah $\frac{3 ^{n} + 1}{2}$ .

🏆 ONMIPA PT 2018 • ← Direktori Utama ONMIPA

← 2017 2018 2019 →

📍 Navigasi Bidang (2018):

📐 Analisis Real 📊 Aljabar Linear 🔍 Struktur Aljabar 🌀 Analisis Kompleks 🎲 Kombinatorika

Naskah Soal & Pembahasan ONMIPA PT 2018 — Kombinatorika

Bagian I: Soal Isian Singkat

Bagian II: Soal Uraian / Esai

Materi Terkait (Linked References) (0)

Diskusi & Tanya Jawab

Title