A Six-Night Roster That 'Cannot Be Drawn'
The emergency department of a teaching hospital has to publish a six-night duty roster, Monday to Saturday, for four duty medical officers: Dr. A, Dr. B, Dr. C and Dr. D. Exactly two officers are on night duty each night, and, to keep the load equal, each officer must do exactly three nights. A documented professional dispute means Dr. A and Dr. B must never be rostered on the same night. Dr. C has been granted the first three nights - Monday, Tuesday and Wednesday - for a family reason. Dr. A's leave for Saturday has been sanctioned, so A cannot be rostered that night. The senior resident who drafts the roster returns it with a note saying the conditions cannot all be met and asking for the A–B restriction to be relaxed. The head of department wants the claim checked before any rule is relaxed, because once a restriction is set aside it is difficult to restore.
1. Show that Dr. C and Dr. D can never be paired on the same night, whatever roster is drawn.
Read the worked answer
Count slots rather than trying rosters. The week has 6 nights × 2 officers = 12 duty slots, and the four officers take exactly 3 each: 4 × 3 = 12, so the quotas fit exactly and no slot is spare.
Dr. A takes 3 nights and Dr. B takes 3 nights, making 6 slots. These two can never share a night, so every one of those 6 slots must be filled by a partner drawn from Dr. C or Dr. D. That consumes exactly 6 of C's and D's slots.
But C and D hold 3 + 3 = 6 slots between them. All six are therefore used up as partners to A or B. Nothing is left over, so no night can consist of C with D.
The argument is a proof about any valid roster, not a check of one sample: the conclusion follows from the slot count plus the A–B exclusion, and it will still hold if the individual night assignments are rearranged.
2. Using Dr. C's granted first three nights, deduce where Dr. D and the A–B choice must fall.
Read the worked answer
Dr. C occupies Monday, Tuesday and Wednesday. Only one further officer can be on duty on each of those nights. If that officer were Dr. D, the night would be a C–D pair, which the previous step rules out. So the first three nights are C plus one of A or B, and Dr. D cannot appear on Monday, Tuesday or Wednesday at all.
Dr. D still owes three nights, and the only nights left are Thursday, Friday and Saturday. Hence D works all three, each paired with A or B.
The whole roster therefore collapses into a simple sequence of choices: on Monday to Wednesday the question is whether A or B joins C, and on Thursday to Saturday whether A or B joins D. Each night contains exactly one of A and B, which automatically gives A three nights and B three nights and makes an A–B clash impossible. The 'impossible' roster is a puzzle with one freedom left in it, not a contradiction.
3. Dr. A is on sanctioned leave on Saturday. Determine what follows, and say whether a valid roster exists.
Read the worked answer
Saturday cannot contain A, so Saturday must be D with B, since C is fixed to Monday to Wednesday and D must work Thursday to Saturday.
Now count. A needs three nights, all of them between Monday and Friday. B needs three nights, one of which is Saturday, so B must take two of Monday to Friday. Monday to Friday has five nights, each containing exactly one of A or B, and 3 + 2 = 5, so the count is consistent.
A valid roster exists. One example: Monday A + C, Tuesday A + C, Wednesday B + C, Thursday A + D, Friday B + D, Saturday B + D. Check it against every rule: A works Monday, Tuesday, Thursday (three); B works Wednesday, Friday, Saturday (three); C and D work three each; no night pairs A with B; no night pairs C with D; A is not on duty on Saturday.
The senior resident's claim is false. A tight set of constraints had been mistaken for an infeasible one, and the A–B rule - intended to protect staff from a documented dispute - would have been surrendered for no reason. The correct response to the note is to return it with the worked roster, not to reopen the restriction.