UTS Struktur Diskret 2025

UTS Struktur Diskrit, gasal 2025/2026. Rabu, 15 Oktober 2025. 10.00–11.40 WIB (100 menit). Buku tertutup.

Tuliskan NIM dan nama pada setiap lembar jawab. Soal terdiri dari dua bagian berdasarkan dosen pengampu. Jawaban Soal A ditulis pada lembar jawab folio; jawaban Soal B ditulis langsung di lembar soal dan dikumpulkan. Nilai UTS = (nilai soal A + B) / 2. Jawab dengan jelas, sertakan asumsi/gambar bila perlu. Dilarang mencontek atau melakukan kecurangan.

Soal A.1 — SubCPMK 03.2, 50%

Dalam permainan misterius di Alice in Borderland, peserta harus membuka gerbang digital agar lolos dari jebakan aktif labirin. Gerbang terbuka jika peserta memasukkan sandi rahasia yang valid. Setiap sandi terdiri dari 6 karakter yang diambil dari 7 huruf: A, B, C, D, E, F, G. Huruf boleh diulang dan urutan diperhatikan.

Tiga kondisi terlarang:

P: sandi memiliki tepat dua huruf B.
Q: sandi dimulai dengan urutan AB.
R: sandi memiliki tepat tiga huruf A.

Pemain aman jika sandi tidak memenuhi satu pun kondisi P, Q, atau R.

a. Tentukan total semua kemungkinan sandi enam karakter tanpa memperhatikan aturan keamanan. b. Tentukan banyak sandi valid yang tidak memenuhi satu pun kondisi terlarang P, Q, R.

Gunakan prinsip inklusi–eksklusi, argumen pencacahan, permutasi, kombinasi, dan komplemen himpunan. Lakukan hingga hasil akhir bilangan bulat.

Nilai aritmetika yang diberikan: 7² = 49; 7³ = 343; 7⁴ = 2401; 7⁶ = 117649; 6⁴ = 1296; 6³ = 216.

Soal A.2 — SubCPMK 03.4, 50%

Dalam simulasi keamanan siber, peneliti mengamati banyak virus komputer yang menyebar setiap tahun, dilambangkan aₙ.

Tahun ke-0 belum ada virus.
Tahun ke-1 ada 1 virus aktif.
Tahun ke-2 ada 3 virus aktif.

Nilai aₙ dihitung dari tiga tahun sebelumnya:

Tiga kali jumlah virus satu tahun sebelumnya berhasil aktif menyebar ke sistem baru.
Tiga kali jumlah virus dua tahun sebelumnya berhasil mati/dibersihkan antivirus.
Sejumlah virus dari tiga tahun sebelumnya (aₙ₋₃) yang sempat terkarantina kembali aktif.

a. Tentukan fungsi rekursif aₙ untuk banyak virus pada tahun ke-n. b. Tentukan solusi umum relasi aₙ = 3aₙ₋₁ − 3aₙ₋₂ + aₙ₋₃ dengan a₀ = 0, a₁ = 1, a₂ = 3.

Dua halaman PDF arsip merupakan halaman tercetak 1/4 dan 2/4.

Inklusi–eksklusi untuk sandi enam karakter dan penyelesaian relasi rekurens. Arsip hanya memuat bagian A, halaman 1–2 dari empat halaman tercetak.

Soal A1 — Menghitung sandi valid

a. Semesta

Enam posisi masing-masing memiliki tujuh pilihan huruf; pengulangan diizinkan dan urutan membedakan sandi. Maka $|U|=7^6=117649$ . Tidak memakai permutasi tanpa pengulangan, sebab huruf yang sama boleh muncul berkali-kali.

b. Komplemen gabungan tiga larangan

Misalkan P adalah sandi dengan tepat dua B, Q sandi berawalan AB, dan R sandi dengan tepat tiga A. Kata tepat membatasi huruf pada posisi sisanya.

Himpunan	Cara menghitung	Jumlah
P	pilih dua posisi B, empat lainnya bukan B: $\binom62 6^4$	19440
Q	dua posisi awal tetap, empat lainnya bebas: $7^4$	2401
R	pilih tiga posisi A, tiga lainnya bukan A: $\binom63 6^3$	4320
P ∩ Q	awal AB sudah mengandung satu B; pilih satu B di empat sisa: $4\cdot6^3$	864
P ∩ R	susun dua B, tiga A, satu huruf selain A/B: $\frac{6!}{2!3!1!}\cdot5$	300
Q ∩ R	awal AB mengandung satu A; pilih dua A tambahan: $\binom42 6^2$	216
P ∩ Q ∩ R	empat posisi sisa memuat dua A, satu B, satu huruf lain: $\frac{4!}{2!1!1!}\cdot5$	60

Pada P ∩ Q, enam pilihan untuk posisi non-B masih boleh A. Pada Q ∩ R, enam pilihan untuk posisi non-A masih boleh B. Pada irisan tiga, huruf sisa memiliki lima pilihan agar jumlah A/B tidak bertambah.

$|P\cup Q\cup R|=19440+2401+4320-864-300-216+60=24841.$

Jadi banyak sandi aman adalah $117649-24841=\boxed{92808}$ .

Verifikasi independen dapat dilakukan dengan enumerasi seluruh $7^6$ sandi dan menghitung yang jumlah B-nya bukan 2, tidak berawalan AB, serta jumlah A-nya bukan 3. Pemeriksaan tersebut memberi 92808 juga.

Soal A2 — Rekurens jumlah virus

a. Model rekursif

Kontribusi satu tahun sebelumnya positif tiga kali, dua tahun sebelumnya negatif tiga kali, dan tiga tahun sebelumnya positif satu kali. Dengan kondisi awal yang diberikan:

$a_0=0,\quad a_1=1,\quad a_2=3,\qquad a_n=3a_{n-1}-3a_{n-2}+a_{n-3}\quad(n\ge3).$

Tanda negatif pada kontribusi dua tahun sebelumnya menyatakan pembersihan, bukan tambahan infeksi.

b. Solusi eksplisit

Substitusi $a_n=r^n$ menghasilkan $r^3-3r^2+3r-1=(r-1)^3=0$ . Akar 1 bermultiplikitas tiga memberi bentuk umum $a_n=c_0+c_1n+c_2n^2$ . Kondisi awal memberi $c_0=0$ , $c_1+c_2=1$ , $2c_1+4c_2=3$ , sehingga $c_1=c_2=1/2$ .

$\boxed{a_n=\frac{n(n+1)}2}.$

Pengecekan: barisan dimulai 0, 1, 3, 6, 10, 15; untuk n = 3, rekurens memberi $3(3)-3(1)+0=6$ . Bentuk polinomial kuadrat diperlukan karena akar berulang; menulis hanya $C\cdot1^n$ tidak dapat memenuhi tiga kondisi awal.

Pembahasan ditulis independen oleh belajar.myudak, bukan kunci jawaban resmi. Soal asli tetap milik pengampu mata kuliah dan ditampilkan langsung dari arsip Google Drive.