catch_up_value_aux_icc_opening_one_ne_win_three
In Catch-Up on {1, 2, 3}, Player 2 does not win after Player 1 opens with 1.
Statement
theorem catch_up_value_aux_icc_opening_one_ne_win_three :
catch_up_value_aux ((Finset.Icc 1 3).erase 1) 0 1 false ≠ CatchUpOutcome.win- Source
- step towards catch_up_value_aux_icc_opening_one_ne_win (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 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…
- 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_opening_one_ne_win_iffWhen N ≥ 3, Player 2 does not win after Player 1 opens with 1 iff for every response y from {2, ..., N}, Player 1 does not lose from the…
- catch_up_value_aux_singletonIn a Catch-Up position with a single remaining piece x, current score s_me, and opponent score s_opp, the game value for the mover is win…
The proof, explained
The proof reduces Player 2's inability to win after Player 1 opens with 1 to checking that neither of Player 2's possible replies, 2 or 3, forces a loss for Player 1. In both cases, exactly one number remains, allowing the game value to be calculated directly: replying with 2 allows Player 1 to take 3 and win (4 > 2), while replying with 3 leaves Player 1 to take 2 and draw (3 = 3).
Player 2 does not win after Player 1 opens with 1 if and only if no subsequent response y ∈ {1, 2, 3} \ {1} by Player 2 forces a loss for Player 1.
Applying `catch_up_value_aux_icc_opening_one_ne_win_iff` with N = 3 (where 3 ≤ 3 is checked by `norm_num`) rewrites the goal into showing that for every valid response y available to Player 2, the resulting game is not a loss for Player 1.
uses
catch_up_value_aux_icc_opening_one_ne_win_iffrw [catch_up_value_aux_icc_opening_one_ne_win_iff 3 (by norm_num)]
Player 2's response must be either y = 2 or y = 3.
Let y be Player 2's move. Unfolding the definition of membership in {1, 2, 3} \ {1} using `Finset.mem_erase` and `Finset.mem_Icc` gives y ≠ 1 and 1 ≤ y ≤ 3. Linear integer arithmetic (`omega`) leaves only two possibilities: y = 2 or y = 3. We split into these two cases.
uses
Finset.mem_erase,Finset.mem_Iccintro y hy simp only [Finset.mem_erase, Finset.mem_Icc] at hy rcases show y = 2 ∨ y = 3 by omega with rfl | rfl
If Player 2 plays 2, Player 1 does not lose.
After removing 2, the remaining set is the singleton {3}, verified by finite evaluation (`decide`). Rewriting with `catch_up_value_aux_singleton`, Player 1 takes 3 and reaches a score of 1 + 3 = 4 against Player 2's 2. Since 4 > 2, Player 1 wins (outcome `win`), which is not a loss; `decide` closes the goal.
uses
catch_up_value_aux_singleton· have hset : ((Finset.Icc 1 3).erase 1).erase 2 = {3} := by decide rw [hset, catch_up_value_aux_singleton] decide
If Player 2 plays 3, Player 1 does not lose.
After removing 3, the remaining set is the singleton {2}, verified by `decide`. Rewriting with `catch_up_value_aux_singleton`, Player 1 takes 2 and reaches a score of 1 + 2 = 3 against Player 2's 3. Since 3 = 3, the game ends in a draw (outcome `draw`), which is not a loss; `decide` closes the goal.
uses
catch_up_value_aux_singleton· have hset : ((Finset.Icc 1 3).erase 1).erase 3 = {2} := by decide rw [hset, catch_up_value_aux_singleton] decide
catch_up_value_aux_icc_opening_one_ne_win_iff- For N ≥ 3, Player 2 does not win after Player 1 opens with 1 if and only if for every subsequent choice y ∈ {1, ..., N} \ {1} by Player 2, the game does not result in a loss for Player 1.
Finset.mem_Icc- An element x belongs to the closed discrete interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.mem_erase- An element a belongs to s \ {b} if and only if a ≠ b and a ∈ s.
catch_up_value_aux_singleton- When a single element x remains, the outcome from the current player's perspective is determined by comparing their final score s_me + x with the opponent's score s_opp: a win if s_me + x > s_opp, a loss if s_me + x < s_opp, and a draw if s_me + x = s_opp.
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.
/-- In Catch-Up on {1, 2, 3}, Player 2 does not win after Player 1 opens with 1. -/theorem catch_up_value_aux_icc_opening_one_ne_win_three : catch_up_value_aux ((Finset.Icc 1 3).erase 1) 0 1 false ≠ CatchUpOutcome.win := by rw [catch_up_value_aux_icc_opening_one_ne_win_iff 3 (by norm_num)] intro y hy simp only [Finset.mem_erase, Finset.mem_Icc] at hy rcases show y = 2 ∨ y = 3 by omega with rfl | rfl · have hset : ((Finset.Icc 1 3).erase 1).erase 2 = {3} := by decide rw [hset, catch_up_value_aux_singleton] decide · have hset : ((Finset.Icc 1 3).erase 1).erase 3 = {2} := by decide rw [hset, catch_up_value_aux_singleton] decide