catch_up_outcome_best_eq_draw
theoremverified
Under Catch-Up's best-outcome aggregation on a list of outcomes, the aggregated outcome is a draw if and only if no win appears in the list and at least one draw appears.
Statement
theorem catch_up_outcome_best_eq_draw (os : List CatchUpOutcome) :
CatchUpOutcome.best os = CatchUpOutcome.draw ↔
CatchUpOutcome.win ∉ os ∧ CatchUpOutcome.draw ∈ os- Source
- step towards the Catch-Up conjecture (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Sec. 3.1; formal-conjectures CatchUpConjecture.lean) (Catch-Up ladder step)
- Verified
- 06 Oct 2026
- Axioms
propext- Built on 2
- CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
- CatchUpOutcome.bestGiven a list of outcomes, the best one for the player who chooses, under the order win > draw > loss (and loss if the list is empty).
- Used by 4
- catch_up_value_aux_ne_draw_of_odd_sumIn Catch-Up, if the sum of remaining piece values and player scores is odd, the mover cannot achieve a draw.
- catch_up_outcome_best_eq_iteThe best outcome of a list depends only on which outcomes occur in it: win if a win occurs, otherwise draw if a draw occurs, otherwise loss.
- catch_up_outcome_best_eq_lossUnder Catch-Up's best-outcome aggregation on a list of outcomes, the aggregated outcome is a loss if and only if every outcome in the list…
- catch_up_value_triple_drawFor any natural numbers x < y < z such that x + y = z, the game value of Catch-Up played on the three-element set {x, y, z} is…
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 catch_up_outcome_best_foldl_draw_spec (f : CatchUpOutcome → CatchUpOutcome → CatchUpOutcome) (hf : ∀ a b, f a b = if a = .win ∨ b = .win then .win else if a = .draw ∨ b = .draw then .draw else .loss) (os : List CatchUpOutcome) (acc : CatchUpOutcome) : os.foldl f acc = CatchUpOutcome.draw ↔ CatchUpOutcome.win ∉ os ∧ (acc = CatchUpOutcome.draw ∨ (acc = CatchUpOutcome.loss ∧ CatchUpOutcome.draw ∈ os)) := by induction os generalizing acc with | nil => simp | cons head tail ih => rw [List.foldl_cons, ih, hf, List.mem_cons, List.mem_cons] cases acc <;> cases head <;> simp/-- Under Catch-Up's best-outcome aggregation on a list of outcomes, the outcome is a draw iff no win appears and at least one draw appears. -/theorem catch_up_outcome_best_eq_draw (os : List CatchUpOutcome) : CatchUpOutcome.best os = CatchUpOutcome.draw ↔ CatchUpOutcome.win ∉ os ∧ CatchUpOutcome.draw ∈ os := by unfold CatchUpOutcome.best rw [catch_up_outcome_best_foldl_draw_spec _ (by intro a b; cases a <;> cases b <;> rfl)] simp