Five Talks, Three Rooms, Three Slots
A college fest must place five talks - P, Q, R, S and T - into three rooms across three slots: 9:00, 11:00 and 2:00. Each room holds at most one talk per slot, and each talk occupies exactly one slot. R's speaker needs the only projector, which is in Room 1, so R must be in Room 1. S and T are by speakers who must leave on the same evening train, so they cannot share a slot. Q must be scheduled earlier than T, and Q's host has asked not to be put in Room 3. P's speaker must leave by 1:00, so P cannot be in the 2:00 slot. Room 3 is closed for maintenance at 9:00.
1. Construct one complete timetable that satisfies every constraint, and show the check.
Read the worked answer
One valid timetable:
| Slot | Room 1 | Room 2 | Room 3 |
|---|---|---|---|
| 9:00 | R | Q | closed |
| 11:00 | P | S | - |
| 2:00 | T | - | - |
Check against each constraint:
- R in Room 1 - yes, at 9:00.
- S and T in different slots - S at 11:00, T at 2:00. Satisfied.
- Q earlier than T - Q at 9:00, T at 2:00. Satisfied.
- Q not in Room 3 - Q is in Room 2. Satisfied.
- P not at 2:00 - P is at 11:00. Satisfied.
- Room 3 not used at 9:00 - it is not used at all. Satisfied.
- No room double-booked in a slot - each column has at most one entry per row. Satisfied.
Note how much slack remains: only three of the eight usable room-slots are needed beyond the five talks, so the puzzle is not tight. That is why several timetable variations exist, and why an answer that satisfies every constraint should be accepted without matching any particular published arrangement.
2. What is the earliest slot T can occupy, and what does pushing T that early force elsewhere?
Read the worked answer
Earliest slot for T is 11:00. T cannot be at 9:00, because Q must be scheduled earlier than T and nothing precedes the first slot of the day.
T at 11:00 is achievable, but it forces a chain of consequences:
- Q must then be at 9:00.
- R must be in Room 1, and Room 3 is closed at 9:00, so the 9:00 slot has exactly two usable rooms. R and Q therefore take Room 1 and Room 2 at 9:00 - there is no third place for either.
- P cannot be at 2:00, and 9:00 is now full, so P must be at 11:00.
- S cannot share a slot with T, so S cannot be at 11:00 and must be at 2:00.
Resulting timetable: 9:00 R (Room 1) and Q (Room 2); 11:00 T (Room 1) and P (Room 2); 2:00 S (Room 1). All constraints hold.
So the answer is 11:00, but it is not free: it consumes the only two usable 9:00 rooms and pushes S to the last slot. If S's speaker is the one with the tightest train, the organiser should keep T at 2:00 instead.
3. Room 3 is closed for the entire day. Can all five talks still be held? Justify your answer with a timetable or a proof that none exists.
Read the worked answer
Yes, all five can still be held. Two rooms across three slots give six places for five talks, and the constraints can be met:
| Slot | Room 1 | Room 2 |
|---|---|---|
| 9:00 | R | Q |
| 11:00 | P | S |
| 2:00 | T | - |
Check: R is in Room 1; Q (9:00) precedes T (2:00); S (11:00) and T (2:00) are in different slots; P is at 11:00, not 2:00; Q is in Room 2, not Room 3 - trivially satisfied since Room 3 is closed.
The reasoning worth stating is why the closure is survivable: capacity is six places against five talks, so there is one place of slack, and the tightest point is not the total but the 9:00 slot, where only two rooms exist at all. Two talks needing to be at 9:00 is therefore the real limit. If a further condition forced three talks into 9:00 - for instance if both R and Q were fixed at 9:00 and P also could not move - the day would become infeasible, and the organiser would have to relax a constraint rather than add a room.