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
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.
/-- 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