AFTD Auto-Formalizing Theoretical Domains

pathGreedyRun_eq_count_and_odd

theoremverified

Twice the greedy count equals the number of true edges plus the number of odd true runs.

Statement

open scoped BigOperators in
theorem pathGreedyRun_eq_count_and_odd (xs : List Bool) :
    2 * pathGreedyRun false xs = xs.countP id + odd_run_count xs
Source
Finite-state path cut-matching certificate for OP-827; exhaustive transition check in experiment 22529.
Verified
11 Nov 2026
Axioms
Quot.soundpropext
Built on 6
  • pathGreedyRun_identityThe greedy matching count and pending run parity satisfy an exact counting identity.
  • pathOddRunFinish_identityThe pending parity counter agrees with the existing odd-run counter.
  • odd_run_countodd_run_count l is the number of maximal runs of true in the boolean word l whose length is odd. The final false is appended so…
  • pathGreedyRunGreedily count disjoint true edges in a Boolean edge word.
  • pathOddRunFinishCount odd true runs while retaining a pending run parity.
  • odd_run_auxodd_run_aux inRun oddLen l scans the boolean list l left to right, keeping a flag inRun (currently inside a run of trues) and…
Used by 1
  • pathCertOddRunIneqFor any four-color path word, the signed sum of odd crossing-run counts for the seven masks is nonpositive.

Lean source view module on GitHub

open scoped BigOperators in
theorem pathGreedyRun_eq_count_and_odd (xs : List Bool) :
    2 * pathGreedyRun false xs = xs.countP id + odd_run_count xs := by
  have h := pathGreedyRun_identity false xs
  have h2 := pathOddRunFinish_identity false false xs
  simp only [Bool.false_and] at h h2
  change odd_run_count xs = pathOddRunFinish false xs at h2
  simpa [h2] using h
See it in the graphDiscuss this resultChallenge it