Scheduling Six Village Inspections Under Conflicting Constraints
A Sub-Divisional Magistrate must inspect six villages - Rampur, Saho, Bhano, Talwara, Kotla and Dharamkot - over five working days, Monday to Friday. Exactly one day will carry two inspections; every other day will carry one. Saho must be inspected on the same day as Rampur or on the day immediately after Rampur. Bhano cannot be on Monday. Talwara must fall earlier in the week than Kotla. Dharamkot must be on Friday, and Rampur cannot be on Thursday. The clerk submits a draft: Monday - Rampur and Saho; Tuesday - Bhano; Wednesday - Talwara; Thursday - Kotla; Friday - Dharamkot. The SDM then says that if Dharamkot has to be shifted to Thursday for a meeting, the plan must be redone with the fewest possible changes.
1. Is the clerk's draft valid? Check it constraint by constraint.
Read the worked answer
Walk through the five conditions:
- Double day: only Monday carries two; all other days carry one. Satisfied.
- Saho with or immediately after Rampur: both on Monday, same day. Satisfied.
- Bhano not on Monday: Bhano is Tuesday. Satisfied.
- Talwara before Kotla: Wednesday before Thursday. Satisfied.
- Dharamkot on Friday; Rampur not on Thursday: both hold.
Every village appears exactly once: Rampur, Saho, Bhano, Talwara, Kotla, Dharamkot - six villages, six slots. The draft is valid and can be issued as it stands.
2. Dharamkot must now move to Thursday. What is the minimum-change revision, and is it valid?
Read the worked answer
Swap Kotla and Dharamkot between Thursday and Friday, and change nothing else:
- Monday - Rampur, Saho
- Tuesday - Bhano
- Wednesday - Talwara
- Thursday - Dharamkot
- Friday - Kotla
The only constraint touched is the Talwara–Kotla ordering, and it still holds because Wednesday precedes Friday. Dharamkot is now Thursday as required, Rampur is still not on Thursday, Bhano is still not on Monday, and the double day is still Monday. One swap is the minimum possible, since Dharamkot's move alone would leave two villages on Thursday and none on Friday.
3. The SDM now wants the double inspection on Friday, covering Dharamkot and Kotla. Is that compatible with all the original constraints?
Read the worked answer
Yes, and it is worth showing that more than one schedule works, so the SDM has options.
With Dharamkot and Kotla both on Friday, the remaining four villages occupy Monday to Thursday one per day. Bhano cannot be Monday and Talwara only has to precede Kotla, which is now Friday - so Talwara is free. Rampur and Saho must be adjacent, with Rampur not on Thursday, giving three placements:
- Mon Rampur, Tue Saho, Wed Bhano, Thu Talwara
- Mon Talwara, Tue Rampur, Wed Saho, Thu Bhano
- Mon Talwara, Tue Bhano, Wed Rampur, Thu Saho
All three satisfy every constraint. Recommend the first, because it puts the paired inspections early in the week and leaves Thursday free for paperwork before the Friday double visit.