Scheduling Five Recruitment Drives in One Week
The placement cell of a polytechnic must allot five company drives, C1 to C5, to the five working days Monday to Friday of the week beginning 10 March, exactly one drive per day. Constraints agreed at the meeting: (i) C3 must be on Thursday, because that company's interview panel arrives only that morning; (ii) C4 must be on the day immediately after C1, because the same panel conducts both; (iii) C2 cannot be on Monday, because its online test window opens on Tuesday; (iv) C5 must be held before C2. The coordinator announces that the calendar is now fully determined and pins a single schedule on the notice board. A student representative claims there is more than one valid schedule. Separately, the IT cell asks whether the campus fibre upgrade, which needs the whole week's network switched off, can be done on Wednesday.
1. Is the coordinator right that the schedule is unique? Enumerate the valid schedules.
Read the worked answer
No - there are exactly two.
C3 is fixed on Thursday. The C1–C4 pair must be consecutive, and Thursday is unavailable, so the pair can only be Monday–Tuesday or Tuesday–Wednesday.
- Case 1: C1 Monday, C4 Tuesday. Wednesday and Friday remain for C5 and C2. Since C5 must precede C2, C5 = Wednesday and C2 = Friday. C2 is not Monday → satisfied. Valid.
- Case 2: C1 Tuesday, C4 Wednesday. Monday and Friday remain. C5 = Monday, C2 = Friday. C2 not Monday → satisfied. Valid.
Both satisfy all four conditions, so the single schedule on the notice board is arbitrary, not deduced. The coordinator has confused "a schedule that works" with "the only schedule that works". One extra condition - for example C1 must be on Monday, or C5 must be on Monday - would settle it, but as it stands the board should show the constraints, not a false certainty.
2. Which drives' days are forced by the constraints alone, regardless of which valid schedule is chosen? Prove it.
Read the worked answer
C3 is Thursday by condition (i), and C2 is Friday - this one has to be proved, since it is not stated.
- C2 ≠ Monday (condition iii) and C2 ≠ Thursday (C3 is there).
- Suppose C2 = Tuesday. Then C5 must be Monday (it precedes C2). C1–C4 must occupy consecutive days among Wednesday–Friday, but Wednesday–Thursday is blocked by C3 and Thursday–Friday by C3, so no consecutive pair is free. Contradiction.
- Suppose C2 = Wednesday. Then C5 is Monday or Tuesday, and C1–C4 must be a consecutive pair from the remaining days. If C5 = Monday, the free days are Tuesday, Thursday, Friday - no consecutive pair. If C5 = Tuesday, the free days are Monday, Thursday, Friday - again no consecutive pair. Contradiction.
So C2 is Friday, and with C3 on Thursday the pair C1–C4 plus C5 must fill Monday to Wednesday, which is exactly why two arrangements survive. The genuinely forced facts are C3 Thursday, C2 Friday, and C5 occupying whichever of Monday or Wednesday the pair leaves free.
3. Can the fibre upgrade be done on Wednesday, with no drive that day? Determine feasibility and advise the IT cell.
Read the worked answer
No - a Wednesday blackout makes the week impossible.
If Wednesday is unavailable, the C1–C4 pair cannot be Tuesday–Wednesday, so it must be Monday–Tuesday. C3 occupies Thursday. That leaves only Friday for both C5 and C2, and two drives cannot share one day. So no valid schedule exists with Wednesday blank. The constraint is not tight - it is contradictory.
The reason is structural: five drives fill five days, so no day is actually free. Any "day off" must be bought by moving a drive, and moving one breaks either the C1–C4 adjacency or the C5-before-C2 ordering.
Advice to the IT cell: schedule the fibre work outside the drive window - the weekend, or after 17:00 on any drive day, since interviews end by late afternoon. If the work must consume a full working day, either a drive shifts to Saturday (which changes the five-day assumption and must be re-approved by the companies) or the upgrade moves to the following week. The one thing that cannot be done is declaring Wednesday empty while keeping all four conditions.