Scheduling Five Workshops Under Hard Constraints
A college tech fest must schedule five workshops-P, Q, R, S, and T-in five consecutive slots numbered 1 to 5, one workshop per slot. The constraints are: P must be before Q; R cannot be in slot 1 or slot 5; S must be immediately after T; and Q cannot be in slot 3. Two student coordinators submit schedules. Proposal 1 is: slot 1 P, slot 2 T, slot 3 S, slot 4 Q, slot 5 R. Proposal 2 is: slot 1 T, slot 2 S, slot 3 P, slot 4 R, slot 5 Q. The faculty coordinator says at least one proposal breaks a rule and asks the students to check both. A sponsor then asks for R to be placed as late as possible. The students must decide which proposal is valid, whether the valid proposal is the only possible schedule, and the latest slot that R can occupy.
1. Check both proposals against every constraint and identify which one is valid.
Read the worked answer
Proposal 1: P1, T2, S3, Q4, R5. P before Q: 1 < 4, satisfied. R not in slot 1 or 5: R is in slot 5, violated. S immediately after T: T2, S3, satisfied. Q not in slot 3: Q is in slot 4, satisfied. Proposal 1 is invalid because of the R placement.
Proposal 2: T1, S2, P3, R4, Q5. P before Q: 3 < 5, satisfied. R not in slot 1 or 5: R is in slot 4, satisfied. S immediately after T: T1, S2, satisfied. Q not in slot 3: Q is in slot 5, satisfied. Proposal 2 is valid. It is not enough to find one satisfied constraint; every constraint must hold simultaneously.
2. Determine whether Proposal 2 is the only valid schedule. If not, list the other valid schedules or explain how you know they exist.
Read the worked answer
Proposal 2 is not unique. Treat T and S as a block TS, since S must immediately follow T. The block can occupy slots (1,2), (2,3), (3,4), or (4,5). Place the block, then place R and the ordered pair P before Q.
Case TS at (1,2): remaining slots 3,4,5. R can be 3 or 4. If R = 3, then P4 Q5 works: T S R P Q. If R = 4, then P3 Q5 works: T S P R Q (Proposal 2).
Case TS at (2,3): remaining slots 1,4,5. R must be 4, and P1 Q5 works: P T S R Q.
Case TS at (3,4): remaining slots 1,2,5. R must be 2, and P1 Q5 works: P R T S Q.
Case TS at (4,5): remaining slots 1,2,3. R cannot be 1, so try R = 2 or 3. R = 2 forces Q into slot 3 if P is before Q, which is forbidden; R = 3 allows P1 Q2: P Q R T S.
Thus there are five valid schedules: TSRPQ, TSPRQ, PTSRQ, PRTSQ, and PQRTS. Proposal 2 is only one of them.
3. The sponsor wants R as late as possible. Find the latest slot R can occupy and give a schedule that achieves it.
Read the worked answer
R cannot occupy slot 5 by the stated constraint, so the latest possible slot is at most 4. We must check whether slot 4 is actually achievable.
Yes: two valid schedules place R in slot 4. One is P1, T2, S3, R4, Q5 (P T S R Q). Check: P before Q, R not 1 or 5, S immediately after T, Q not 3. The other is T1, S2, P3, R4, Q5 (Proposal 2).
Therefore the latest possible slot for R is 4. The answer is not 5 simply because “latest” sounds like the last slot; the explicit constraint rules out slot 5. The sponsor should be offered either of the two schedules with R in slot 4.