Latihan Akhir - Bagian II: Essay Pembuktian

Halaman ini berisi 5 soal essay pembuktian matematis bidang Kombinatorika beserta langkah-langkah pembahasannya.

5 Soal Essay Pembuktian

✏️ Latihan Soal 1 (Pembuktian Dua Orang dengan Jumlah Kenalan Sama)

Buktikan bahwa di dalam sebuah pesta yang dihadiri oleh $n$ orang ( $n \geq 2$ ), selalu terdapat setidaknya dua orang yang memiliki jumlah kenalan yang sama di antara tamu-tamu tersebut. (Asumsikan hubungan kenalan bersifat simetris dan tidak ada yang mengenal dirinya sendiri).

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan:

Merpati: $n$ orang tamu.
Sangkar: Jumlah kenalan yang mungkin ${0, 1, \dots, n - 1}$ .
Analisis Kasus:
1. Jika ada orang mengenal $0$ orang, maka tidak ada orang mengenal $n - 1$ orang. Kemungkinan kenalan: ${0, 1, \dots, n - 2}$ ( $n - 1$ sangkar).
2. Jika tidak ada orang mengenal $0$ orang, kemungkinan kenalan: ${1, 2, \dots, n - 1}$ ( $n - 1$ sangkar).
Kesimpulan: Ada $n$ orang dan $n - 1$ kemungkinan nilai kenalan. Berdasarkan Pigeonhole Principle, pasti ada 2 orang yang jumlah kenalannya sama. $■$

✏️ Latihan Soal 2 (EGF untuk Angka 0 Genap & 1 Minimal Sekali)

Gunakan fungsi pembangkit eksponensial untuk menentukan banyaknya cara menyusun barisan panjang $n$ dari angka ${0, 1, 2}$ sedemikian sehingga angka 0 muncul dalam jumlah genap dan angka 1 muncul setidaknya satu kali.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: EGF: $\hat{A} (x) = (\frac{e ^{x} + e ^{- x}}{2}) (e^{x} - 1) e^{x} = \frac{e ^{3 x} - e ^{2 x} + e ^{x} - 1}{2}$ . Maka $a_{n} = \frac{3 ^{n} - 2 ^{n} + 1}{2}$ . $■$

✏️ Latihan Soal 3 (Batas Maksimum Sisi Graf dengan k Komponen)

Misalkan $G$ adalah graf sederhana dengan $n$ titik dan $k$ komponen terhubung. Buktikan bahwa jumlah sisi maksimal di $G$ adalah:

$∣ E ∣ \leq \frac{( n - k ) ( n - k + 1 )}{2}$

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Sisi maksimal tercapai saat $k - 1$ komponen berupa 1 titik terisolasi dan 1 komponen terbesar berisi $n - k + 1$ titik. Maka $∣ E ∣ \leq (2 n - k + 1) = \frac{( n - k ) ( n - k + 1 )}{2}$ . $■$

✏️ Latihan Soal 4 (Solusi Bulat Terbatas dengan PIE)

Tentukan banyaknya solusi bulat dari $x_{1} + x_{2} + x_{3} + x_{4} = 18$ dengan batasan $0 \leq x_{i} \leq 7$ untuk setiap $i = 1, 2, 3, 4$ . Gunakan Prinsip Inklusi-Eksklusi.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: $N = (3 21) = 1330$ .

1 Pelanggaran ( $x_{i} \geq 8$ ): $4 \times (3 13) = 4 \times 286 = 1144$ .
2 Pelanggaran: $6 \times (3 5) = 6 \times 10 = 60$ . Total solusi $= 1330 - 1144 + 60 = 246$ . $■$

✏️ Latihan Soal 5 (Pembuktian Kombinatorik Identitas Kuasa Binomial)

Tunjukkan bahwa untuk setiap bilangan asli $n$ , berlaku identitas kombinatorik berikut menggunakan argumen kombinatorik (combinatorial proof):

$\sum_{k = 0}^{n} (k n)^{2} = (n 2 n)$

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan:

Ruas Kanan $(n 2 n)$ : Memilih $n$ orang komite dari $n$ pria dan $n$ wanita.
Ruas Kiri $\sum_{k = 0}^{n} (k n)^{2}$ : Memilih $k$ pria ( $(k n)$ ) dan $n - k$ wanita ( $(n - k n) = (k n)$ ). Total cara $= \sum_{k = 0}^{n} (k n)^{2}$ . Terbukti. $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Latihan Akhir - Bagian I: Isian Singkat
Kembali ke Materi Kombinatorika

Latihan Akhir - Bagian II: Essay Pembuktian

5 Soal Essay Pembuktian

Navigasi Sub-Topik

Materi Terkait (Linked References) (4)

Latihan Akhir - Bagian I: Isian Singkat

Latihan Akhir - Bagian I: Isian Singkat

Latihan Akhir - Bagian I: Isian Singkat

Latihan Akhir - Bagian I: Isian Singkat

Diskusi & Tanya Jawab

Title