Penjadwalan Lima Sesi Debat dengan Tiga Kendala
Panitia lomba debat SMA Cendekia harus menjadwalkan lima sesi latihan dari Senin sampai Jumat, satu sesi per hari, tanpa hari kosong. Lima topik yang harus dijadwalkan adalah Ekonomi (E), Hukum (H), Lingkungan (L), Pendidikan (P), dan Teknologi (T). Koordinator akademik menetapkan tiga aturan yang tidak boleh dilanggar: (1) sesi Teknologi dijadwalkan tepat satu hari setelah sesi Ekonomi; (2) sesi Lingkungan tidak boleh diletakkan pada hari Senin maupun hari Jumat; (3) sesi Hukum harus lebih dahulu daripada sesi Pendidikan. Pelatih tim mengeluh bahwa aturan itu membuat sebagian topik nyaris terkunci, sementara dua anggota lain berpendapat bahwa variasi jadwal masih cukup banyak. Sebelum papan jadwal final dicetak, panitia ingin memastikan berapa banyak susunan yang sah dan apa yang bersifat pasti. Pembina kemudian menambahkan satu permintaan: panitia harus menyiapkan contoh jadwal untuk skenario sesi Ekonomi ditempatkan di hari Senin, agar bisa dibandingkan dengan skenario lain pada rapat berikutnya.
1. Susun semua kemungkinan jadwal bila sesi Ekonomi (E) ditempatkan pada hari Senin. Jelaskan langkah penyusunannya, bukan hanya hasil akhirnya.
Read the worked answer
Langkah 1 - kunci pasangan E–T. Aturan (1) menyatakan T tepat satu hari setelah E. Jika E hari Senin, maka T wajib hari Selasa.
Langkah 2 - tempatkan L. Aturan (2) melarang L di Senin dan Jumat, sehingga L hanya mungkin di Selasa, Rabu, atau Kamis. Selasa sudah dipakai T, jadi L ∈ {Rabu, Kamis}.
Langkah 3 - isi sisa hari dengan H dan P. Aturan (3) menuntut H lebih awal daripada P.
- Jika L = Rabu, sisa hari adalah Kamis dan Jumat. Satu-satunya penempatan yang memenuhi H sebelum P adalah H = Kamis, P = Jumat. Jadwal: E, T, L, H, P.
- Jika L = Kamis, sisa hari adalah Rabu dan Jumat. Maka H = Rabu, P = Jumat. Jadwal: E, T, H, L, P.
Kesimpulan: ada tepat dua susunan sah untuk skenario E di hari Senin. Perhatikan bahwa pilihan L = Selasa tidak pernah muncul karena hari itu sudah terpakai oleh T - inilah yang membuat jumlah kemungkinan lebih kecil daripada dugaan awal panitia.
2. Seorang anggota menyatakan: "Sesi Pendidikan dapat dijadwalkan paling cepat hari Selasa, dan bila itu terjadi maka sesi Hukum pasti menempati hari Senin." Nilai pernyataan itu secara keseluruhan.
Read the worked answer
Bagian pertama - benar. P tidak mungkin di hari Senin, sebab aturan (3) menuntut H lebih awal daripada P, dan tidak ada hari sebelum Senin. Jadi hari tercepat untuk P memang Selasa.
Bagian kedua - juga benar, dan dapat dibuktikan. Andaikan P = Selasa. Maka H harus Senin, sehingga tiga hari tersisa (Rabu, Kamis, Jumat) diisi E, T, dan L.
- Pasangan (E, T) = (Rabu, Kamis) menyisakan Jumat untuk L - melanggar aturan (2).
- Pasangan (E, T) = (Kamis, Jumat) menyisakan Rabu untuk L - sah.
Jadi P = Selasa memaksa jadwal H, P, L, E, T. Tidak ada susunan lain yang mungkin.
Penilaian: pernyataan itu benar seluruhnya. Yang membuatnya benar bukan hafalan, melainkan pemeriksaan rantai kendala: posisi P menentukan posisi H, lalu menyisakan satu-satunya pasangan E–T yang sah. Jika salah satu aturan dihapus, misalnya larangan L di hari Jumat, kesimpulan ini akan runtuh.
3. Berapa banyak susunan sah secara keseluruhan? Tunjukkan cara menghitungnya secara sistematis dan simpulkan apakah keluhan pelatih beralasan.
Read the worked answer
Cara paling aman adalah mengelompokkan berdasarkan posisi E, karena E menentukan T.
| Posisi E | Posisi T | Kemungkinan L | Sisa untuk H, P | Jumlah |
|---|---|---|---|---|
| Senin | Selasa | Rabu, Kamis | 2 penempatan | 2 |
| Selasa | Rabu | Kamis (wajib) | H = Senin, P = Jumat | 1 |
| Rabu | Kamis | Selasa (wajib) | H = Senin, P = Jumat | 1 |
| Kamis | Jumat | Selasa atau Rabu | 2 penempatan | 2 |
Untuk E = Kamis, keduanya sah: L = Selasa memberi H = Senin, P = Rabu; L = Rabu memberi H = Senin, P = Selasa. Keduanya memenuhi H sebelum P.
Total = 2 + 1 + 1 + 2 = 6 susunan sah.
Kesimpulan: keluhan pelatih sebagian beralasan. Dari 5! = 120 urutan bebas, hanya 6 yang bertahan, jadi ruang gerak panitia memang sempit. Namun jadwal tidak sepenuhnya terkunci: masih ada enam variasi, dan satu di antaranya dapat dipilih sesuai ketersediaan ruang atau pembicara.