Programming Four Conference Talks
Four speakers - Ines, Karim, Luca and Mira - each give exactly one talk at a one-day conference, in four consecutive slots numbered 1 to 4, one speaker per slot. The organiser's constraints are: Karim's talk comes before Luca's; Mira's talk is not in a slot immediately before or immediately after Luca's; Ines speaks in slot 3; and Luca does not speak in slot 4. Every constraint must hold simultaneously, and the programme goes to the printer before the venue's deadline, so no slot may be left provisional.
1. Which speaker occupies slot 4? Show that the answer is forced rather than merely consistent.
Read the worked answer
With Ines fixed in slot 3, slots 1, 2 and 4 hold Karim, Luca and Mira.
Where can Luca go? Not slot 4 (given), and not slot 1 - Karim must precede Luca, and nothing precedes slot 1. So Luca is in slot 2.
Where can Mira go? Slots 1 and 4 remain, one of which is Karim's. Mira cannot be in slot 1, because slot 1 is immediately before Luca in slot 2. So Mira is in slot 4.
Karim then takes slot 1, which satisfies 'Karim before Luca'.
Programme: 1 Karim, 2 Luca, 3 Ines, 4 Mira.
Check: Karim (1) before Luca (2) ✓; Mira (4) is two slots from Luca (2), not adjacent ✓; Ines (3) ✓; Luca not in 4 ✓.
The answer is forced because each step eliminated all alternatives; there is exactly one solution, so it cannot be otherwise.
2. If the constraint 'Luca does not speak in slot 4' were dropped, how many programmes would satisfy the remaining constraints? List them.
Read the worked answer
Keep: Karim before Luca; Mira not adjacent to Luca; Ines in slot 3.
With Ines in slot 3, the other three fill slots 1, 2, 4.
Case Luca in slot 2: Karim must be in slot 1; Mira in slot 4. Mira (4) and Luca (2) are not adjacent ✓ → K1, L2, I3, M4.
Case Luca in slot 4: Karim is in slot 1 or 2, Mira takes the other.
- K1, M2, I3, L4: Mira (2) and Luca (4) are not adjacent ✓
- M1, K2, I3, L4: Mira (1) and Luca (4) are not adjacent ✓
Case Luca in slot 1: impossible - Karim cannot precede slot 1.
Total: 3 programmes. Removing one constraint multiplied the solutions from 1 to 3, and in each of the two new ones Luca sits in slot 4 - which is exactly the configuration the dropped constraint was there to forbid.
3. The venue now offers a different slot: suppose Ines is moved to slot 2 instead of slot 3, with all the other constraints unchanged. What programme results?
Read the worked answer
Slots 1, 3 and 4 now hold Karim, Luca and Mira.
Where can Luca go?
- Slot 4: forbidden by the stated constraint.
- Slot 1: impossible, since Karim must speak before Luca and nothing precedes slot 1.
- So Luca must be in slot 3.
Consequences: Karim must be before slot 3, and slot 2 is taken by Ines, so Karim is in slot 1 and Mira is in slot 4.
Check: Mira in slot 4 is immediately after Luca in slot 3 - this violates 'Mira is not adjacent to Luca'.
Result: no valid programme exists. The constraints are mutually inconsistent under the new premise, so the organiser cannot simply move Ines; she must renegotiate either the adjacency rule or the ban on Luca speaking last.
The method is the same as before - propagate from the most restricted item - but the deliverable changes: here the correct output is a proof of infeasibility, not a schedule.