catch_up_value_aux_ne_draw_of_odd_sum
theoremverifiedformalization
In Catch-Up, if the sum of remaining piece values and player scores is odd, the mover cannot achieve a draw.
Statement
theorem catch_up_value_aux_ne_draw_of_odd_sum (remaining : Finset ℕ) (s_me s_opp : ℕ) (isFirstMove : Bool) (h_odd : Odd (remaining.sum (fun x => x) + s_me + s_opp)) : catch_up_value_aux remaining s_me s_opp isFirstMove ≠ CatchUpOutcome.draw
- Formalizes
- Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Sec. 2.6 and Appendix 5.1 (an odd total cannot be split evenly, so no draw); stated for arbitrary positions (scores plus remaining sum odd)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_outcome_best_eq_drawUnder Catch-Up's best-outcome aggregation on a list of outcomes, the aggregated outcome is a draw if and only if no win appears in the…
- catch_up_outcome_neg_eq_draw_iffNegating an outcome yields a draw if and only if the original outcome is a draw.
- catch_up_sum_invariantIn any Catch-Up position, picking a piece x from remaining preserves the total sum of remaining pieces and both players' scores.
- catch_up_score_diff_odd_of_odd_sumIf the sum T of player scores satisfies s_me + s_opp = T and T is odd, then the final score difference (s_me : ℤ) - (s_opp : ℤ) is an odd…
- CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
- Used by 1
- catch_up_value_ne_draw_of_odd_sumFor any finite set S of natural numbers whose sum is odd, the game value catch_up_value S is not a draw.
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 any Catch-Up position, if the total sum of remaining pieces and both player scores is odd, the game value cannot be a draw. -/theorem catch_up_value_aux_ne_draw_of_odd_sum (remaining : Finset ℕ) (s_me s_opp : ℕ) (isFirstMove : Bool) (h_odd : Odd (remaining.sum (fun x => x) + s_me + s_opp)) : catch_up_value_aux remaining s_me s_opp isFirstMove ≠ CatchUpOutcome.draw := by rw [catch_up_value_aux.eq_def] by_cases hr : remaining = ∅ · subst hr simp only [Finset.sum_empty, zero_add] at h_odd rcases h_odd with ⟨k, hk⟩ simp only [ite_true] split_ifs · intro h; cases h · intro h; cases h · intro _ omega · simp only [hr, ite_false] by_cases h_lt : s_me + ∑ x ∈ remaining, x < s_opp · simp only [h_lt, ite_true] intro h; cases h · simp only [h_lt, ite_false] intro h_draw rw [catch_up_outcome_best_eq_draw] at h_draw obtain ⟨-, h_in⟩ := h_draw rw [List.mem_map] at h_in obtain ⟨⟨x, hx⟩, -, h_eq⟩ := h_in dsimp at h_eq have h_sum_inv := catch_up_sum_invariant remaining x s_me s_opp hx split_ifs at h_eq · rw [catch_up_outcome_neg_eq_draw_iff] at h_eq have h_odd' : Odd ((remaining.erase x).sum (fun y => y) + s_opp + (s_me + x)) := by have : (remaining.erase x).sum (fun y => y) + s_opp + (s_me + x) = (remaining.erase x).sum (fun y => y) + (s_me + x) + s_opp := by omega rw [this, h_sum_inv] exact h_odd exact catch_up_value_aux_ne_draw_of_odd_sum (remaining.erase x) s_opp (s_me + x) false h_odd' h_eq · rw [catch_up_outcome_neg_eq_draw_iff] at h_eq have h_odd' : Odd ((remaining.erase x).sum (fun y => y) + s_opp + (s_me + x)) := by have : (remaining.erase x).sum (fun y => y) + s_opp + (s_me + x) = (remaining.erase x).sum (fun y => y) + (s_me + x) + s_opp := by omega rw [this, h_sum_inv] exact h_odd exact catch_up_value_aux_ne_draw_of_odd_sum (remaining.erase x) s_opp (s_me + x) false h_odd' h_eq · have h_odd' : Odd ((remaining.erase x).sum (fun y => y) + (s_me + x) + s_opp) := by rw [h_sum_inv] exact h_odd exact catch_up_value_aux_ne_draw_of_odd_sum (remaining.erase x) (s_me + x) s_opp false h_odd' h_eqtermination_by remaining.carddecreasing_by all_goals exact Finset.card_erase_lt_of_mem hx