--- topicNum: 6 topic: "Greedy & Strategi Permainan" --- ### 1 — Tic Tac Toe 4×4 (KSNK 2021 #9 modified) ## Jawaban: **18** ### Langkah 1 — Formulasi Masalah Papan 4×4 = 16 kotak. X bermain pertama, jadi posisi akhir penuh memiliki tepat **8 huruf X** dan **8 huruf O**. Kondisi *seimbang* berarti papan penuh **tanpa ada 3 huruf sama dalam 1 garis lurus** (horizontal, vertikal, atau diagonal) — untuk X maupun O. ### Langkah 2 — Identifikasi Pola Baris Valid Setiap baris panjang 4 tidak boleh memiliki **3 karakter berurutan yang sama** (substring `XXX` atau `OOO`). Dari 16 kombinasi biner, yang memenuhi syarat ada tepat **10 pola**: | Pola | Jumlah X | |------|----------| | `O O X O`, `O X O O` | 1 X | | `O O X X`, `O X O X`, `O X X O`, `X O O X`, `X O X O`, `X X O O` | 2 X | | `X O X X`, `X X O X` | 3 X | ### Langkah 3 — Kendala yang Harus Dipenuhi Untuk 4 baris (r₁, r₂, r₃, r₄): **Kolom** (8 kendala): Untuk setiap kolom j, tidak boleh rᵢ[j] = rᵢ₊₁[j] = rᵢ₊₂[j] **Diagonal ↘** (4 kendala): - r₁[1]=r₂[2]=r₃[3]; r₂[2]=r₃[3]=r₄[4] - r₁[2]=r₂[3]=r₃[4]; r₂[1]=r₃[2]=r₄[3] **Diagonal ↗** (4 kendala): - r₄[1]=r₃[2]=r₂[3]; r₃[2]=r₂[3]=r₁[4] - r₄[2]=r₃[3]=r₂[4]; r₃[1]=r₂[2]=r₁[3] ### Langkah 4 — Pendekatan Backtracking Karena total 8 X, distribusi X per baris yang mungkin adalah: - **(2,2,2,2)**: semua baris punya 2 X → 6⁴ = 1296 kombinasi awal - **(1,2,2,3)**: satu baris 1X, dua baris 2X, satu baris 3X → 1728 kombinasi - **(1,1,3,3)**: dua baris 1X, dua baris 3X → 96 kombinasi Total ~3120 kandidat. Setelah menerapkan semua kendala kolom dan diagonal: ### Hasil: 18 Posisi Akhir Draw Berikut seluruh 18 papan (X=X, O=O): ``` #1 #2 #3 #4 #5 #6 OOXX OOXX OXOX OXOX OXOX OXOX XXOO XXOO OXOO OXOX XOXO XXOO OOXX OOXX XOXX XOXO XOXO OOXX XOXO XXOO XOXO XOXO OXOX XOXO ``` ``` #7 #8 #9 #10 #11 #12 OXOX OXOX OXXO XOOX XOXO XOXO XXOO XXOX XOOX OXXO OOXO OOXX OOXX OOXO OXXO XOOX XXOX XXOO XXOO XOXO XOOX OXXO OXOX OOXX ``` ``` #13 #14 #15 #16 #17 #18 XOXO XOXO XOXO XOXO XXOO XXOO OOXX OXOX XOXO XOXX OOXX OOXX XXOO OXOX OXOX OXOO XXOO XXOO OXOX XOXO OXOX OXOX OOXX OXOX ``` **Rincian:** 14 papan berasal dari distribusi (2,2,2,2), dan 4 papan dari distribusi (1,2,2,3). Distribusi (1,1,3,3) tidak menghasilkan papan yang valid setelah cek diagonal. $$\boxed{18}$$ --- ### 2 — Permainan Bebek (KSNK 2021 #13) Tiga bebek: Kwik (peluang berhasil **100%**), Kwak (**33%** ≈ 1/3), Kwek (**66%** ≈ 2/3). Urutan giliran acak (6 kemungkinan, sama peluang). **Strategi optimal:** Setiap bebek menyerang lawan yang paling berbahaya (peluang tertinggi) yang masih hidup. Kwik selalu jadi target utama karena 100% kill rate. **Analisis per urutan giliran (6 permutasi):** | # | Urutan | Kwik menang | Kwak menang | Kwek menang | |---|---------|:-----------:|:-----------:|:-----------:| | 1 | Kwik→Kwak→Kwek | ~66,5% | ~33,5% | 0% | | 2 | Kwik→Kwek→Kwak | ~66,5% | ~33,5% | 0% | | 3 | Kwak→Kwik→Kwek | ~44,6% | ~27,1% | ~28,3% | | 4 | Kwak→Kwek→Kwik | ~14,9% | ~31,2% | ~53,9% | | 5 | Kwek→Kwik→Kwak | ~22,3% | ~39,6% | ~38,1% | | 6 | Kwek→Kwak→Kwik | ~14,7% | ~37,5% | ~47,8% | | | **Rata-rata** | **~38,3%** | **~33,8%** | **~28,0%** | **Kesimpulan:** Tidak ada bebek yang peluangnya melebihi 1/2. Bahkan Kwik yang paling kuat hanya ~38%. **Metode Simulasi Monte Carlo Manual (tanpa komputer):** **Alat:** 1 dadu standar (1–6), kertas & pensil untuk mencatat. **Langkah 1 — Tentukan urutan giliran (lempar dadu):** | Dadu | Urutan giliran | |-----|-----------------| | 1 | Kwik → Kwak → Kwek | | 2 | Kwik → Kwek → Kwak | | 3 | Kwak → Kwik → Kwek | | 4 | Kwak → Kwek → Kwik | | 5 | Kwek → Kwik → Kwak | | 6 | Kwek → Kwak → Kwik | **Langkah 2 — Tentukan hasil serangan (lempar dadu per serangan):** - **Kwik** (100%): selalu berhasil, tidak perlu lempar dadu - **Kwak** (33% ≈ 1/3): Dadu **1–2** = berhasil, **3–6** = gagal - **Kwek** (66% ≈ 2/3): Dadu **1–4** = berhasil, **5–6** = gagal **Langkah 3 — Jalankan satu simulasi (contoh):** *Contoh iterasi ke-1:* 1. Lempar dadu untuk urutan → dapat **3** → urutan: **Kwak → Kwik → Kwek** 2. Semua hidup. Giliran **Kwak**: serang Kwik (paling berbahaya). Lempar dadu → **5** (gagal, butuh 1–2). Tidak ada yang mati. 3. Giliran **Kwik**: serang Kwek (satu-satunya lawan berbahaya setelah Kwak). **100% berhasil** → **Kwek mati!** 4. Sisa: Kwik vs Kwak. Giliran **Kwek** → dilewat (sudah mati). 5. Giliran **Kwak**: serang Kwik. Lempar → **2** (berhasil!) → **Kwik mati!** 6. **Pemenang: Kwak** ✓ (catat di tabel) *Catat hasil di tabel:* | Iterasi | Urutan (dadu) | Pemenang | |---------|--------------|----------| | 1 | 3 (Kwak,Kwik,Kwek) | Kwak | | 2 | ... | ... | | ... | ... | ... | **Langkah 4 — Ulangi minimal 12–20 kali**, lalu hitung frekuensi: - Peluang Kwik ≈ (jumlah menang Kwik) / total iterasi - Peluang Kwak ≈ (jumlah menang Kwak) / total iterasi - Peluang Kwek ≈ (jumlah menang Kwek) / total iterasi **Tips manual:** - Dengan 18 iterasi (kelipatan 6), setiap urutan giliran muncul tepat 3 kali → sampel seimbang. - Dengan 12–20 iterasi sudah cukup melihat tren: tidak ada yang mendekati 50%. - Semakin banyak iterasi → semakin akurat (hukum bilangan besar). **Hasil simulasi besar (500.000 iterasi komputer sebagai acuan):** - **Kwik: 38,3%** - **Kwak: 33,8%** - **Kwek: 28,0%** **Jawaban:** **TIDAK ADA** --- ### 3 — Permainan Papan (OSNK 2022 #12 modified) Papan 11 posisi (0–10). Kwak di posisi 1 (kiri), Kwek di posisi 9 (kanan). Gap awal = 8. **Aturan:** Pada setiap giliran, pemain dapat bergerak 1 langkah ke kiri, atau 1–2 langkah ke kanan. Pemain tidak boleh berada di posisi yang sama atau melompati lawan (urutan relatif tetap: Kwak kiri, Kwek kanan). Kwak mulai lebih dulu. Pemain yang tidak bisa bergerak kalah. **Analisis retrograde (110 state, Kwak jalan pertama):** Kwak menang dari posisi awal (1,9). Strategi optimal: Kwak mundur ke posisi 0, memaksa Kwek maju (mengecilkan gap). Pola berulang: | Giliran | Kwak | Kwek | Gap | Langkah | |:---:|:---:|:---:|:---:|---| | 1 | 1→0 | 9 | 9 | Kwak mundur | | 2 | 0 | 9→8 | 8 | Kwek terpaksa maju | | 3 | 0→1 | 8 | 7 | Kwak maju | | 4 | 1 | 8→7 | 6 | Kwek terpaksa maju | | ... | ... | ... | ... | gap menyusut 2 setiap 2 giliran | | akhir | 0 | 2 | 2 | Kwak ke-1, Kwek tidak bisa ke-1 | Di akhir: Kwak=0, Kwek=2, gap=2. Kwak pindah ke 1. Kwek di posisi 2 hanya bisa ke 3 atau 4 (keduanya posisi menang Kwak). Kwek tidak punya langkah yang menyelamatkan. **Jawaban:** **KWAK** --- ### 4 — Permainan Pizza (OSNK 2024 #3 modified) **Soal:** 4 pizza: Tuna(8), Keju(4), Jagung(3), Sayur(8). Kwak tidak suka keju, Kwik tidak suka tuna. Bergantian mengambil 1 potong, **Kwak mulai**. Berhenti jika tidak ada pizza yang disukai tersisa (teman tetap bisa lanjut). Maksimum potong untuk Kwak? **Analisis:** Klasifikasi pizza menurut siapa yang bisa makan: | Pizza | Potong | Kwak | Kwik | Verdict | |:------:|:------:|:----:|:----:|:-------:| | Tuna | 8 | ✓ | ✗ | **Kwak-only** | | Keju | 4 | ✗ | ✓ | **Kwik-only** | | Jagung | 3 | ✓ | ✓ | **Kontes** | | Sayur | 8 | ✓ | ✓ | **Kontes** | **Strategi optimal:** Kedua pemain selalu mengambil dari pizza **kontes** (Jagung/Sayur) selama masih ada. Mengambil dari kontes sekaligus memperbanyak diri sendiri dan mengurangi lawan. **Fase 1 — Pizza Kontes (J+S = 11 potong, Kwak mulai):** Giliran bergantian di Jagung lalu Sayur: | Giliran | Pemain | Aksi | Sisa J | Sisa S | |:--------:|:------:|------|:------:|:------:| | 1 | Kwak | Jagung | 2 | 8 | | 2 | Kwik | Jagung | 1 | 8 | | 3 | Kwak | Jagung | 0 | 8 | | 4 | Kwik | Sayur | 0 | 7 | | 5 | Kwak | Sayur | 0 | 6 | | 6 | Kwik | Sayur | 0 | 5 | | 7 | Kwak | Sayur | 0 | 4 | | 8 | Kwik | Sayur | 0 | 3 | | 9 | Kwak | Sayur | 0 | 2 | | 10 | Kwik | Sayur | 0 | 1 | | 11 | Kwak | Sayur | 0 | 0 | Hasil fase 1: **Kwak = 6** (2 jagung + 4 sayur), **Kwik = 5** (1 jagung + 4 sayur) **Fase 2 — Pizza Sendiri (kontes habis):** Sekarang Kwak hanya bisa ambil Tuna, Kwik hanya Keju. Giliran tetap bergantian: | Giliran | Pemain | Aksi | Sisa T | Sisa K | |:--------:|:------:|------|:------:|:------:| | 12 | Kwik | Keju | 8 | 3 | | 13 | Kwak | Tuna | 7 | 3 | | 14 | Kwik | Keju | 7 | 2 | | 15 | Kwak | Tuna | 6 | 2 | | 16 | Kwik | Keju | 6 | 1 | | 17 | Kwak | Tuna | 5 | 1 | | 18 | Kwik | Keju | 5 | **0** → Kwik berhenti! | | 19–23 | Kwak | Tuna ×5 | **0** | 0 | Setelah Kwik berhenti (Keju habis), Kwak terus makan Tuna sendirian sampai habis. Hasil fase 2: **Kwak = 8** (semua Tuna), **Kwik = 4** (semua Keju) **Total:** Kwak = 6 + 8 = **14**, Kwik = 5 + 4 = 9 **Rumus umum:** Kwak mendapat semua Tuna (tidak bisa disentuh Kwik) + ⌈(J+S)/2⌉ dari kontes (karena mulai lebih dulu). Kwakₘₐₖₛ = T + ⌈(J+S)/2⌉ = 8 + ⌈11/2⌉ = 8 + 6 = **14** **Jawaban:** **14** --- ### 5 — Mengambil Daun / Nim (OSNK 2024 #9) Nim dengan 2 tumpukan: A = 2, B = 3. Normal play (pengambil terakhir menang). **Teorema Nim (Sprague-Grundy):** Posisi kalah (losing position) iff XOR semua tumpukan = 0. A ⊕ B = 2 ⊕ 3 = 1 ≠ 0 → posisi menang bagi pemain saat ini (Pak Dengklek). **Langkah menang:** buat A ⊕ B = 0. Cari langkah yang menghasilkan XOR = 0. - Ambil 1 dari A: A'=1, 1 ⊕ 3 = 2 ≠ 0 ✗ - Ambil 2 dari A: A'=0, 0 ⊕ 3 = 3 ≠ 0 ✗ - Ambil 1 dari B: B'=2, 2 ⊕ 2 = 0 ✓ - Ambil 2 dari B: B'=1, 2 ⊕ 1 = 3 ≠ 0 ✗ - Ambil 3 dari B: B'=0, 2 ⊕ 0 = 2 ≠ 0 ✗ **Jawaban:** **C. Ambil 1 dari B** --- ### 6 — Random Walk Ruangan (KSNK 2021 #14) **Soal:** Pak Dengklek di ruangan **S**. Bergerak acak ke tetangga. Sampai **W** = menang, sampai **L** = kalah. Berapa peluang menang dari S? **Graf (13 node, dari gambar soal):** | Node | Label | Derajat | Tetangga | |:----:|:-----:|:-------:|----------| | 0 | **W** | 1 | A | | 1 | A | 3 | W, B, C | | 2 | B | 3 | A, lB, D | | 3 | lB | 1 | B (daun) | | 4 | C | 3 | A, L, E | | 5 | **L** | 1 | C | | 6 | D | 3 | B, lD, F | | 7 | lD | 1 | D (daun) | | 8 | E | 3 | C, lE, G | | 9 | lE | 2 | E, G | | 10 | G | 3 | E, lE, F | | 11 | F | 3 | D, G, S | | 12 | **S** | 1 | F (start) | **Metode:** Susun sistem persamaan linear, selesaikan dengan substitusi bertahap. Misal p(X) = peluang mencapai W dari node X. Kondisi batas: **p(W) = 1**, **p(L) = 0**. **Langkah 1 — Sederhanakan node daun (derajat 1):** Node daun hanya punya 1 tetangga, jadi pasti bounce back: - `p(lB) = p(B)` (daun dari B) - `p(lD) = p(D)` (daun dari D) - `p(S) = p(F)` (start, hanya terhubung ke F) Artinya kita hanya perlu menyelesaikan: **A, B, C, D, E, G, F, lE** (8 variabel). **Langkah 2 — Susun persamaan untuk tiap node:** Untuk node dengan derajat d yang terhubung ke tetangga t₁,...,t_d: p(node) = Σ p(tᵢ) / d. Untuk node daun (bounce back), tetangganya termasuk dirinya sendiri: | Persamaan | Bentuk asli | Disederhanakan | |-----------|-------------|----------------| | (1) | p(A) = (1 + p(B) + p(C)) / 3 | 3a = 1 + b + c | | (2) | p(B) = (p(A) + p(B) + p(D)) / 3 | 2b = a + d | | (3) | p(C) = (p(A) + 0 + p(E)) / 3 | 3c = a + e | | (4) | p(D) = (p(B) + p(D) + p(F)) / 3 | 2d = b + f | | (5) | p(E) = (p(C) + p(lE) + p(G)) / 3 | 3e = c + lE + g | | (6) | p(lE) = (p(E) + p(G)) / 2 | 2·lE = e + g | | (7) | p(G) = (p(E) + p(lE) + p(F)) / 3 | 3g = e + lE + f | | (8) | p(F) = (p(D) + p(G) + p(F)) / 3 | 2f = d + g | (a = p(A), b = p(B), dst.) **Langkah 3 — Substitusi dari atas (dekat W/L):** **Dari (2):** d = 2b − a ... (2') **Dari (4):** f = 2d − b = 2(2b−a) − b = 3b − 2a ... (4') **Dari (8):** g = 2f − d = 2(3b−2a) − (2b−a) = 6b−4a−2b+a = **4b − 3a** ... (8') **Langkah 4 — Substitusi lE ke (7):** Dari (6): lE = (e + g) / 2 Substitusi ke (7): 3g = e + (e+g)/2 + f ``` 6g = 2e + e + g + 2f 5g = 3e + 2f ``` Substitusi f = 3b−2a, g = 4b−3a: ``` 5(4b − 3a) = 3e + 2(3b − 2a) 20b − 15a = 3e + 6b − 4a 14b − 11a = 3e ``` **e = (14b − 11a) / 3** ... (7') **Langkah 5 — Substitusi ke (3):** Dari (3): c = (a + e) / 3 = (a + (14b−11a)/3) / 3 = (3a + 14b − 11a) / 9 **c = (14b − 8a) / 9** ... (3') **Langkah 6 — Substitusi ke (1) untuk mendapatkan a:** Dari (1): 3a = 1 + b + c = 1 + b + (14b−8a)/9 ``` 27a = 9 + 9b + 14b − 8a 35a = 9 + 23b ``` **a = (9 + 23b) / 35** ... (1') **Langkah 7 — Gunakan persamaan terakhir (5) untuk mendapatkan b:** Dari (5): 3e = c + lE + g = c + (e+g)/2 + g ``` 6e = 2c + e + g + 2g 5e = 2c + 3g ``` Substitusi semua dalam b (menggunakan a = (9+23b)/35): Hitung masing-masing: - a = (9 + 23b)/35 - c = (14b − 8a)/9 = (14b − 8(9+23b)/35)/9 = (34b − 8)/35 - e = (14b − 11a)/3 = (14b − 11(9+23b)/35)/3 = (79b − 33)/35 - g = 4b − 3a = 4b − 3(9+23b)/35 = (71b − 27)/35 Substitusi ke 5e = 2c + 3g (kalikan kedua ruang 35): ``` 5(79b − 33) = 2(34b − 8) + 3(71b − 27) 395b − 165 = 68b − 16 + 213b − 81 395b − 165 = 281b − 97 114b = 68 b = 68/114 = 34/57 ``` **Langkah 8 — Hitung f = p(S):** f = 3b − 2a = 3·(34/57) − 2·(9 + 23·34/57)/35 Hitung a terlebih dahulu: ``` a = (9 + 23·34/57)/35 = (9 + 782/57)/35 = (513 + 782)/(57·35) = 1295/1995 = 37/57 ``` Hitung f: ``` f = 3·(34/57) − 2·(37/57) = (102 − 74)/57 = 28/57 ``` **Hasil akhir:** **p(S) = p(F) = 28/57 ≈ 0,4912** (Peluang kalah dari S = 1 − 28/57 = 29/57 ≈ 0,5088) **Jawaban:** **28/57** (**0,491** dan **0.49** juga dibenarkan) --- ### 7 — Simulasi Lift (OSNK 2023 #15) Basuki di lantai 7, ingin ke lantai 1. Lift memprioritaskan tujuan terdekat. Jarak antar lantai = 3 meter. Penumpang: lantai 6→7, lantai 5→1, lantai 4→7, lantai 3→4, lantai 2→4. **Simulasi langkah demi langkah:** Lift di lantai 7. Algoritma: lift selalu pergi ke lantai terdekat (baik tujuan penumpang di dalam maupun panggilan penumpang menunggu). Jika jarak sama, panggilan yang sudah terdaftar lebih dahulu diprioritaskan. 1. **7→6** (1 lantai, 3m). Ambil penumpang (tujuan: 7). Tujuan aktif: {7}. Panggilan: {5, 4, 3, 2}. 2. **6→5** (1 lantai, 3m). Dari lantai 6: tujuan {7} (jarak 1) dan panggilan {5} (jarak 1) sama-sama 1 lantai. Panggilan 5 sudah terdaftar sebelumnya → prioritas ke 5. Ambil penumpang (tujuan: 1). Tujuan aktif: {7, 1}. Panggilan: {4, 3, 2}. 3. **5→4** (1 lantai, 3m). Terdekat = panggilan 4 (jarak 1). Ambil penumpang (tujuan: 7). Tujuan aktif: {7, 1}. Panggilan: {3, 2}. 4. **4→3** (1 lantai, 3m). Terdekat = panggilan 3 (jarak 1). Ambil penumpang (tujuan: 4). Tujuan aktif: {7, 1, 4}. Panggilan: {2}. 5. **3→2** (1 lantai, 3m). Dari lantai 3: tujuan {4} (jarak 1) dan panggilan {2} (jarak 1) sama-sama 1 lantai. Panggilan 2 sudah terdaftar → prioritas ke 2. Ambil penumpang (tujuan: 4). Tujuan aktif: {7, 1, 4}. Panggilan: ∅. 6. **2→1** (1 lantai, 3m). Terdekat = tujuan 1 (jarak 1). Antar penumpang dari lantai 5. Tujuan aktif: {7, 4}. 7. **1→4** (3 lantai, 9m). Terdekat = tujuan 4 (jarak 3). Antar penumpang dari lantai 3 dan 2. Tujuan aktif: {7}. 8. **4→7** (3 lantai, 9m). Terdekat = tujuan 7 (jarak 3). Antar penumpang dari lantai 6 dan 4. Selesai. Total = 1+1+1+1+1+1+3+3 = 12 lantai × 3m = **36** meter **Jawaban:** **36** --- ### 8 — Pencarian Koin (OSNK 2025 #6) **Strategi:** Binary search pada rentang [1, 255]. Setiap langkah, Pak Dengklek bertanya ke bebek di tengah rentang yang masih mungkin. | Langkah | Rentang | Tengah | Jawaban | Rentang baru | |:---:|:---:|:---:|:---:|:---:| | 1 | [1, 255] | 128 | Barat | [1, 127] | | 2 | [1, 127] | 64 | Barat | [1, 63] | | 3 | [1, 63] | 32 | Timur | [33, 63] | | 4 | [33, 63] | 48 | Barat | [33, 47] | | 5 | [33, 47] | 40 | Timur | [41, 47] | | 6 | [41, 47] | **44** | **ditemukan!** | — | Setiap jawaban "Barat" memotong rentang menjadi setengah kiri (tidak termasuk tengah), "Timur" menjadi setengah kanan. **Jawaban:** **44** --- ### 9 — Menyimpan Kotak Kardus (OSNK 2025 #17) 10 kotak: 1, 1, 2, 2, 2, 3, 3, 4, 6, 8. Kotak lebih kecil bisa dimasukkan ke kotak lebih besar (selisih ≥ 1). Setiap kotak hanya boleh berisi 1 kotak lain. **Strategi:** Bentuk rantai bersarang (nesting chain) sepanjang mungkin. Kotak terluar saja yang terlihat. **Pembentukan rantai:** - Rantai 1: 1 → 2 → 3 → 4 → 6 → 8 (menggunakan 1, 2, 3, 4, 6, 8) - Kotak tersisa: 1, 2, 2, 3 - Rantai 2: 1 → 2 → 3 (menggunakan 1, 2, 3) - Kotak tersisa: 2 - Rantai 2 perlu selisih ≥ 1: 1→2✓, 2→3✓. ✓ - Tersisa: 2 (tidak bisa dimasukkan ke mana pun karena rantai terluar lain ukuran 3 dan 8, dan 2 < 3 tapi 3-2=1≥1, jadi bisa masukkan 2 ke dalam 3? Tidak, 3 sudah berisi 2. Setiap kotak hanya boleh berisi 1.) Atau optimasi lain: - Rantai 1: 1 → 2 → 3 → 4 → 6 → 8 (terlihat: kotak 8) - Rantai 2: 1 → 2 → 3 (terlihat: kotak 3) - Tersisa: 2 (terlihat: kotak 2) Total terlihat = 3 (kotak 8, kotak 3, kotak 2). **Verifikasi ini optimal?** 10 kotak, 3 rantai: 6+3+1 = 10 ✓. Apakah bisa 2 rantai? Harus ada rantai sepanjang ≥ 5 dan rantai ≥ 5 (5+5=10). Tapi kotak tersedia: 1,1,2,2,2,3,3,4,6,8. Rantai terpanjang dimulai dari 1: 1→2→3→4→6→8 = 6. Sisa: 1,2,2,3. Rantai: 1→2→3 = 3. Sisa: 2. Total rantai = 3. Tidak bisa 2. **Jawaban:** **3** --- ### 10 — Menyimpan Kotak Benar/Salah (OSNK 2025 #18) Jika semua kotak memiliki ukuran berbeda, kita bisa menyusun rantai bersarang: kotak terkecil di dalam kotak kedua terkecil, di dalam kotak ketiga terkecil, dst. Setiap pasangan berurutan memiliki selisih ≥ 1 (karena ukurannya berbeda dan ukuran adalah bilangan bulat, maka selisih minimal 1). Hanya kotak terluar (terbesar) yang terlihat. **Jawaban:** **BENAR** --- ### 11 — Menyimpan Kotak Kardus (OSNK 2025 #19) 60 kotak dengan 7 ukuran berbeda. Kotak kecil bisa masuk ke kotak besar (sisi dalam < sisi luar). **Strategi greedy optimal:** urutkan kotak dari kecil ke besar, setiap kotak masuk ke rantai nesting yang paling kiri yang muat (ujung rantai < ukuran kotak). Jumlah rantai = jumlah kotak terlihat. | Ukuran | Jumlah | Rantai sebelum | Ditambah | Rantai sesudah | |:---:|:---:|:---:|:---:|:---:| | 2 | 4 | 0 | 4 | **4** | | 3 | 9 | 4 | 5 | **9** | | 5 | 15 | 9 | 6 | **15** | | 8 | 3 | 15 | 0 | **15** | | 13 | 12 | 15 | 0 | **15** | | 21 | 6 | 15 | 0 | **15** | | 34 | 11 | 15 | 0 | **15** | Puncak rantai terjadi setelah memproses ukuran 5: 4+9+15 = 28 kotak hanya bisa didistribusi ke 3 level ukuran (2,3,5), sehingga butuh minimal **15** rantai. Ukuran 8+ cukup sedikit sehingga semua masuk ke rantai yang sudah ada. **Jawaban:** **15** --- ### 12 — Mengangkut Bebek Bagian (a) (OSNP 2022 B2) 3 bebek dengan bobot B_{1}=2, B_{2}=2, B_{3}=3. Kandang kapasitas P_{1}=4 (mampu menampung 4 bebek), biaya C_{1}=5 per kg. Semua 3 bebek muat (3 ≤ 4). Total berat = 2+2+3 = 7 kg. Biaya = 7 × 5 = **35** **Jawaban:** **35** ### 13 — Mengangkut Bebek Bagian (b) (OSNP 2022 B2) Tiga kandang, kapasitas masing-masing 3, biaya C_{1}=5, C_{2}=2, C_{3}=3 per kg. 7 bebek masing-masing berat 5 kg. Kapasitas kandang menyatakan **banyaknya bebek** (bukan total berat). Jadi setiap kandang muat 3 bebek. Strategi: isi kandang termurah terlebih dahulu. - Kandang 2 (biaya 2/kg): 3 bebek × 5 kg × 2 = **30** - Kandang 3 (biaya 3/kg): 3 bebek × 5 kg × 3 = **45** - Kandang 1 (biaya 5/kg): 1 bebek × 5 kg × 5 = **25** Total = 30 + 45 + 25 = **100** **Jawaban:** **100** --- ### 14 — Tebas Tebang Bambu Pilihan Ganda (OSNP 2025 E1) **Analisis tiap skenario** (K=0, min 3/ikat, semua sama panjang, harus jual seluruh): | Skenario | Frekuensi | Bisa jual semua? | Jumlah ikat | | -------- | --------- | --------------- | ----------- | | A | {1:2, 2:2, 3:2, 4:2, 5:2, 6:2, 7:2} | ❌ (semua < 3) | 0 | | B | {2:5, 3:5, 4:4} | ✅ (5+5+4) | 3 | | C | {5:4, 6:4, 7:4, 8:2} | ❌ (8 hanya 2) | 3 | | **D** | **{8:7, 7:7}** | **✅ (3+4, 3+4)** | **4** | | E | {1:3, 2:1, 3:3, 4:1, 5:3, 6:3} | ❌ (2 dan 4 hanya 1) | 4 | Skenario yang bisa menjual seluruh bambu: B (3 ikat) dan D (4 ikat). D menghasilkan ikat terbanyak. **Jawaban:** **D** --- ### 15 — Tebas Tebang Bambu Benar/Salah (OSNP 2025 E2) Pernyataan tersebut **BENAR**. Berikut adalah pembuktian logisnya melalui observasi *greedy*: Misalkan kamu sudah menemukan sebuah konfigurasi valid di mana seluruh bambu terjual dan panjangnya seragam dalam setiap ikat sesuai batasan $K$. Asumsikan dalam konfigurasi tersebut terdapat setidaknya satu ikat yang berisi $X$ bilah bambu, di mana $X \ge 2M$. Karena seluruh bambu dalam satu ikat yang sama sudah pasti memiliki panjang yang seragam, kamu bisa memecah ikat besar tersebut menjadi dua ikat yang lebih kecil: 1. Ikat pertama mengambil $M$ bilah bambu. 2. Ikat kedua mengambil sisa $X - M$ bilah bambu. Perhatikan bahwa karena $X \ge 2M$, maka sisa bambu untuk ikat kedua adalah $X - M \ge 2M - M \ge M$. Ini berarti **kedua ikat baru tersebut masing-masing memenuhi syarat minimal $M$ bilah bambu**. Keduanya juga otomatis valid karena panjang bambunya sudah terbukti seragam dan pangkasannya tidak melanggar syarat $K$ (aturan soal memperbolehkan dua ikat berbeda memiliki panjang yang sama). Dengan memecah satu ikat besar tersebut menjadi dua, total ikat bambu yang bisa kamu jual **bertambah satu**. Ini membuktikan sebuah kontradiksi: jika ada ikat yang berukuran $2M$ atau lebih, konfigurasi tersebut **belum menghasilkan jumlah ikat maksimum**. Untuk mendapatkan jumlah ikat yang paling maksimal, kamu harus terus memecah ikat bambu sampai tidak ada satupun ikat yang ukurannya mencapai $2M$. Oleh karena itu, pada konfigurasi yang memaksimumkan jumlah ikat, setiap ikat pasti akan selalu memiliki jumlah bambu di rentang $M$ hingga $2M - 1$ (dengan kata lain, selalu kurang dari $2M$). Observasi matematis seperti ini adalah kunci klasik untuk menyederhanakan *state* dalam memecahkan soal-soal algoritma atau *competitive programming*. --- ### 16 — Tebas Tebang Bambu Optimasi (OSNP 2025 E3) **Data:** 18 bambu: [1, 1, 3, 3, 4, 5, 6, 7, 8, 9, 9, 13, 13, 14, 14, 14, 15, 16] **K = 2** (maks potong 2 satuan), **M = 3** (minimal 3 batang/ikat). Harus jual **semua**. **Konsep:** Dalam setiap ikat, semua bambu harus sama panjang setelah dipotong. Syarat: max(h) − min(h) ≤ K (agar semua bisa dipotong ke tinggi yang sama). **Cluster analysis:** Celah antara 9 dan 13 (gap=4 > K=2), tidak bisa cross-cluster. - Cluster rendah (11): [1,1,3,3,4,5,6,7,8,9,9] - Cluster tinggi (7): [13,13,14,14,14,15,16] **Optimal partition** (exhaustive search verified): | Ikat | Bambu | Target | Range | | ---- | ----- | ------ | ----- | | 1 | {1,1,3,3} | 1 | 2 ✓ | | 2 | {4,5,6} | 4 | 2 ✓ | | 3 | {7,8,9,9} | 7 | 2 ✓ | | 4 | {13,13,14} | 13 | 1 ✓ | | 5 | {14,14,15,16} | 14 | 2 ✓ | Total: **5 ikat**, semua 18 bambu terpakai. > Solusi lama: 6 (salah, mengabaikan syarat "sama panjang dalam ikat") **Jawaban:** **5** --- ### 17 — Tebas Tebang Bambu Skenario (OSNP 2025 E1 lanjutan) Mengacu pada analisis soal 14 (E1), skenario yang menghasilkan ikat **terbanyak** adalah **D** (4 ikat dari {8:7, 7:7}). Meskipun secara ketat tidak ada skenario yang bisa menjual 100% bambu (sisa 2 batang di D), **D adalah pilihan terbaik** di antara semua opsi. **Jawaban:** **D** --- ### 18 — Tebas Tebang Bambu Benar/Salah (OSNP 2025 E2 lanjutan) **Pernyataan:** "Jika semua N bambu memiliki tinggi < 2M, maka tidak ada bundel yang bisa dijual." **Jawaban:** **SALAH** **Penjelasan:** Syarat membentuk bundel adalah: 1. Setiap bundel terdiri dari **≥ M bilah bambu** (syarat jumlah) 2. Semua bambu dalam satu bundel memiliki **panjang yang sama** (syarat keseragaman) 3. Setiap bambu boleh dipotong **maksimal K satuan** (syarat pemangkasan) Pernyataan soal bicara tentang **tinggi bambu < 2M** — ini adalah syarat tentang **panjang/tinggi individual**, bukan tentang jumlah bambu per bundel. Tinggi bambu tidak ada hubungannya langsung dengan kemampuan membentuk bundel. **Counterexample:** Misalkan **M = 3**, **K = 0** (tanpa pemangkasan), dan ada **6 bambu** masing-masing tingginya: ``` Bambu: [4, 4, 4, 5, 5, 5] ``` Semua tinggi < 2M = 6. Tapi: - Bundel 1: {4, 4, 4} → 3 bambu panjang 4 ✓ (≥ M=3) - Bundel 2: {5, 5, 5} → 3 bambu panjang 5 ✓ (≥ M=3) Jadi **2 bundel bisa dijual**, padahal semua tinggi < 2M. **Pernyataan SALAH.** **Contoh lebih sederhana:** M = 3, 3 bambu masing-masing tinggi **1** (semua < 2M = 6). Bundel {1, 1, 1} → 3 bambu panjang 1. **Valid!** Tidak perlu dipotong sama sekali. **Intuisi:** Pernyataan ini mencoba menipu dengan mencampuradukkan "tinggi bambu" dengan "jumlah bambu per bundel". Syarat M berkaitan dengan **jumlah bambu per bundel**, bukan tinggi bambu. Selama ada ≥ M bambu yang bisa disamakan panjangnya (dengan pemangkasan ≤ K), bundel bisa terbentuk — terlepas dari berapa tinggi bambunya. --- ### 19 — Tebas Tebang Bambu Optimasi (OSNP 2025 E3 praktik) **Data:** 18 bambu: [1, 1, 3, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16] **K = 2** (maks potong 2 satuan), **M = 3** (minimal 3 batang/bundel). Harus jual **semua**. Perbedaan dari soal 16: data lebih **merata** — celah antar cluster lebih kecil (tidak ada lompatan 9→13), sehingga memungkinkan lebih banyak bundel. **Optimal partition:** | Bundel | Bambu | Target | Range | | ------ | ----- | ------ | ----- | | 1 | {1, 1, 3} | 1 | 2 ✓ | | 2 | {3, 4, 5} | 3 | 2 ✓ | | 3 | {6, 7, 8} | 6 | 2 ✓ | | 4 | {9, 9, 10} | 9 | 1 ✓ | | 5 | {11, 12, 13} | 11 | 2 ✓ | | 6 | {14, 15, 16} | 14 | 2 ✓ | Total: **6 bundel**, semua 18 bambu terpakai. Bandingkan dengan soal 16 (jawaban 5): di sini tidak ada celah besar antara cluster, sehingga bambu bisa dikelompokkan lebih efisien menjadi 6 bundel. **Jawaban:** **6** --- ### 20 — Penukaran Koin (OSP 2019 #6) **Jawaban: 3** Koin yang ada: **{1, 7, 23}**. Tambah tepat 1 koin baru *c* dengan 2 ≤ *c* ≤ 30, *c* ∉ {1,7,23}, sehingga sistem koin tetap **kanonik** (greedy selalu menghasilkan jumlah koin minimum). **Mengapa sebuah koin baru bisa gagal?** Greedy selalu memilih koin **terbesar** yang ≤ sisa uang. Koin baru *c* gagal jika ada suatu nilai *V* di mana: - **Greedy:** ambil *c* (atau koin besar lain), lalu banyak koin kecil → total *X* koin - **Optimal:** lewati *c*, pakai kombinasi koin lain → total *Y* koin dengan *Y < X* Ini terjadi ketika koin baru *c* berada di posisi yang membuat greedy "salah arah" — mengambil koin yang terlalu besar, lalu terjebak mengisi sisa dengan koin 1. **Contoh konkret mekanisme kegagalan:** **c = 5** → Sistem {1, 5, 7, 23} ``` Nilai 10: greedy → 7 + 1 + 1 + 1 = 4 koin (ambil 7 dulu, sisa 3 diisi 1×3) optimal → 5 + 5 = 2 koin (pakai koin baru 2×, lebih efisien!) ``` Greedy mengambil 7 (koin terbesar ≤ 10), padahal 5+5 jauh lebih baik. **GAGAL.** **c = 8** → Sistem {1, 7, 8, 23} ``` Nilai 14: greedy → 8 + 1×6 = 7 koin (ambil 8 dulu, sisa 6 diisi 1×6) optimal → 7 + 7 = 2 koin (7+7 sempurna!) ``` Greedy memilih 8 (terbesar ≤ 14), padahal 7+7 jauh lebih baik. **GAGAL.** **Pola umum kegagalan:** | Rentang c | Mengapa gagal | Nilai counter-example | |-----------|--------------|---------------------| | 5 | Greedy ambil 7, optimal pakai c×2 | V = 2c: greedy = 7+1×(2c−7), optimal = c+c | | 6 | Greedy ambil 7, optimal pakai c×2 | V = 12: greedy = 7+1×5, optimal = 6+6 | | 8–12 | Greedy ambil c, optimal pakai 7+7 | V = 14: greedy = c+1×(14−c), optimal = 7+7 | | 13 | Greedy ambil 23, optimal pakai c×2 | V = 26: greedy = 23+1×3, optimal = 13+13 | | 14–18 | Greedy ambil c, optimal pakai 7×3 | V = 21: greedy = c+1×(21−c), optimal = 7+7+7 | | 19 | Greedy ambil 23, optimal pakai 19+7 | V = 26: greedy = 23+1×3, optimal = 19+7 | | 20–27 | Greedy ambil 23, optimal pakai c+7 | V = c+7: greedy = 23+1×(c−16), optimal = c+7 | | 28–30 | Greedy ambil c, optimal pakai 23+7 atau 23×2 | V = 30 atau 46 | **Intuisi:** Setiap koin c ≥ 5 "mengganggu" keseimbangan greedy. Entah: 1. Greedy memilih 7 padahal c×2 lebih efisien (c kecil: 5,6) 2. Greedy memilih c padahal 7+7 atau 7×3 lebih efisien (c sedang: 8–18) 3. Greedy memilih 23 padahal c+7 atau c×2 lebih efisien (c besar: 19–30) **Mengapa c = 2, 3, 4 berhasil?** Koin-kecil (2, 3, 4) terlalu kecil untuk "menggoda" greedy keluar dari jalur optimal. Greedy tetap memilih 7 dan 23 di saat yang tepat, dan koin kecil hanya digunakan untuk "kembalian" yang tidak bisa dihindari. - **c = 2** ({1,2,7,23}): Semua kelipatan ditangani optimal. Misal V=14 → greedy=7+7=2 ✓. V=4 → greedy=2+2=2 ✓. - **c = 3** ({1,3,7,23}): V=6 → greedy=3+3=2 ✓. V=14 → 7+7=2 ✓. Tidak ada jebakan. - **c = 4** ({1,4,7,23}): V=8 → greedy=7+1=2 ✓ (optimal juga). V=14 → 7+7=2 ✓. Tidak ada jebakan. Untuk c=4, perhatikan bahwa V=8: greedy memilih 7 (bukan 4), sisa 1. Total 2 koin. Alternatif 4+4 juga 2 koin. Tie, bukan kegagalan. **Jawaban: 3** nilai koin baru yang mungkin: **{2, 3, 4}**.

Member	Answer
Yazid	D
Habibie	D
Kian	D
Algazel	D
Priscilla	D
Danish	B
Athar	B
Athmar	E
Quinna	-

Question 17 — Tebas Tebang Bambu 4

Question

Show Solution AI ▸

Answers (9 members)

Show Solution ^AI ▸