Scheduling Five Candidate Seminars
A small research institute must schedule five candidate seminars-P, Q, R, S and T-across Monday, Tuesday and Wednesday. Each day has two slots, but because of room sharing no more than two seminars can run on any day. 'Before' means on an earlier day, not merely an earlier slot on the same day. The constraints are: P must be before Q; R cannot be on Monday; T must be on Wednesday; and S must be on the day immediately after P. The administrator has produced a draft schedule with P and R on Monday, S and Q on Tuesday, and T alone on Wednesday. A colleague objects that the draft violates at least one rule. The institute needs a valid schedule before Friday, and the director also wants to know which placements are forced rather than chosen.
1. Determine every valid schedule and identify which placements are forced. Use case reasoning.
Read the worked answer
Start with the constraint that S is on the day immediately after P. P cannot be Wednesday, because then S would be Thursday, outside the window. So P is Monday or Tuesday.
Case 1: P on Tuesday. Then S is Wednesday. Q must be after P, so Q must also be Wednesday. T is already Wednesday. That puts S, Q and T on Wednesday-three seminars-violating the maximum of two. So P cannot be Tuesday.
Case 2: P on Monday. Then S is Tuesday. Q must be after P, so Q is Tuesday or Wednesday. T is Wednesday. R cannot be Monday, so R is Tuesday or Wednesday. Monday contains only P, because S is Tuesday, T is Wednesday, R is barred from Monday, and Q must follow P. Tuesday and Wednesday each have one remaining slot.
The two valid schedules are therefore:
- Monday: P. Tuesday: S, Q. Wednesday: R, T.
- Monday: P. Tuesday: S, R. Wednesday: Q, T.
Forced placements: P on Monday and S on Tuesday. Q and R are interchangeable between Tuesday and Wednesday, subject to the two-per-day cap. The draft is invalid because it places R on Monday, which the rule forbids.
2. The colleague argues: 'R cannot be on Monday, and Wednesday must contain T plus either Q or R, so R must be on Tuesday.' Is the conclusion valid? Identify the faulty assumption.
Read the worked answer
The conclusion is not valid. The premises are true individually:
- R cannot be Monday.
- Wednesday must contain T and one of Q or R, because Q must follow P and P is Monday, and R must be placed somewhere.
But 'Wednesday must contain T plus either Q or R' is a disjunction. It does not select R. There are two sub-cases:
- If Q is placed Wednesday, then R can be Tuesday, giving the schedule P / S, R / Q, T.
- If R is placed Wednesday, then Q must be Tuesday, giving P / S, Q / R, T.
The argument treats the disjunction as if it forced R into Wednesday's second slot, then concludes R must be Tuesday. In fact, R may be Tuesday or Wednesday. The only forced placements are P on Monday and S on Tuesday. The colleague has confused a necessary condition ('R must be Tuesday or Wednesday') with a sufficient one ('R must be Tuesday').
3. A new rule requires that R be scheduled after S. Does the schedule become unique? If so, state it; if not, explain why.
Read the worked answer
Yes, the schedule becomes unique.
From the earlier analysis, P must be Monday and S must be Tuesday. 'R after S' means R must be later than Tuesday. The only remaining day later than Tuesday is Wednesday, so R is Wednesday. T is also Wednesday, filling Wednesday's two slots. Q must follow P, and the only available slot is Tuesday with S. Monday has P alone.
Unique schedule:
- Monday: P
- Tuesday: S, Q
- Wednesday: R, T
The new rule eliminates the alternative in which R was Tuesday and Q was Wednesday. It does not create a capacity conflict, because Wednesday now holds exactly R and T, and Tuesday holds exactly S and Q.