catch_up_value_aux_icc_erase_max_ne_loss_iff
After Player 1 opens with N in Catch-Up on {1, ..., N} with even triangular sum and N > 0, every response y satisfies y < N, so Player 2 does not lose iff there is a response y such that Player 2 does not lose from the resulting position with scores (y, N).
Statement
theorem catch_up_value_aux_icc_erase_max_ne_loss_iff (N : ℕ) (hN : 0 < N)
(h_even : Even (N * (N + 1) / 2)) :
catch_up_value_aux ((Finset.Icc 1 N).erase N) 0 N false ≠ CatchUpOutcome.loss ↔
∃ y ∈ (Finset.Icc 1 N).erase N,
catch_up_value_aux (((Finset.Icc 1 N).erase N).erase y) y N false ≠ CatchUpOutcome.loss- Source
- step towards catch_up_value_aux_icc_after_opening_ne_loss (Catch-Up conjecture (Catch-Up: A Game in Which the Lead Alternates, 2015, Sec. 3.1))
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
- 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…
The proof, explained
The theorem characterizes when Player 2 avoids losing after Player 1 opens with the maximum tile N. It specializes the general response theorem catch_up_value_aux_icc_erase_ne_loss_iff to x = N. Because every remaining response tile y satisfies y ≤ N and y ≠ N, one always has y < N; hence the condition y ≥ N never holds, and the branching outcome simplifies directly to Player 2 not losing from the resulting score position (y, N).
Player 2 avoids a loss after opening move N if and only if there exists a response y ∈ {1, ..., N} \ {N} satisfying the general conditional outcome formula against N.
Because 0 < N and N ≤ N, N belongs to {1, ..., N} (established as hN_mem). We can therefore rewrite the non-loss condition using the general theorem catch_up_value_aux_icc_erase_ne_loss_iff specialized to opening move x = N.
uses
Finset.mem_Icc.mpr,le_rfl,catch_up_value_aux_icc_erase_ne_loss_iffhave hN_mem : N ∈ Finset.Icc 1 N := Finset.mem_Icc.mpr ⟨hN, le_rfl⟩ rw [catch_up_value_aux_icc_erase_ne_loss_iff N h_even N hN_mem]
It suffices to show that for any response y ∈ {1, ..., N} \ {N}, the conditional outcome formula against N is equivalent to Player 2 not losing from score position (y, N).
By exists_congr, equivalence of the two existential statements reduces to equivalence of their predicates for any response y. Then and_congr_right reduces this further: assuming y belongs to {1, ..., N} \ {N}, it suffices to show that the if-then-else condition simplifies to the desired non-loss condition.
uses
exists_congr,and_congr_rightapply exists_congr intro y apply and_congr_right intro hy
For any response y ∈ {1, ..., N} \ {N}, the condition y ≥ N is false, simplifying the conditional outcome to the non-loss condition from (y, N).
Unfolding membership in {1, ..., N} \ {N} shows y ≠ N and y ≤ N, which implies y < N and therefore ¬(y ≥ N). Applying if_neg with this fact selects the else branch of the conditional, which is identically the claim that Player 2 does not lose from scores (y, N).
uses
Finset.mem_erase,Finset.mem_Icc,not_le_of_gt,lt_of_le_of_ne,if_negrw [Finset.mem_erase, Finset.mem_Icc] at hy have h_not : ¬(y ≥ N) := not_le_of_gt (lt_of_le_of_ne hy.2.2 hy.1) rw [if_neg h_not]
catch_up_value_aux_icc_erase_ne_loss_iff- In Catch-Up on {1, ..., N} with an even sum, Player 2 does not lose after opening move x iff there is a response y such that: if y ≥ x the continuation from scores (x, y) is not a win, and if y < x the continuation from scores (y, x) is not a loss.
Finset.mem_Icc.mpr- An element x belongs to the closed discrete interval {a, ..., b} if a ≤ x and x ≤ b.
le_rfl- Every element is less than or equal to itself (reflexivity of ≤).
exists_congr- Two existential propositions ∃ a, p a and ∃ a, q a are equivalent if p a ↔ q a for all a.
and_congr_right- Conjunctions a ∧ b and a ∧ c are equivalent if b ↔ c holds assuming a.
Finset.mem_erase- An element a belongs to s \ {b} if and only if a ≠ b and a ∈ s.
Finset.mem_Icc- An element x belongs to {a, ..., b} if and only if a ≤ x and x ≤ b.
not_le_of_gt- If a < b, then b ≤ a is false.
lt_of_le_of_ne- If a ≤ b and a ≠ b in a partial order, then a < b.
if_neg- A conditional expression if c then t else e simplifies to e when c is false.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- After Player 1 opens with N in Catch-Up on {1, ..., N} with even triangular sum and N > 0, every response y satisfies y < N, so Player 2 does not lose iff there is a response y such that Player 2 does not lose from the resulting position with scores (y, N). -/theorem catch_up_value_aux_icc_erase_max_ne_loss_iff (N : ℕ) (hN : 0 < N) (h_even : Even (N * (N + 1) / 2)) : catch_up_value_aux ((Finset.Icc 1 N).erase N) 0 N false ≠ CatchUpOutcome.loss ↔ ∃ y ∈ (Finset.Icc 1 N).erase N, catch_up_value_aux (((Finset.Icc 1 N).erase N).erase y) y N false ≠ CatchUpOutcome.loss := by have hN_mem : N ∈ Finset.Icc 1 N := Finset.mem_Icc.mpr ⟨hN, le_rfl⟩ rw [catch_up_value_aux_icc_erase_ne_loss_iff N h_even N hN_mem] apply exists_congr intro y apply and_congr_right intro hy rw [Finset.mem_erase, Finset.mem_Icc] at hy have h_not : ¬(y ≥ N) := not_le_of_gt (lt_of_le_of_ne hy.2.2 hy.1) rw [if_neg h_not]