Rebuilding a Teaching Rota: One Solution or Several?
A small teaching department is rebuilding its induction rota after a colleague left. Four sessions must be covered, one on each weekday from Monday to Thursday, by four staff: Ana, Ben, Cal and Dee. Each person teaches exactly one session, and no day has more than one session. The department has agreed four rules: (i) Ana teaches before Cal; (ii) Cal teaches on the day immediately after Ana; (iii) Ben does not teach on Monday; (iv) Dee teaches on Thursday. The secretary has asked you to confirm whether the rota is fully determined before she publishes it.
1. Determine the rota. If more than one arrangement satisfies the rules, say so and list them.
Read the worked answer
Work from the strongest rule. Rule (ii) forces Ana and Cal into adjacent days: the options are (Mon, Tue), (Tue, Wed) and (Wed, Thu).
Eliminate by rule (iv): Dee holds Thursday, so (Wed, Thu) is impossible.
Test (Ana Tue, Cal Wed): the free days are Monday and Thursday. Thursday is Dee's, so Ben must take Monday - which breaks rule (iii). Impossible.
Test (Ana Mon, Cal Tue): free days are Wednesday and Thursday. Thursday is Dee's, so Ben takes Wednesday. Check (iii): Ben is not on Monday. Satisfied. Rule (i) is satisfied.
Unique rota: Monday Ana, Tuesday Cal, Wednesday Ben, Thursday Dee.
The rota is fully determined, so the secretary can publish.
2. Which of the four rules could be deleted without changing the answer, and why does it make no difference?
Read the worked answer
Rule (i) - 'Ana teaches before Cal' - is redundant.
Rule (ii) already says Cal teaches on the day immediately after Ana. If Cal is on the very next day, Ana is necessarily before him; rule (i) adds no constraint that (ii) has not already imposed. Deleting it leaves exactly the same single rota.
Check the others are load-bearing:
- Delete (ii): Ana/Cal need not be adjacent, so many arrangements open up. Needed.
- Delete (iii): Ana Tue / Cal Wed / Ben Mon / Dee Thu also becomes valid - two solutions. Needed.
- Delete (iv): Dee could move, and alternative valid rotas appear. Needed.
The test for redundancy is not 'does the rule sound true?' but 'does removing it change the set of solutions?'