Workshop Planning: Counts and Certificates

Build a toy workshop planner and a mathematical decision report. Allow 10–14 hours after the labs. The planner distinguishes possible group sizes, assignments of named tasks, conflict-free schedules and staff feasibility. These are different counted objects; combining their numbers without a joint model is invalid.

Fixture and questions

Tasks are {0,1,2,3,4}. Conflicts are (0,1),(1,2),(2,3),(3,0); task 4 is isolated. There are two labeled slots, each holding at most three tasks. Each task goes into exactly one slot, and adjacent tasks must go into different slots.

Staff on the left are {10,11,12}; stations on the right are {20,21,22}. Eligibility is (10,20),(11,20),(12,21),(12,22). Each staff member requires one distinct station; no sharing is allowed in this separate assignment model.

1. Count legal slot-size vectors summing to five with upper bounds three.
2. Count onto assignments of five named tasks to two slots without conflicts or capacity limits. Then impose the actual conflict and capacity constraints.
3. Return a valid slot assignment, prove the minimum number of slots, and explain why the isolate affects the assignment count.
4. Return a maximum staff matching and a subset-based upper bound proving it cannot be improved. Decide whether all staffing requirements are satisfied.
5. Report degrees, components, bridges and two-step walk counts of the conflict graph. Explain why an Euler report on that graph is not a workshop itinerary: edges mean conflict, not physical movement.
6. Count independent task selections along a separate five-vertex path by encoding selected vertices as ones. Explain why this differs from proper coloring, which also forbids adjacent zero-colored vertices sharing their color.
7. For optional workshop tokens in denominations one and two, count unordered ways to provide total four and compare with ordered dispensing sequences.

Proof packet

For each count, state the object set, labels, empty convention and constraints. Give a bijection, disjoint recurrence or inclusion-exclusion derivation. For coloring, pair a witness with a lower bound. For matching, explain why a subset S allows at most |N(S)| of its staff to be matched, and use the resulting upper bound on all staff. Include algorithm coverage and termination under the kit's explicit size limits. Tests and a fixture trace do not replace general reasoning.

Calibration after the attempt

Size vectors are (2,3) and (3,2): two. Onto assignments number 2⁵−2=30. Capacity alone permits C(5,2)+C(5,3)=20 assignments. The four-cycle has two two-colorings, and its isolate doubles the count to four. Every one has slot sizes two and three, so all four satisfy capacity. An edge requires at least two slots and these witnesses establish sufficiency.

Staff matching size is two. S={10,11} has only neighbor 20, leaving at least one staff member unmatched; matching (10,20),(12,21) meets the upper bound. The conflict graph has degrees 2,2,2,2,0, two components, no bridges and an Euler circuit on its non-isolated component. The independent selections on the separate five-vertex path number 13. Token multisets number three, while ordered sequences number five. These numbers describe separate models, not a product formula for the complete workshop.

Changed-assumption defense

Add conflict (0,2): a triangle proves two slots impossible. Add eligibility (11,21): the matching (10,20),(11,21),(12,22) proves full staffing feasible. Now lower both slot capacities to two; five tasks cannot fit even if all conflicts are removed, since total capacity is four. Derive these conclusions before running your program and explain why each certificate answers its own claim.

Submit code, commands, deterministic output, the proof packet, one deliberate fault/regression and a reviewer challenge. Keep first attempts and assistance. Mark external review pending if unavailable. Carry the distinction between model, witness and optimality certificate into Probability and Semester 2 algorithms.