§2.1, p. 153, flow sketch after Proposition 2.3 — after one balanced day, the remaining days stay balanced
ProvedTimetabling85.ClassTeacher.remaining_boundsbalanced-edge-coloringfloor-ceilingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1timetabling
Let and let be nonnegative integers with . Then
Applied to every entry , every row total and every column total of a requirement matrix, it says that once one day has been scheduled within the bounds of (8)–(10), the remaining lectures form a CT3 instance on days whose bounds lie inside the original ones. So a CT3 solution for the rest is a CT3 solution for the whole, which is what makes the day-by-day construction of the paper's sketch possible: "it will be possible to schedule the remaining lectures … without violating the right inequalities in (8)–(10)".
Formalization Note is natural-number subtraction; under the hypotheses whenever (and when ), so no truncation occurs.
Preamble
import Mathlib import Definitions.Def_Timetabling85_ClassTeacher_Problems
Formal statement
namespace Timetabling85.ClassTeacher
/-- The remaining days stay balanced (de Werra 1985, §2.1, p. 153): if `p ≥ 2` and a day receives
`y` of `s` lectures with `⌊s/p⌋ ≤ y ≤ ⌈s/p⌉`, the remaining `s − y` lectures over `p − 1` days
have bounds `⌊(s−y)/(p−1)⌋ ≥ ⌊s/p⌋` and `⌈(s−y)/(p−1)⌉ ≤ ⌈s/p⌉`. -/
theorem remaining_bounds (s y p : ℕ) (hp : 2 ≤ p) (hlo : lo s p ≤ y) (hhi : y ≤ hi s p) :
lo s p ≤ lo (s - y) (p - 1) ∧ hi (s - y) (p - 1) ≤ hi s p := by sorry
end Timetabling85.ClassTeacher
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 153, §2.1, network-flow sketch after Proposition 2.3 (lower bounds l^k guaranteeing the remaining days)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.