Duty Roster Under Conflicting Constraints
A cadet squadron must fill three nightly duties - gate sentry, armoury check, and study hall supervisor - for four nights, Monday to Thursday. Four cadets are available: Ayesha, Bilal, Chenab, and Danish. Constraints: no cadet may do more than three duties in total; Ayesha cannot do gate sentry; Bilal must do armoury check if Danish does study hall; Chenab is unavailable on Tuesday; Danish must do at least one duty before Wednesday; each night must have exactly one cadet on each duty, and no cadet may hold two duties on the same night. The duty officer drafts: Monday Ayesha-study, Bilal-gate, Danish-armoury; Tuesday Chenab-study, Ayesha-gate, Danish-armoury; Wednesday Bilal-study, Chenab-gate, Ayesha-armoury; Thursday Danish-study, Bilal-gate, Chenab-armoury.
1. List every violation in the duty officer's draft. Check constraints, not just the obvious names.
Read the worked answer
The draft has three violations:
- Ayesha is on gate sentry on Tuesday. The constraint says Ayesha cannot do gate sentry.
- Chenab is on study hall on Tuesday. Chenab is unavailable on Tuesday.
- Danish is on study hall on Thursday, but Bilal is on gate sentry that night. The rule says Bilal must do armoury check if Danish does study hall. Bilal is not on armoury, so the conditional rule is broken.
The total duty counts are otherwise balanced at three each: Ayesha (Mon study, Tue gate, Wed armoury), Bilal (Mon gate, Wed study, Thu gate), Chenab (Tue study, Wed gate, Thu armoury), Danish (Mon armoury, Tue armoury, Thu study). Danish also satisfies the before-Wednesday rule.
2. Construct a valid roster. Show it night by night and prove that it satisfies each constraint.
Read the worked answer
One valid roster:
| Night | Gate | Study hall | Armoury |
|---|---|---|---|
| Monday | Danish | Chenab | Ayesha |
| Tuesday | Bilal | Ayesha | Danish |
| Wednesday | Chenab | Bilal | Danish |
| Thursday | Bilal | Ayesha | Chenab |
Proof:
- Ayesha: Mon armoury, Tue study, Thu study = 3 duties; never gate.
- Bilal: Tue gate, Wed study, Thu gate = 3 duties.
- Chenab: Mon study, Wed gate, Thu armoury = 3 duties; not on Tuesday.
- Danish: Mon gate, Tue armoury, Wed armoury = 3 duties; one duty before Wednesday.
- Bilal's conditional armoury duty is not triggered because Danish never does study hall.
- Each night has exactly one cadet per duty, and no cadet is doubled on a night.
3. If Chenab also becomes unavailable on Wednesday, can a valid roster still exist under the same rules? Justify your answer without simply guessing.
Read the worked answer
No. If Chenab is unavailable on Tuesday and Wednesday, Chenab can work only Monday and Thursday. Because no cadet may hold two duties on the same night, Chenab can do at most 2 duties. The other three cadets can do at most 3 each, giving a maximum of 3 + 3 + 3 + 2 = 11 duty slots. The week requires 4 nights × 3 duties = 12 slots. One slot cannot be filled, so no valid roster exists.
A minimal fix would be to relax one constraint - for example, allow one named cadet a fourth duty, make Chenab available for one hour on Wednesday, or reduce Wednesday to two duties. The point is to prove infeasibility by capacity, not to keep shuffling names.