AFTD Auto-Formalizing Theoretical Domains

catch_up_value_pair

theoremverifiedformalization

For any natural numbers x < y, the game value of Catch-Up played on the two-element set {x, y} is CatchUpOutcome.win.

Statement

theorem catch_up_value_pair (x y : ℕ) (hxy : x < y) :
    catch_up_value {x, y} = CatchUpOutcome.win
Formalizes
Analysis of All the End Game Possibilities in Catch-up When There Are 3 or 4 Pieces Remaining (2024); Catch-Up: A Game in Which the Lead Alternates (2015)
Verified
01 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • catch_up_value_eq_aux_falseThe game value catch_up_value S is equal to catch_up_value_aux S 0 0 false.
  • catch_up_value_aux_zero_zeroFor any nonempty set S of pieces, the auxiliary Catch-Up value from scores (0, 0) is the best outcome among all opening moves x ∈ S.
  • catch_up_outcome_best_eq_winUnder Catch-Up's best-outcome aggregation on a list of outcomes, the aggregated outcome is a win if and only if a win appears in the list.
  • catch_up_outcome_neg_eq_win_iffNegating an outcome yields a win if and only if the original outcome was a loss.
  • catch_up_value_aux_singletonIn a Catch-Up position with a single remaining piece x, current score s_me, and opponent score s_opp, the game value for the mover is win…
  • catch_up_valueThe outcome of Catch-Up played on the finite set S of natural numbers, from the first player's point of view, assuming optimal play by…
  • CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
  • catch_up_value_eq_win_iffFor any nonempty finite set S of natural numbers, the game value catch_up_value S is CatchUpOutcome.win if and only if there exists some…
Used by 1
  • catch_up_value_icc_twoThe game value of Catch-Up played on the interval Finset.Icc 1 2 = {1, 2} is CatchUpOutcome.win.

Read back from the Lean

For any two natural numbers $x$ and $y$, if $x < y$, then the Catch-Up game played on the set $\{x, y\}$ evaluates to a win for the first player (catch_up_value {x, y} = CatchUpOutcome.win).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- In Catch-Up played on two distinct pieces {x, y} with x < y, the first player wins by choosing the larger piece y. -/theorem catch_up_value_pair (x y : ℕ) (hxy : x < y) :    catch_up_value {x, y} = CatchUpOutcome.win := by  have hne : ({x, y} : Finset ℕ).Nonempty := by simp  rw [catch_up_value_eq_win_iff _ hne]  refine ⟨y, by simp, ?_⟩  rw [Finset.erase_insert_of_ne (ne_of_lt hxy), Finset.erase_singleton, Finset.insert_empty]  rw [catch_up_value_aux_singleton]  split_ifs with h1 h2  · omega  · rfl  · omega
See it in the graphDiscuss this resultChallenge it