The Exam Scheduling Conflict
A school must schedule five exams: Maths, English, Irish, Science, and History. Each exam is 2 hours long. There are three exam halls: Hall 1 (capacity 100), Hall 2 (capacity 80), Hall 3 (capacity 60). The number of students taking each exam: Maths 90, English 70, Irish 50, Science 40, History 30. Exams cannot be in the same hall at the same time, and each hall can host only one exam at a time. The exams must be scheduled over three consecutive days, with two time slots per day: morning (9-11am) and afternoon (1-3pm). Each exam must be scheduled exactly once. Additionally, there are constraints: Maths and English cannot be on the same day because some students take both. Irish and History cannot be on the same day for the same reason. Science has no conflicts. Also, Hall 1 is unavailable on the first day due to maintenance. Determine if a valid schedule exists, and if so, provide one. If not, explain why.
1. List the exams with their student numbers and the halls with their capacities. Identify which halls can accommodate which exams based on capacity.
Read the worked answer
Exams and students: Maths 90, English 70, Irish 50, Science 40, History 30. Halls: Hall1=100, Hall2=80, Hall3=60. Capacity compatibility:
- Maths (90) needs capacity >=90: only Hall1 (100) works. Hall2=80 too small, Hall3=60 too small.
- English (70) needs capacity >=70: Hall1 (100) or Hall2 (80). Hall3=60 too small.
- Irish (50) needs capacity >=50: any hall (Hall1,2,3 all >=50).
- Science (40) needs capacity >=40: any hall.
- History (30) needs capacity >=30: any hall. So Maths must be in Hall1. English in Hall1 or Hall2. Others anywhere.
2. Considering the time slots, hall availability, and the conflict constraints, determine if a valid schedule exists. If yes, provide a schedule that satisfies all constraints. If no, explain why.
Read the worked answer
We have 3 days, 2 slots per day = 6 time slots total. 5 exams, so one slot will be empty. Hall1 unavailable on day1, so Hall1 can only be used on days 2 and 3. Maths requires Hall1, so Maths must be on day2 or day3. Conflict: Maths and English cannot be on the same day. So if Maths is on day2, English cannot be on day2; if Maths on day3, English not on day3. Irish and History cannot be on the same day. We need to assign each exam to a slot and a hall. Let's try to construct a schedule. Day1: Hall1 unavailable. Available halls: Hall2, Hall3. We can schedule exams that don't require Hall1 on day1. English could be on day1 in Hall2. Irish, Science, History could be on day1 in Hall2 or Hall3. But we must respect conflicts. Let's attempt: Day1 morning: English in Hall2 (capacity 80, fits 70). Day1 afternoon: Irish in Hall3 (capacity 60, fits 50). Day2 morning: Maths in Hall1 (capacity 100, fits 90). Day2 afternoon: Science in Hall2 (capacity 80, fits 40). Day3 morning: History in Hall3 (capacity 60, fits 30). Check conflicts: Maths (day2) and English (day1) are on different days, ok. Irish (day1) and History (day3) are on different days, ok. Hall usage: each hall used at most once per slot? We have only one exam per slot in this schedule, so no hall conflicts. Hall1 used only on day2, which is allowed. All exams scheduled. So a valid schedule exists. However, we must ensure that no two exams are in the same hall at the same time: we have only one exam per time slot, so it's fine. But we have 6 slots and 5 exams, so one slot empty. This schedule works. But wait: we have two exams on day1: English and Irish. They are in different slots (morning and afternoon) and different halls, so ok. Day2: Maths and Science, different slots, ok. Day3: History only. So valid.