pathGreedyRun_identity
theoremverified
The greedy matching count and pending run parity satisfy an exact counting identity.
Statement
open scoped BigOperators in theorem pathGreedyRun_identity (p : Bool) (xs : List Bool) : 2 * pathGreedyRun p xs + (if p then 1 else 0) = xs.countP id + pathOddRunFinish p 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 2
- pathGreedyRunGreedily count disjoint true edges in a Boolean edge word.
- pathOddRunFinishCount odd true runs while retaining a pending run parity.
- Used by 1
- pathGreedyRun_eq_count_and_oddTwice the greedy count equals the number of true edges plus the number of odd true runs.
Lean source view module on GitHub
open scoped BigOperators in theorem pathGreedyRun_identity (p : Bool) (xs : List Bool) : 2 * pathGreedyRun p xs + (if p then 1 else 0) = xs.countP id + pathOddRunFinish p xs := by induction xs generalizing p with | nil => cases p <;> rfl | cons b bs ih => cases p <;> cases b <;> simp [pathGreedyRun, pathOddRunFinish, List.countP_cons] at * <;> omega