Five keynote slots with a redundant rule
Srijan, the annual fest of a small college, must place five keynote talks-A, B, C, D and E-in five consecutive slots: Day 1 morning, Day 1 afternoon, Day 2 morning, Day 2 afternoon, Day 3 morning. Each talk gets exactly one slot. The student council has fixed five rules: (1) A must come before B; (2) C must be immediately after D; (3) E must be in slot 2 or slot 4; (4) B cannot be the last talk; (5) D cannot be in slot 1. A volunteer submits the order A, E, D, C, B for approval. The cultural secretary is unsure whether the rules allow any other order and asks for a full check rather than a spot check. She also wants to know which rule is doing no work, because she prefers a shorter rulebook for next year.
1. Find every schedule satisfying rules (1)–(5). Is the volunteer's order valid?
Read the worked answer
Because C is immediately after D, treat D-C as a block. D cannot be in slot 1, so the possible placements are (2,3), (3,4) and (4,5).\n\n- D-C = (2,3): E must be in slot 4, since slot 2 is taken. Remaining slots 1 and 5 go to A and B. A before B forces A1, B5, but B is last, violating rule 4. Reject.\n- D-C = (3,4): E must be slot 2. Remaining slots 1 and 5 go to A and B; A before B again forces A1, B5, violating rule 4. Reject.\n- D-C = (4,5): E must be slot 2. Remaining slots 1 and 3 go to A and B; A before B gives A1, B3. Valid order: A, E, B, D, C.\n\nSo the only valid order is A, E, B, D, C. The volunteer's A, E, D, C, B is invalid: B is last, directly breaking rule 4.
2. Which rule is redundant? Which rules are essential? Justify by removing rules in turn.
Read the worked answer
Rule 5 (D not in slot 1) is redundant. If D were allowed in slot 1, then C would be in slot 2, E would be forced into slot 4, and the remaining slots 3 and 5 would go to A and B. A before B forces A3, B5, but that violates rule 4. So permitting D in slot 1 creates no additional valid schedule.\n\nRule 4 is essential: remove it and D-C = (2,3) with E4, A1, B5 becomes valid, giving the second order A, E, D, C, B.\n\nRule 2 is essential: without the immediate D-C link, the block structure disappears and many placements become possible. Rule 1 is essential: with D4, C5 and E2 fixed, removing A-before-B allows both A1, B3 and B1, A3. Rule 3 is essential: without the E restriction, the same skeleton allows E in slot 1 or slot 3 as well. The shortest equivalent rulebook is therefore (1)–(4), dropping (5).