catch_up_value_aux_ne_loss_iff
theoremverified
In Catch-Up with nonempty remaining pieces and score plus remaining sum at least opponent's score, the mover does not lose if and only if there exists a move y such that the resulting position is not a win for opponent (if turn passes) or not a loss for mover (if turn continues).
Statement
theorem catch_up_value_aux_ne_loss_iff (remaining : Finset ℕ) (s_me s_opp : ℕ) (hrem : remaining.Nonempty) (hsum : ¬ s_me + ∑ x ∈ remaining, x < s_opp) : catch_up_value_aux remaining s_me s_opp false ≠ CatchUpOutcome.loss ↔ ∃ y ∈ remaining, if s_me + y ≥ s_opp then catch_up_value_aux (remaining.erase y) s_opp (s_me + y) false ≠ CatchUpOutcome.win else catch_up_value_aux (remaining.erase y) (s_me + y) s_opp false ≠ CatchUpOutcome.loss
- 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
Classical.choiceQuot.soundpropext- Built on 4
- catch_up_value_auxThe game value of a Catch-Up position for the player about to move. If nothing remains, compare scores. If even all remaining numbers…
- 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…
- CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
- CatchUpOutcome.negNegation of an outcome: win and loss are exchanged, draw is fixed. Used when the turn passes to the other player.
- Used by 2
- 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…
- catch_up_value_aux_icc_erase_ne_loss_iffAfter Player 1 opens with x from {1, ..., N} (with even triangular sum), Player 2 does not lose if and only if there exists a response…
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.
/-- In a Catch-Up position where remaining pieces are nonempty and the mover is not deficit-dominated, the outcome is not a loss if and only if there exists a valid move leading to a non-losing position. -/theorem catch_up_value_aux_ne_loss_iff (remaining : Finset ℕ) (s_me s_opp : ℕ) (hrem : remaining.Nonempty) (hsum : ¬ s_me + ∑ x ∈ remaining, x < s_opp) : catch_up_value_aux remaining s_me s_opp false ≠ CatchUpOutcome.loss ↔ ∃ y ∈ remaining, if s_me + y ≥ s_opp then catch_up_value_aux (remaining.erase y) s_opp (s_me + y) false ≠ CatchUpOutcome.win else catch_up_value_aux (remaining.erase y) (s_me + y) s_opp false ≠ CatchUpOutcome.loss := by conv_lhs => rw [catch_up_value_aux] have hne : remaining ≠ ∅ := Finset.Nonempty.ne_empty hrem simp only [hne, ite_false, hsum] dsimp rw [catch_up_outcome_best_eq_loss] have h_neg (o : CatchUpOutcome) : o.neg = CatchUpOutcome.loss ↔ o = CatchUpOutcome.win := by cases o <;> decide simp [apply_ite (fun x => ¬ x = CatchUpOutcome.loss), h_neg]