catch_up_sum_icc_erase_ge
theoremverified
In {1, ..., N} with even triangular sum, removing any element x leaves a sum at least x.
Statement
theorem catch_up_sum_icc_erase_ge (N : ℕ) (h_even : Even (N * (N + 1) / 2))
(x : ℕ) (hx : x ∈ Finset.Icc 1 N) :
x ≤ ∑ y ∈ (Finset.Icc 1 N).erase x, y- 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 1
- catch_up_sum_icc_idThe sum of numbers in the interval {1, ..., N} equals the N-th triangular number N(N+1)/2.
- Used by 1
- catch_up_value_aux_icc_erase_ne_loss_iffAfter Player 1 opens with x from {1, ..., N} (with even triangular sum), Player 2 does not lose if and only if there exists a response…
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.
/-- For any N with even triangular number and any x in {1, ..., N}, the sum of the remaining elements {1, ..., N} \ {x} is at least x. -/theorem catch_up_sum_icc_erase_ge (N : ℕ) (h_even : Even (N * (N + 1) / 2)) (x : ℕ) (hx : x ∈ Finset.Icc 1 N) : x ≤ ∑ y ∈ (Finset.Icc 1 N).erase x, y := by have hx_le : x ≤ N := (Finset.mem_Icc.mp hx).2 have hN : 3 ≤ N := by rcases N with _ | _ | _ | N' · have := (Finset.mem_Icc.mp hx).1 omega · revert h_even; decide · revert h_even; decide · omega have h_le : 2 * x ≤ N * (N + 1) / 2 := by have : 4 * N ≤ N * (N + 1) := by calc 4 * N ≤ (N + 1) * N := Nat.mul_le_mul_right N (by omega) _ = N * (N + 1) := mul_comm (N + 1) N omega have h_sum : x + ∑ y ∈ (Finset.Icc 1 N).erase x, y = N * (N + 1) / 2 := by rw [← catch_up_sum_icc_id N] exact Finset.add_sum_erase (Finset.Icc 1 N) (fun y => y) hx omega