Proposition 2.3, p. 153 — there exists a solution to CT3 for any number p ≥ 1 of days
ProvedTimetabling85.ClassTeacher.prop_2_3Let be an requirement matrix of nonnegative integers, with class totals and teacher totals , and let be a number of days. Then there are nonnegative integers (, , ) with for all such that, for every day and all ,
In words: the lectures can always be spread over the days so that the daily load of every class and every teacher is perfectly balanced, and at the same time the lectures of each class–teacher pair are spread as evenly as possible. Equivalently, every bipartite multigraph has a -edge-colouring in which every node sees or edges of each colour ( its degree) and every bundle of parallel edges contains or edges of each colour. It extends Propositions 2.1 and 2.2.
Formalization Note The paper says "for any "; the hypothesis makes this a number of days (for and constraint (1) cannot hold). Floors and ceilings in the first two families are of the totals divided by , not sums of entrywise floors and ceilings.
import Mathlib import Definitions.Def_Timetabling85_ClassTeacher_Problems
namespace Timetabling85.ClassTeacher
/-- Proposition 2.3 (de Werra 1985, p. 153): for every `m × n` requirement matrix `R` and every
number `p ≥ 1` of days, problem CT3 ((1) and (8)–(10)) has a solution. -/
theorem prop_2_3 {m n : ℕ} (R : Fin m → Fin n → ℕ) (p : ℕ) (hp : 0 < p) :
∃ x : Fin m → Fin n → Fin p → ℕ, IsCT3 R p x := by sorry
end Timetabling85.ClassTeacher
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.