carpool_backward_step_slack_increase
For natural numbers n and T, an integer D, trajectory d : ℕ → Fin n → ℤ, and receiver/sender functions a, b : ℕ → Fin n satisfying for all t with 1 ≤ t and t ≤ T that a t ≠ b t, for all v, d t v = d (t - 1) v + (if v = a t then 1 else if v = b t then -1 else 0), and d t (a t) - d t (b t) ≤ 29: if 1 ≤ t, t ≤ T, S : Finset (Fin n) is nonempty, and carpool_edge_crosses (a t) (b t) S, then there exists a finite subset S' : Finset (Fin n) such that (S' = S ∨ S' = insert (b t) S ∨ S' = S \ {a t}), carpool_slack D (d (t - 1)) S' ≥ carpool_slack D (d t) S + 1, and (carpool_slack D (d t) S ≥ 0 → S'.Nonempty).
Statement
theorem carpool_backward_step_slack_increase (n T : ℕ) (D : ℤ) (d : ℕ → Fin n → ℤ) (a b : ℕ → Fin n) (hab : ∀ t, 1 ≤ t → t ≤ T → a t ≠ b t) (hstep : ∀ t v, 1 ≤ t → t ≤ T → d t v = d (t - 1) v + (if v = a t then 1 else if v = b t then -1 else 0)) (hgap : ∀ t, 1 ≤ t → t ≤ T → d t (a t) - d t (b t) ≤ 29) (t : ℕ) (ht1 : 1 ≤ t) (htT : t ≤ T) (S : Finset (Fin n)) (hS : S.Nonempty) (hcross : carpool_edge_crosses (a t) (b t) S) : ∃ S' : Finset (Fin n), (S' = S ∨ S' = insert (b t) S ∨ S' = S \ {a t}) ∧ carpool_slack D (d (t - 1)) S' ≥ carpool_slack D (d t) S + 1 ∧ (carpool_slack D (d t) S ≥ 0 → S'.Nonempty)
- Formalizes
- arXiv:2611.00388 Lemma 4.1
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- carpool_threshold_AThe quadratic threshold function carpool_threshold_A taking an integer parameter D : ℤ and a natural number k : ℕ, defined as the integer…
- carpool_slackThe discrepancy slack carpool_slack taking an integer threshold D : ℤ, a discrepancy vector d : Fin n → ℤ, and a finite vertex subset S :…
- carpool_edge_crossesAn edge between vertices u and v in Fin n crosses a finite vertex subset S : Finset (Fin n) if either u ∈ S and v ∉ S, or v ∈ S and u ∉ S.
- carpool_threshold_A_diffFor any integer threshold D : ℤ and natural number k : ℕ, the forward difference carpool_threshold_A D (k + 1) - carpool_threshold_A D k…
- carpool_slack_emptyFor any natural number n : ℕ, integer threshold D : ℤ, and discrepancy vector d : Fin n → ℤ, the slack carpool_slack D d (∅ : Finset (Fin…
- carpool_delta_sumFor any integer threshold D : ℤ, integer discrepancies da db : ℤ satisfying da - db ≤ 29, and natural number k ≥ 1, the sum of delta_plus…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- carpool_witness_familyFix n, T, an edge sequence (u_t, v_t) and D >= 300. From the edges alone one builds a family W of pairs (t, S) with |W| <= 2 T…
Read back from the Lean
Given natural numbers $n$ and $T$, an integer $D$, and functions $d : \mathbb{N} \to \mathrm{Fin}(n) \to \mathbb{Z}$ and $a, b : \mathbb{N} \to \mathrm{Fin}(n)$ such that for every $t \in [1, T]$: 1. $a(t) \neq b(t)$, 2. for all $v \in \mathrm{Fin}(n)$, $d(t, v) = d(t-1, v) + 1$ if $v = a(t)$, $d(t-1, v) - 1$ if $v = b(t)$, and $d(t-1, v)$ otherwise, and 3. $d(t, a(t)) - d(t, b(t)) \le 29$; if $t \in [1, T]$, $S \subseteq \mathrm{Fin}(n)$ is a nonempty finite set, and the edge between $a(t)$ and $b(t)$ crosses $S$ (meaning either $a(t) \in S \wedge b(t) \notin S$ or $b(t) \in S \wedge a(t) \notin S$), then there exists a finite subset $S' \subseteq \mathrm{Fin}(n)$ such that: - $S' = S$, $S' = S \cup \{b(t)\}$, or $S' = S \setminus \{a(t)\}$; - the slack of $S'$ with respect to $d(t-1)$ and $D$ is at least the slack of $S$ with respect to $d(t)$ and $D$ plus $1$; and - if the slack of $S$ with respect to $d(t)$ and $D$ is non-negative, then $S'$ is nonempty.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the potential (slack) can increase by at least 1 when taking a backward step from time t to t - 1, the proof analyzes the crossing edge between receiver a(t) (incremented at step t) and sender b(t) (decremented at step t). When b(t) ∈ S and a(t) ∉ S, keeping S' = S directly increases the weight sum on S by 1 while preserving its cardinality, increasing slack by 1. When a(t) ∈ S and b(t) ∉ S, two candidate modifications are evaluated: adding b(t) to S or removing a(t) from S. The lemma carpool_delta_sum shows that the bounded gap d_t(a(t)) - d_t(b(t)) ≤ 29 forces the sum of the slack changes of these two candidate modifications to be at least 1, so at least one candidate increases slack by at least 1. Finally, nonemptiness of S' follows by construction for insertions, or because an empty set has slack 0 which contradicts the strictly positive lower bound on slack at t - 1.
For any subset U, the sum of weights at time t - 1 satisfies ∑_{i ∈ U} d(t-1, i) = ∑_{i ∈ U} d(t, i) - 1_{a(t) ∈ U} + 1_{b(t) ∈ U}.
By the forward dynamics, d(t, v) changes from d(t-1, v) by +1 at a(t) and -1 at b(t), with a(t) ≠ b(t) by assumption hab. Inverting this relation point-by-point yields d(t-1, v) = d(t, v) - 1_{v = a(t)} + 1_{v = b(t)}. Summing this identity over U via Finset.sum_congr, Finset.sum_sub_distrib, and Finset.sum_add_distrib, and collapsing the indicator sums via Finset.sum_ite_eq', yields the general subset sum formula.
uses
Finset.sum_congr,Finset.sum_sub_distrib,Finset.sum_add_distrib,Finset.sum_ite_eq'have ht : a t ≠ b t := hab t ht1 htT have hsum : ∀ U : Finset (Fin n), ∑ i ∈ U, d (t - 1) i = ∑ i ∈ U, d t i - (if a t ∈ U then (1:ℤ) else 0) + (if b t ∈ U then (1:ℤ) else 0) := by intro U have hpt : ∀ i ∈ U, d (t-1) i = d t i - (if i = a t then (1:ℤ) else if i = b t then -1 else 0) := by intro i _ have h := hstep t i ht1 htT linarith rw [Finset.sum_congr rfl hpt, Finset.sum_sub_distrib] have hsplit : ∀ i : Fin n, (if i = a t then (1:ℤ) else if i = b t then -1 else 0) = (if i = a t then (1:ℤ) else 0) + (if i = b t then (-1:ℤ) else 0) := by intro i by_cases h1 : i = a t · subst h1; simp [ht] · simp [h1] rw [Finset.sum_congr rfl (fun i _ => hsplit i), Finset.sum_add_distrib] rw [Finset.sum_ite_eq', Finset.sum_ite_eq'] split_ifs <;> simp
The crossing hypothesis splits into two cases: either a(t) ∈ S and b(t) ∉ S, or b(t) ∈ S and a(t) ∉ S.
Unfolding carpool_edge_crosses shows that exactly one endpoint of the edge (a(t), b(t)) lies in S. We perform a case analysis on the two disjuncts.
uses
carpool_edge_crossesunfold carpool_edge_crosses at hcross rcases hcross with ⟨haS, hbS⟩ | ⟨hbS, haS⟩
When a(t) ∈ S and b(t) ∉ S, the sum on S ∪ {b(t)} at t - 1 is ∑_{i ∈ S} d(t, i) + d(t, b(t)) with cardinality |S| + 1, and the sum on S \ {a(t)} at t - 1 is ∑_{i ∈ S} d(t, i) - d(t, a(t)) with cardinality |S| - 1.
Since a(t) ∈ S and b(t) ∉ S, the sum over S at time t - 1 decreases by 1 (using if_pos and if_neg). At the single vertex b(t), d(t-1, b(t)) = d(t, b(t)) + 1 (using Ne.symm and if_pos), so adding b(t) to S via Finset.sum_insert produces a total sum of ∑_{i ∈ S} d(t, i) + d(t, b(t)), with cardinality |S| + 1 by Finset.card_insert_of_notMem. On the other hand, neither a(t) nor b(t) belongs to S \ {a(t)} (by Finset.mem_sdiff and Finset.mem_singleton), so its sum is unchanged from t to t - 1; removing a(t) subtracts d(t, a(t)) via Finset.sum_erase_add and reduces the cardinality by 1 via Finset.card_erase_of_mem and Finset.sdiff_singleton_eq_erase. Nonemptiness of S also ensures 1 ≤ |S| by Finset.card_pos.mpr.
uses
Finset.card_pos.mpr,if_pos,if_neg,Ne.symm,Finset.sum_insert,Finset.mem_sdiff,Finset.mem_singleton,Finset.sdiff_singleton_eq_erase,Finset.card_erase_of_mem,Finset.sum_erase_add,Finset.card_insert_of_notMem· -- case: a t ∈ S, b t ∉ S have hk : 1 ≤ S.card := by have := Finset.card_pos.mpr hS; omega have hAt : ∑ i ∈ S, d (t-1) i = ∑ i ∈ S, d t i - 1 := by have h := hsum S rw [if_pos haS, if_neg hbS] at h linarith have hbt : d (t-1) (b t) = d t (b t) + 1 := by have h := hstep t (b t) ht1 htT rw [if_neg (Ne.symm ht), if_pos rfl] at h linarith have hSt : ∑ i ∈ insert (b t) S, d (t-1) i = ∑ i ∈ S, d t i + d t (b t) := by rw [Finset.sum_insert hbS, hAt, hbt]; ring have hSa : ∑ i ∈ S \ {a t}, d (t-1) i = ∑ i ∈ S \ {a t}, d t i := by have h := hsum (S \ {a t}) have ha' : a t ∉ S \ {a t} := by simp have hb' : b t ∉ S \ {a t} := by simp only [Finset.mem_sdiff, Finset.mem_singleton] rintro ⟨hbs, hba⟩; exact hbS hbs rw [if_neg ha', if_neg hb'] at h linarith have hcardminus : (S \ {a t}).card = S.card - 1 := by rw [Finset.sdiff_singleton_eq_erase] exact Finset.card_erase_of_mem haS have hSminus_t : ∑ i ∈ S \ {a t}, d t i = ∑ i ∈ S, d t i - d t (a t) := by rw [Finset.sdiff_singleton_eq_erase] have h := Finset.sum_erase_add S (fun i => d t i) haS linarith have hcardplus : (insert (b t) S).card = S.card + 1 := Finset.card_insert_of_notMem hbS
The slack of S ∪ {b(t)} at t - 1 equals the slack of S at t plus Δ⁺, and the slack of S \ {a(t)} at t - 1 equals the slack of S at t plus Δ⁻.
Unfolding carpool_slack and substituting the sums and cardinalities computed in the previous step, algebraic simplification expresses the slack of S ∪ {b(t)} as carpool_slack D (d t) S + Δ⁺, where Δ⁺ = d(t, b(t)) - (Φ_D(|S|+1) - Φ_D(|S|)), and the slack of S \ {a(t)} as carpool_slack D (d t) S + Δ⁻, where Δ⁻ = -d(t, a(t)) + (Φ_D(|S|) - Φ_D(|S|-1)).
uses
carpool_slackhave hplus : carpool_slack D (d (t-1)) (insert (b t) S) = carpool_slack D (d t) S + (d t (b t) - (carpool_threshold_A D (S.card + 1) - carpool_threshold_A D S.card)) := by simp only [carpool_slack] rw [hSt, hcardplus] ring have hminus : carpool_slack D (d (t-1)) (S \ {a t}) = carpool_slack D (d t) S + (- d t (a t) + (carpool_threshold_A D S.card - carpool_threshold_A D (S.card - 1))) := by simp only [carpool_slack] rw [hSa, hcardminus, hSminus_t] ring
The sum of the two adjustments satisfies Δ⁺ + Δ⁻ ≥ 1.
Lemma carpool_delta_sum shows that whenever 1 ≤ |S| and the gap condition d(t, a(t)) - d(t, b(t)) ≤ 29 holds, the sum of the adjustments Δ⁺ and Δ⁻ is at least 1.
uses
carpool_delta_sumhave hdelta : (d t (b t) - (carpool_threshold_A D (S.card + 1) - carpool_threshold_A D S.card)) + (- d t (a t) + (carpool_threshold_A D S.card - carpool_threshold_A D (S.card - 1))) ≥ 1 := by have h := carpool_delta_sum D (d t (a t)) (d t (b t)) S.card hk (hgap t ht1 htT) simpa using h
If Δ⁺ ≥ 1, then choosing S' = S ∪ {b(t)} satisfies the theorem.
When Δ⁺ ≥ 1, the slack formula shows that the slack of S ∪ {b(t)} at time t - 1 increases by at least 1. The set is nonempty by Finset.insert_nonempty and matches the second candidate form (Or.inr (Or.inl rfl)).
uses
Or.inr,Or.inl,Finset.insert_nonemptyby_cases hp : (d t (b t) - (carpool_threshold_A D (S.card + 1) - carpool_threshold_A D S.card)) ≥ 1 · have hle : carpool_slack D (d (t-1)) (insert (b t) S) ≥ carpool_slack D (d t) S + 1 := by rw [hplus]; linarith exact ⟨insert (b t) S, Or.inr (Or.inl rfl), hle, fun _ => Finset.insert_nonempty (b t) S⟩
If Δ⁺ < 1, then choosing S' = S \ {a(t)} satisfies the theorem.
Since Δ⁺ + Δ⁻ ≥ 1, Δ⁺ < 1 forces Δ⁻ ≥ 1, so S \ {a(t)} increases slack by at least 1 (Or.inr). Moreover, if the slack of S at time t was non-negative, S \ {a(t)} cannot be empty: by Finset.nonempty_iff_ne_empty, an empty set would have slack 0 by carpool_slack_empty, contradicting that its slack at t - 1 is at least 0 + 1 = 1 > 0.
uses
Or.inr,Finset.nonempty_iff_ne_empty,carpool_slack_empty· have hm : (- d t (a t) + (carpool_threshold_A D S.card - carpool_threshold_A D (S.card - 1))) ≥ 1 := by linarith have hle : carpool_slack D (d (t-1)) (S \ {a t}) ≥ carpool_slack D (d t) S + 1 := by rw [hminus]; linarith refine ⟨S \ {a t}, Or.inr (Or.inr rfl), hle, ?_⟩ intro hs rw [Finset.nonempty_iff_ne_empty] intro he rw [he, carpool_slack_empty] at hle linarith
When b(t) ∈ S and a(t) ∉ S, choosing S' = S satisfies the theorem.
Applying the general subset sum formula with a(t) ∉ S and b(t) ∈ S using if_neg and if_pos shows that ∑_{i ∈ S} d(t-1, i) = ∑_{i ∈ S} d(t, i) + 1. Since S is retained unchanged (Or.inl), its cardinality and threshold penalty do not change, so by definition of carpool_slack, its slack increases by exactly 1. Nonemptiness is inherited directly from S.
uses
if_neg,if_pos,Or.inl,carpool_slack· -- case: b t ∈ S, a t ∉ S have hAt : ∑ i ∈ S, d (t-1) i = ∑ i ∈ S, d t i + 1 := by have h := hsum S rw [if_neg haS, if_pos hbS] at h linarith refine ⟨S, Or.inl rfl, ?_, fun _ => hS⟩ simp only [carpool_slack] rw [hAt] ring_nf linarith
Finset.sum_congr- If two finite sets are equal and their summands agree on every element, their sums are equal.
Finset.sum_sub_distrib- The sum of a difference of functions over a finite set equals the difference of their sums.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of their sums.
Finset.sum_ite_eq'- Summing over a finite set an indicator term that is non-zero only at a single point a yields that value if a is in the set, and 0 otherwise.
carpool_edge_crosses- A directed edge between u and v crosses a set S if exactly one of u or v belongs to S.
Finset.card_pos.mpr- A finite set has strictly positive cardinality if and only if it is nonempty.
if_pos- If a condition is true, the conditional if-then-else expression evaluates to the then branch.
if_neg- If a condition is false, the conditional if-then-else expression evaluates to the else branch.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.sum_insert- If an element a is not in s, the sum over s ∪ {a} equals f(a) plus the sum over s.
Finset.mem_sdiff- An element belongs to a set difference s \ t if and only if it belongs to s and not to t.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.sdiff_singleton_eq_erase- Removing the singleton {a} from a finite set s is identical to erasing a from s.
Finset.card_erase_of_mem- Erasing an element from a set in which it is present decreases the cardinality by 1.
Finset.sum_erase_add- If a belongs to s, the sum over s \ {a} plus f(a) equals the sum over s.
Finset.card_insert_of_notMem- Inserting an element not already in s increases the cardinality of s by 1.
carpool_slack- The slack of a set S with respect to state vector d and target D is the sum of d over S minus the threshold Φ_D(|S|).
carpool_delta_sum- If the gap d(a) - d(b) is at most 29 and |S| ≥ 1, the sum of the potential slack adjustments Δ⁺ (from inserting b) and Δ⁻ (from removing a) is at least 1.
Or.inr- Proves a disjunction A ∨ B given a proof of the right disjunct B.
Or.inl- Proves a disjunction A ∨ B given a proof of the left disjunct A.
Finset.insert_nonempty- Inserting an element into any finite set produces a nonempty set.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not the empty set.
carpool_slack_empty- The slack of the empty set is 0.
- The threshold function carpool_threshold_A D k is defined as k * D - 15 * k * (k - 1). The lemma carpool_delta_sum encapsulates the arithmetic verification showing that the sum of the forward and backward slack increments satisfies (d_t(b_t) - d_t(a_t)) + 30 ≥ -29 + 30 = 1 whenever d_t(a_t) - d_t(b_t) ≤ 29.
- The three-way disjunction on candidate sets S' is formally parenthesised as S' = S ∨ (S' = insert (b t) S ∨ S' = S \ {a t}), so selecting the candidate insert (b t) S requires Or.inr (Or.inl rfl) and selecting S \ {a t} requires Or.inr (Or.inr rfl).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Lemma 4.1 in arXiv:2611.00388: potential increase along backward steps in carpooling. -/theorem carpool_backward_step_slack_increase (n T : ℕ) (D : ℤ) (d : ℕ → Fin n → ℤ) (a b : ℕ → Fin n) (hab : ∀ t, 1 ≤ t → t ≤ T → a t ≠ b t) (hstep : ∀ t v, 1 ≤ t → t ≤ T → d t v = d (t - 1) v + (if v = a t then 1 else if v = b t then -1 else 0)) (hgap : ∀ t, 1 ≤ t → t ≤ T → d t (a t) - d t (b t) ≤ 29) (t : ℕ) (ht1 : 1 ≤ t) (htT : t ≤ T) (S : Finset (Fin n)) (hS : S.Nonempty) (hcross : carpool_edge_crosses (a t) (b t) S) : ∃ S' : Finset (Fin n), (S' = S ∨ S' = insert (b t) S ∨ S' = S \ {a t}) ∧ carpool_slack D (d (t - 1)) S' ≥ carpool_slack D (d t) S + 1 ∧ (carpool_slack D (d t) S ≥ 0 → S'.Nonempty) := by have ht : a t ≠ b t := hab t ht1 htT have hsum : ∀ U : Finset (Fin n), ∑ i ∈ U, d (t - 1) i = ∑ i ∈ U, d t i - (if a t ∈ U then (1:ℤ) else 0) + (if b t ∈ U then (1:ℤ) else 0) := by intro U have hpt : ∀ i ∈ U, d (t-1) i = d t i - (if i = a t then (1:ℤ) else if i = b t then -1 else 0) := by intro i _ have h := hstep t i ht1 htT linarith rw [Finset.sum_congr rfl hpt, Finset.sum_sub_distrib] have hsplit : ∀ i : Fin n, (if i = a t then (1:ℤ) else if i = b t then -1 else 0) = (if i = a t then (1:ℤ) else 0) + (if i = b t then (-1:ℤ) else 0) := by intro i by_cases h1 : i = a t · subst h1; simp [ht] · simp [h1] rw [Finset.sum_congr rfl (fun i _ => hsplit i), Finset.sum_add_distrib] rw [Finset.sum_ite_eq', Finset.sum_ite_eq'] split_ifs <;> simp unfold carpool_edge_crosses at hcross rcases hcross with ⟨haS, hbS⟩ | ⟨hbS, haS⟩ · -- case: a t ∈ S, b t ∉ S have hk : 1 ≤ S.card := by have := Finset.card_pos.mpr hS; omega have hAt : ∑ i ∈ S, d (t-1) i = ∑ i ∈ S, d t i - 1 := by have h := hsum S rw [if_pos haS, if_neg hbS] at h linarith have hbt : d (t-1) (b t) = d t (b t) + 1 := by have h := hstep t (b t) ht1 htT rw [if_neg (Ne.symm ht), if_pos rfl] at h linarith have hSt : ∑ i ∈ insert (b t) S, d (t-1) i = ∑ i ∈ S, d t i + d t (b t) := by rw [Finset.sum_insert hbS, hAt, hbt]; ring have hSa : ∑ i ∈ S \ {a t}, d (t-1) i = ∑ i ∈ S \ {a t}, d t i := by have h := hsum (S \ {a t}) have ha' : a t ∉ S \ {a t} := by simp have hb' : b t ∉ S \ {a t} := by simp only [Finset.mem_sdiff, Finset.mem_singleton] rintro ⟨hbs, hba⟩; exact hbS hbs rw [if_neg ha', if_neg hb'] at h linarith have hcardminus : (S \ {a t}).card = S.card - 1 := by rw [Finset.sdiff_singleton_eq_erase] exact Finset.card_erase_of_mem haS have hSminus_t : ∑ i ∈ S \ {a t}, d t i = ∑ i ∈ S, d t i - d t (a t) := by rw [Finset.sdiff_singleton_eq_erase] have h := Finset.sum_erase_add S (fun i => d t i) haS linarith have hcardplus : (insert (b t) S).card = S.card + 1 := Finset.card_insert_of_notMem hbS have hplus : carpool_slack D (d (t-1)) (insert (b t) S) = carpool_slack D (d t) S + (d t (b t) - (carpool_threshold_A D (S.card + 1) - carpool_threshold_A D S.card)) := by simp only [carpool_slack] rw [hSt, hcardplus] ring have hminus : carpool_slack D (d (t-1)) (S \ {a t}) = carpool_slack D (d t) S + (- d t (a t) + (carpool_threshold_A D S.card - carpool_threshold_A D (S.card - 1))) := by simp only [carpool_slack] rw [hSa, hcardminus, hSminus_t] ring have hdelta : (d t (b t) - (carpool_threshold_A D (S.card + 1) - carpool_threshold_A D S.card)) + (- d t (a t) + (carpool_threshold_A D S.card - carpool_threshold_A D (S.card - 1))) ≥ 1 := by have h := carpool_delta_sum D (d t (a t)) (d t (b t)) S.card hk (hgap t ht1 htT) simpa using h by_cases hp : (d t (b t) - (carpool_threshold_A D (S.card + 1) - carpool_threshold_A D S.card)) ≥ 1 · have hle : carpool_slack D (d (t-1)) (insert (b t) S) ≥ carpool_slack D (d t) S + 1 := by rw [hplus]; linarith exact ⟨insert (b t) S, Or.inr (Or.inl rfl), hle, fun _ => Finset.insert_nonempty (b t) S⟩ · have hm : (- d t (a t) + (carpool_threshold_A D S.card - carpool_threshold_A D (S.card - 1))) ≥ 1 := by linarith have hle : carpool_slack D (d (t-1)) (S \ {a t}) ≥ carpool_slack D (d t) S + 1 := by rw [hminus]; linarith refine ⟨S \ {a t}, Or.inr (Or.inr rfl), hle, ?_⟩ intro hs rw [Finset.nonempty_iff_ne_empty] intro he rw [he, carpool_slack_empty] at hle linarith · -- case: b t ∈ S, a t ∉ S have hAt : ∑ i ∈ S, d (t-1) i = ∑ i ∈ S, d t i + 1 := by have h := hsum S rw [if_neg haS, if_pos hbS] at h linarith refine ⟨S, Or.inl rfl, ?_, fun _ => hS⟩ simp only [carpool_slack] rw [hAt] ring_nf linarith