Repairing an Interview Roster Under Fixed Conditions
The district education office must schedule five interviews - Ayesha (A), Bilal (B), Chaman (C), Dilawar (D) and Emaan (E) - one per day from Monday to Friday. The following conditions apply: C must be interviewed immediately before E; A cannot be interviewed on Monday; D must be interviewed after A; and B cannot be interviewed on Friday. A clerk submits this draft roster: Monday A, Tuesday C, Wednesday E, Thursday D, Friday B. The additional secretary rejects the draft without giving reasons and asks you to produce a corrected roster that keeps the original conditions and changes as few placements as possible. No interviewer is available at weekends, and no two candidates can share a day.
1. Identify which conditions the draft roster violates and explain your check.
Read the worked answer
Check each condition against the draft sequence A, C, E, D, B. Condition 1: C is immediately before E - Tuesday C and Wednesday E satisfy this. Condition 2: A is not on Monday - A is on Monday, so this is violated. Condition 3: D is after A - A is Monday and D is Thursday, so this is satisfied. Condition 4: B is not on Friday - B is on Friday, so this is violated. The draft therefore breaks two of the four conditions, not one. The C–E block and the A-before-D ordering are already correct and should be preserved if the aim is to change as few placements as possible.
2. Produce a corrected roster that changes the fewest placements, and state whether that correction is unique.
Read the worked answer
Keep C on Tuesday and E on Wednesday, since moving that block is unnecessary. The remaining slots are Monday, Thursday and Friday, to be filled by A, B and D. A cannot take Monday; B cannot take Friday; D must come after A. Testing the options, A on Thursday forces D to Friday and leaves B on Monday: Monday B, Tuesday C, Wednesday E, Thursday A, Friday D. This satisfies all four conditions. It changes three placements: A moves from Monday to Thursday, B from Friday to Monday, and D from Thursday to Friday. Is a two-change fix possible? If C and E stay fixed, any two-change fix would have to leave one of A, B or D in place, but A on Monday and B on Friday are both forbidden, and D on Thursday cannot work because A would then have to be earlier without using Monday. Moving C or E changes at least four placements. The three-change solution is therefore minimal, and it is unique.
3. A sixth candidate, Farah (F), is added and must be interviewed on the day immediately after B. Using Monday to Saturday, construct one valid six-day order or show that none exists.
Read the worked answer
A valid order is Monday B, Tuesday F, Wednesday C, Thursday E, Friday A, Saturday D. Check each condition. F is immediately after B: B on Monday, F on Tuesday - satisfied. C is immediately before E: Wednesday and Thursday - satisfied. A is not on Monday: A is on Friday - satisfied. D is after A: D is on Saturday - satisfied. B is not on Friday: B is on Monday - satisfied. No day is shared. The key constraint is that F must follow B immediately, so B cannot be placed on Saturday, because F would then need Sunday, which is unavailable. B also cannot be on Friday under the original rule, so B is effectively restricted to Monday to Thursday. Within that range a solution clearly exists, as the constructed roster shows.