catch_up_value_aux_icc_erase_ne_loss_iff
theoremverified
After 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 move y in {1, ..., N} \ {x} that avoids a win for Player 1 (if y ≥ x) or avoids a loss for Player 2 (if y < x).
Statement
theorem catch_up_value_aux_icc_erase_ne_loss_iff (N : ℕ) (h_even : Even (N * (N + 1) / 2)) (x : ℕ) (hx : x ∈ Finset.Icc 1 N) : catch_up_value_aux ((Finset.Icc 1 N).erase x) 0 x false ≠ CatchUpOutcome.loss ↔ ∃ y ∈ (Finset.Icc 1 N).erase x, if y ≥ x then catch_up_value_aux (((Finset.Icc 1 N).erase x).erase y) x y false ≠ CatchUpOutcome.win else catch_up_value_aux (((Finset.Icc 1 N).erase x).erase y) y x 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 5
- catch_up_value_aux_ne_loss_iffIn 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…
- catch_up_sum_icc_erase_geIn {1, ..., N} with even triangular sum, removing any element x leaves a sum at least x.
- catch_up_icc_erase_nonemptyWhen N(N+1)/2 is even and x is in {1, ..., N}, erasing x leaves a nonempty set.
- 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.
- Used by 2
- catch_up_value_aux_icc_erase_max_ne_loss_iffAfter Player 1 opens with N in Catch-Up on {1, ..., N} with even triangular sum and N > 0, every response y satisfies y < N, so Player 2…
- catch_up_value_aux_icc_erase_ne_loss_of_geIn 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…
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, Player 2 does not lose after opening move x if and only if there exists a valid non-losing response. -/theorem catch_up_value_aux_icc_erase_ne_loss_iff (N : ℕ) (h_even : Even (N * (N + 1) / 2)) (x : ℕ) (hx : x ∈ Finset.Icc 1 N) : catch_up_value_aux ((Finset.Icc 1 N).erase x) 0 x false ≠ CatchUpOutcome.loss ↔ ∃ y ∈ (Finset.Icc 1 N).erase x, if y ≥ x then catch_up_value_aux (((Finset.Icc 1 N).erase x).erase y) x y false ≠ CatchUpOutcome.win else catch_up_value_aux (((Finset.Icc 1 N).erase x).erase y) y x false ≠ CatchUpOutcome.loss := by have hrem := catch_up_icc_erase_nonempty N h_even x hx have hsum_ge := catch_up_sum_icc_erase_ge N h_even x hx have hsum : ¬ 0 + ∑ y ∈ (Finset.Icc 1 N).erase x, y < x := by rw [Nat.zero_add] exact not_lt_of_ge hsum_ge have h := catch_up_value_aux_ne_loss_iff ((Finset.Icc 1 N).erase x) 0 x hrem hsum simp only [Nat.zero_add] at h exact h