Penjadwalan Lima Finalis dengan Empat Batasan
Panitia Olimpiade Sekolah Menengah "Cendekia" harus menjadwalkan presentasi lima finalis-Ayu, Bima, Citra, Danu, dan Eka-pada lima slot berurutan, slot 1 sampai slot 5. Setiap siswa menempati tepat satu slot. Panitia menetapkan aturan berikut. Eka harus tampil paling awal karena sudah harus mengikuti seleksi kabupaten pada siang hari. Bima menolak tampil pada slot pertama dan slot terakhir karena harus mendampingi ibunya ke rumah sakit. Citra harus tampil tepat sebelum Danu agar keduanya bisa memakai satu berkas slide yang sama. Ayu baru bisa hadir setelah pukul 10.00, sehingga ia harus tampil setelah Danu. Istirahat resmi dijadwalkan setelah slot kedua. Juri menilai dengan rubrik yang sama untuk semua peserta, dan durasi tiap presentasi 8 menit. Ketua panitia mengeluh bahwa ia sudah mencoba tiga susunan, tetapi selalu ada aturan yang dilanggar. Ia meminta kamu memeriksa apakah ada susunan yang memenuhi semua aturan, dan fakta apa yang sebenarnya sudah pasti.
1. Tentukan semua susunan urutan tampil yang memenuhi seluruh aturan. Tunjukkan langkah deduksinya, bukan hanya hasil akhir.
Read the worked answer
Langkah 1. Eka harus paling awal, jadi slot 1 = Eka. Sisa slot 2–5 untuk Ayu, Bima, Citra, Danu.
Langkah 2. Syarat "Citra tepat sebelum Danu" hanya mungkin untuk pasangan slot (2,3), (3,4), atau (4,5).
- Pasangan (4,5): Ayu harus tampil setelah Danu, padahal tidak ada slot setelah 5 → gugur.
- Pasangan (2,3): sisa slot 4 dan 5 untuk Bima dan Ayu. Bima tidak boleh di slot 5, jadi Bima = 4, Ayu = 5. Susunan: Eka–Citra–Danu–Bima–Ayu.
- Pasangan (3,4): sisa slot 2 dan 5. Bima tidak boleh di slot 5, jadi Bima = 2, Ayu = 5. Susunan: Eka–Bima–Citra–Danu–Ayu.
Jadi hanya ada dua susunan sah. Perhatikan bahwa istirahat setelah slot 2 tidak membatasi siapa pun, sehingga tidak mengurangi jumlah susunan.
2. Manakah pernyataan berikut yang pasti benar untuk semua susunan yang sah: (i) Bima tampil pada slot 2; (ii) Ayu tampil pada slot 5; (iii) Danu tampil pada slot 4; (iv) Citra tampil pada slot 3? Jelaskan.
Read the worked answer
Bandingkan kedua susunan sah: E–C–D–B–A dan E–B–C–D–A.
- (i) salah: Bima ada di slot 4 pada susunan pertama, slot 2 pada susunan kedua.
- (ii) benar: Ayu berada di slot 5 pada kedua susunan. Ini bukan kebetulan; karena Eka mengunci slot 1 dan pasangan Citra–Danu menyisakan tepat satu slot di ujung untuk Ayu agar ia tampil setelah Danu.
- (iii) salah: Danu di slot 3 atau 4.
- (iv) salah: Citra di slot 2 atau 3.
Jawaban: hanya (ii). Yang bisa disimpulkan sebagai kemungkinan (bukan kepastian) adalah Bima di {2,4}, Citra di {2,3}, Danu di {3,4}.
3. Ketua panitia menambahkan syarat baru: Danu harus tampil tepat setelah istirahat, yaitu pada slot 3. Tentukan susunannya dan jelaskan mengapa syarat itu membuat susunan menjadi tunggal.
Read the worked answer
Syarat baru mengunci Danu = slot 3. Karena Citra tepat sebelum Danu, Citra = slot 2. Ini langsung memilih cabang pasangan (2,3) dan membuang cabang (3,4).
Sisa slot 4 dan 5 untuk Bima dan Ayu. Bima dilarang di slot terakhir, jadi Bima = 4 dan Ayu = 5. Susunan tunggal: Eka–Citra–Danu–Bima–Ayu.
Alasannya: sebelumnya ada dua derajat kebebasan (posisi pasangan Citra–Danu dan posisi Bima). Syarat Danu = 3 menghapus kebebasan pertama, sedangkan larangan Bima di slot 1 dan 5 sudah menghapus kebebasan kedua sejak awal. Dua pengunci untuk dua kebebasan menghasilkan satu solusi.