AFTD Auto-Formalizing Theoretical Domains

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

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