catch_up_value_aux_eq_eval_list
theoremverified
For every fuel n, every duplicate-free list l of length at most n, and all scores and opening flags, the Catch-Up value of the finset of l equals the computable mirror catch_up_eval_list n l.
Statement
theorem catch_up_value_aux_eq_eval_list (n : ℕ) :
∀ (l : List ℕ), l.Nodup → l.length ≤ n → ∀ (s_me s_opp : ℕ) (first : Bool),
catch_up_value_aux l.toFinset s_me s_opp first = catch_up_eval_list n l s_me s_opp first- 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 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…
- 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…
- catch_up_best_attach_map_congrIf F and G agree on every element of a list l of natural numbers, then the best outcome of F over the attached elements of l's finset…
- catch_up_toFinset_eraseFor a list l of natural numbers without duplicates, erasing a from the finset of l is the finset of l with a erased.
- Used by 1
- catch_up_value_eq_eval_listFor a duplicate-free list l, the value of Catch-Up on the finset of l equals the computable mirror evaluated on l from scores 0, 0 at 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.
/-- The computable mirror agrees with `catch_up_value_aux` whenever the fuel covers the list. -/theorem catch_up_value_aux_eq_eval_list (n : ℕ) : ∀ (l : List ℕ), l.Nodup → l.length ≤ n → ∀ (s_me s_opp : ℕ) (first : Bool), catch_up_value_aux l.toFinset s_me s_opp first = catch_up_eval_list n l s_me s_opp first := by induction n with | zero => intro l _ hlen s_me s_opp first have : l = [] := List.eq_nil_of_length_eq_zero (by omega) subst this rw [catch_up_value_aux.eq_def] simp [catch_up_eval_list] | succ n ih => intro l hl hlen s_me s_opp first cases l with | nil => rw [catch_up_value_aux.eq_def] simp [catch_up_eval_list] | cons h t => rw [catch_up_value_aux.eq_def] have hne : (h :: t).toFinset ≠ ∅ := by simp have hsum : (h :: t).toFinset.sum (fun x => x) = (h :: t).sum := by rw [List.sum_toFinset _ hl, List.map_id'] simp only [hne, if_false, hsum, catch_up_eval_list] by_cases hlt : s_me + (h :: t).sum < s_opp · simp only [hlt, if_true] · simp only [hlt, if_false] refine catch_up_best_attach_map_congr (h :: t) (fun y => if first = true then (catch_up_value_aux ((h :: t).toFinset.erase y) s_opp (s_me + y) false).neg else if s_me + y ≥ s_opp then (catch_up_value_aux ((h :: t).toFinset.erase y) s_opp (s_me + y) false).neg else catch_up_value_aux ((h :: t).toFinset.erase y) (s_me + y) s_opp false) (fun y => if first = true then (catch_up_eval_list n ((h :: t).erase y) s_opp (s_me + y) false).neg else if s_me + y ≥ s_opp then (catch_up_eval_list n ((h :: t).erase y) s_opp (s_me + y) false).neg else catch_up_eval_list n ((h :: t).erase y) (s_me + y) s_opp false) ?_ intro x hx have hlen' : ((h :: t).erase x).length ≤ n := by rw [List.length_erase_of_mem hx]; simp at hlen ⊢; omega simp only [catch_up_toFinset_erase hl, ih _ (hl.erase x) hlen']