AFTD Auto-Formalizing Theoretical Domains

catch_up_value_aux_icc_opening_one_ne_win_iff

theoremverified

When N ≥ 3, Player 2 does not win after Player 1 opens with 1 iff for every response y from {2, ..., N}, Player 1 does not lose from the resulting position with scores (1, y).

Statement

theorem catch_up_value_aux_icc_opening_one_ne_win_iff (N : ℕ) (hN : 3 ≤ N) :
    catch_up_value_aux ((Finset.Icc 1 N).erase 1) 0 1 false ≠ CatchUpOutcome.win ↔
      ∀ y ∈ (Finset.Icc 1 N).erase 1,
        catch_up_value_aux (((Finset.Icc 1 N).erase 1).erase y) 1 y 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…
  • CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
  • 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.
Used by 1

Lean source view module on GitHub

/-- When N ≥ 3, in the position after Player 1 opens with 1 from {1, ..., N}, Player 2 does not achieve outcome win if and only if for every response move y ∈ {2, ..., N}, Player 1 does not get outcome loss from the resulting position with scores (1, y). -/theorem catch_up_value_aux_icc_opening_one_ne_win_iff (N : ℕ) (hN : 3 ≤ N) :    catch_up_value_aux ((Finset.Icc 1 N).erase 1) 0 1 false ≠ CatchUpOutcome.win ↔      ∀ y ∈ (Finset.Icc 1 N).erase 1,        catch_up_value_aux (((Finset.Icc 1 N).erase 1).erase y) 1 y false ≠ CatchUpOutcome.loss := by  have h2 : 2 ∈ (Finset.Icc 1 N).erase 1 := by    rw [Finset.mem_erase, Finset.mem_Icc]    omega  have hne : (Finset.Icc 1 N).erase 1 ≠ ∅ := Finset.Nonempty.ne_empty ⟨2, h2⟩  have hsum : ¬ (0 + ∑ x ∈ (Finset.Icc 1 N).erase 1, x < 1) := by    have hle := Finset.single_le_sum (fun x _ => Nat.zero_le x) h2    omega  conv_lhs => rw [catch_up_value_aux]  simp only [hne, ite_false, hsum]  dsimp  rw [not_congr (catch_up_outcome_best_eq_win _)]  simp only [List.mem_map, Finset.mem_toList, Finset.mem_attach, true_and,    Subtype.exists, not_exists]  refine forall₂_congr (fun y hy => ?_)  rw [Finset.mem_erase, Finset.mem_Icc] at hy  have hge : 1 ≤ 0 + y := by omega  rw [if_pos hge]  simp only [zero_add]  rw [not_congr (catch_up_outcome_neg_eq_win_iff _)]
See it in the graphDiscuss this resultChallenge it