Five Projects, Five Slots
Ms. S is coordinating the district science exhibition at a Navodaya Vidyalaya. Five projects-P1 (dark-room laser show), P2 (hydroponics), P3 (robotics), P4 (water testing), and P5 (solar cooker)-must be demonstrated in five one-hour slots: 9–10, 10–11, 11–12, 12–1, and 1–2. Constraints: P1 needs a dark room and can run only after 11 a.m. P2 needs a water source that is available only in the 9–10 slot. P3 and P1 share the same judge, so P3 cannot be scheduled immediately before or after P1. P4 must be before P5. P5 cannot be in the 9–10 slot because the power-backup test runs then. A colleague proposes: 9–10 P2, 10–11 P3, 11–12 P1, 12–1 P4, 1–2 P5. Ms. S must check whether this schedule violates any rule and whether the constraints determine a single valid schedule.
1. Is the colleague’s proposed schedule valid? Justify by checking each constraint.
Read the worked answer
The proposal is invalid. Check each rule: P2 is in 9–10, satisfying the water-source constraint. P5 is in 1–2, not 9–10, satisfying the power-test constraint. P4 is at 12–1 and P5 at 1–2, so P4 is before P5. P1 is at 11–12, satisfying “after 11 a.m.” However, P3 is at 10–11 and P1 is at 11–12. That makes P3 immediately before P1, which violates the shared-judge constraint that P3 cannot be immediately before or after P1. The schedule therefore fails on exactly one constraint. Ms. S should not approve it merely because four of five rules are satisfied; the judge conflict could force a last-minute reshuffle during the exhibition.
2. Construct one valid schedule different from the colleague’s and show how you derived it.
Read the worked answer
Start with fixed points. P2 must occupy 9–10, so slot 1 is fixed. Choose P1 at 11–12 (slot 3). Then P3 cannot be at 10–11 (slot 2) or 12–1 (slot 4), because those are immediately before and after P1. The remaining slots for P3 are 1–2 (slot 5), so P3 must go there. The remaining slots are 10–11 and 12–1 for P4 and P5, and P4 must be before P5. Therefore P4 goes at 10–11 and P5 at 12–1. Valid schedule: 9–10 P2; 10–11 P4; 11–12 P1; 12–1 P5; 1–2 P3. Check: P1 after 11 yes; P3 not adjacent to P1 yes (gap of one slot); P4 before P5 yes; P2 and P5 constraints satisfied. This is different from the colleague’s proposal and meets every rule.
3. Are the constraints sufficient to determine a unique schedule? If not, how many valid schedules exist, and what single extra constraint would make the schedule unique?
Read the worked answer
They are not sufficient. With P2 fixed at slot 1, P1 can be in slot 3, 4, or 5. If P1 is in slot 3, P3 must be in slot 5, giving P2–P4–P1–P5–P3. If P1 is in slot 4, P3 must be in slot 2, giving P2–P3–P4–P1–P5. If P1 is in slot 5, P3 can be in slot 2 or slot 3: that gives P2–P3–P4–P5–P1 and P2–P4–P3–P5–P1. So there are four valid schedules. A single extra constraint such as “P3 must be in the last slot” would leave only the first schedule. Alternatively, “P4 must be immediately before P5” would select P2–P3–P4–P5–P1. Ms. S should state the extra rule explicitly rather than assume uniqueness, and she should check that the added rule is operationally justified-for example, that the judge is available only at a certain time.