catch_up_value_aux_icc_erase_ne_loss_of_ge
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.
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).
uses
catch_up_value_aux_icc_erase_ne_loss_iffrw [catch_up_value_aux_icc_erase_ne_loss_iff N h_even x hx]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.
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
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 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]