AFTD Auto-Formalizing Theoretical Domains

catch_up_value_icc_eq_draw_of_search

theoremverified

If the pruned search on [1, ..., N] from scores 0, 0 at the opening move finds no forced win for the first player but finds that the first player can avoid losing, then Catch-Up on {1, ..., N} is a draw.

Statement

theorem catch_up_value_icc_eq_draw_of_search (N : ℕ)
    (hw : catch_up_search N (List.range' 1 N) 0 0 true true = false)
    (hl : catch_up_search N (List.range' 1 N) 0 0 true false = true) :
    catch_up_value (Finset.Icc 1 N) = .draw
Source
step towards the kernel checks catch_up_value_icc_four/seven/eight/eleven (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Table 2; computable mirror and pruned search of catch_up_value_aux)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • catch_up_searchPruned search over the Catch-Up game tree. With the last flag true it decides whether the player to move can force a win, with it false…
  • 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…
  • catch_up_value_icc_eq_evalThe value of Catch-Up on {1, ..., N} equals the computable mirror evaluated on the list [1, ..., N]; this is what lets the kernel settle…
  • catch_up_search_eqFor every fuel n, list l, scores and opening flag, the pruned search with flag true returns true exactly when the computable mirror's…
  • catch_up_eval_listA computable mirror of catch_up_value_aux: the same Catch-Up recursion on a list of the remaining numbers, by structural recursion on a…
Used by 1
  • catch_up_value_icc_elevenCatch-Up on {1, ..., 11} is a draw under optimal play (the case N = 11 of the Catch-Up conjecture), established by the kernel through the…

Lean source view module on GitHub

/-- Catch-Up on {1,...,N} is a draw when the search finds no forced win and no forced loss. -/theorem catch_up_value_icc_eq_draw_of_search (N : ℕ)    (hw : catch_up_search N (List.range' 1 N) 0 0 true true = false)    (hl : catch_up_search N (List.range' 1 N) 0 0 true false = true) :    catch_up_value (Finset.Icc 1 N) = .draw := by  rw [catch_up_value_icc_eq_eval]  have h := catch_up_search_eq N (List.range' 1 N) 0 0 true  have hnw : catch_up_eval_list N (List.range' 1 N) 0 0 true ≠ .win := by    intro e; rw [← h.1, hw] at e; exact Bool.false_ne_true e  have hnl := h.2.1 hl  cases hv : catch_up_eval_list N (List.range' 1 N) 0 0 true  · exact absurd hv hnw  · exact absurd hv hnl  · rfl
See it in the graphDiscuss this resultChallenge it