AFTD Auto-Formalizing Theoretical Domains

carpool_backward_step_slack_increase

theoremverifiedformalization

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

  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.

    lines 16–34

    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
  2. 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.

    lines 35–36

    uses carpool_edge_crosses

      unfold carpool_edge_crosses at hcross
      rcases hcross with ⟨haS, hbS⟩ | ⟨hbS, haS⟩
  3. 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.

    lines 37–64

    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
  4. 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)).

    lines 65–74

    uses carpool_slack

        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
  5. 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.

    lines 75–78

    uses carpool_delta_sum

        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
  6. 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)).

    lines 79–82

    uses Or.inr, Or.inl, Finset.insert_nonempty

        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⟩
  7. 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.

    lines 83–92

    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
  8. 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.

    lines 93–102

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it