AFTD Auto-Formalizing Theoretical Domains

catch_up_value_aux_icc_erase_ne_loss_of_ge

theoremverified

In Catch-Up on {1, ..., N} with even triangular sum, if Player 2 has a response y ≥ x such that Player 1 does not win from the resulting position with scores (x, y), then Player 2 does not lose after opening move x.

Statement

theorem catch_up_value_aux_icc_erase_ne_loss_of_ge (N : ℕ) (h_even : Even (N * (N + 1) / 2))
    (x y : ℕ) (hx : x ∈ Finset.Icc 1 N) (hy : y ∈ (Finset.Icc 1 N).erase x) (hge : x ≤ y)
    (h : catch_up_value_aux (((Finset.Icc 1 N).erase x).erase y) x y false ≠ CatchUpOutcome.win) :
    catch_up_value_aux ((Finset.Icc 1 N).erase x) 0 x false ≠ CatchUpOutcome.loss
Source
step towards catch_up_value_aux_icc_after_opening_ne_loss (Catch-Up conjecture (Catch-Up: A Game in Which the Lead Alternates, 2015, Sec. 3.1))
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • 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_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…

The proof, explained

The proof reduces the goal to an existential statement via `catch_up_value_aux_icc_erase_ne_loss_iff`, which characterizes non-losing positions for Player 2 in terms of having at least one valid response. The given move y serves as the witness: since y ≥ x, the condition reduces to Player 1 not winning from scores (x, y), which holds by assumption.

  1. The goal is equivalent to the existence of a valid response y for Player 2 that avoids a loss.

    Rewriting with `catch_up_value_aux_icc_erase_ne_loss_iff` transforms the goal into showing that there exists some y ∈ {1, ..., N} \ {x} such that if y ≥ x, Player 1 does not win from scores (x, y), and if y < x, Player 2 does not lose from scores (y, x).

    line 6

    uses catch_up_value_aux_icc_erase_ne_loss_iff

      rw [catch_up_value_aux_icc_erase_ne_loss_iff N h_even x hx]
  2. The given move y satisfies this existential condition.

    We supply y and the hypothesis `hy` (y ∈ {1, ..., N} \ {x}) as the witness for the existential quantifier. Since x ≤ y by hypothesis `hge`, the conditional simplifies to its first branch, which states that Player 1 does not win from scores (x, y). This is precisely hypothesis `h`, closing the goal.

    lines 7–8

      refine ⟨y, hy, ?_⟩
      simp [hge, h]
catch_up_value_aux_icc_erase_ne_loss_iff
Player 2 avoids a loss after Player 1's opening move x ∈ {1, ..., N} if and only if there exists a valid reply y ∈ {1, ..., N} \ {x} such that: if y ≥ x, Player 1 does not win from the position with scores (x, y); and if y < x, Player 2 does not lose from the position with scores (y, x).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- In Catch-Up on {1, ..., N} with even triangular sum, if Player 2 has a response y ≥ x such that Player 1 does not win from the resulting position with scores (x, y), then Player 2 does not lose after opening move x. -/theorem catch_up_value_aux_icc_erase_ne_loss_of_ge (N : ℕ) (h_even : Even (N * (N + 1) / 2))    (x y : ℕ) (hx : x ∈ Finset.Icc 1 N) (hy : y ∈ (Finset.Icc 1 N).erase x) (hge : x ≤ y)    (h : catch_up_value_aux (((Finset.Icc 1 N).erase x).erase y) x y false ≠ CatchUpOutcome.win) :    catch_up_value_aux ((Finset.Icc 1 N).erase x) 0 x false ≠ CatchUpOutcome.loss := by  rw [catch_up_value_aux_icc_erase_ne_loss_iff N h_even x hx]  refine ⟨y, hy, ?_⟩  simp [hge, h]
See it in the graphDiscuss this resultChallenge it