run_grundy_zero
For any boundary conditions α and β, a run of length 0 in the Game of Arrows has Grundy value 0.
Statement
theorem run_grundy_zero (α β : RunBoundary) :
run_grundy 0 α β = 0- Source
- scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md:441
- Verified
- 21 Oct 2026
- Axioms
Quot.soundpropext- Built on 5
- run_grundy_auxThe auxiliary Grundy value function for a run of length k with boundary conditions α and β in the Game of Arrows, computed by recursion up…
- run_move_legalIn a run of length k with boundary conditions α and β, orienting edge j in direction δ is legal if and only if (j ≠ 1 or α ∈ {free, δ})…
- run_grundyThe Grundy value of a run of length k with boundary conditions α and β in the Game of Arrows, defined using depth bound k + 1.
- RunBoundaryThe boundary condition at an end of a path segment in the Game of Arrows is either free (denoted *), blocked inward (denoted →), or…
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
Read back from the Lean
For all boundary conditions α and β of type RunBoundary, run_grundy 0 α β equals 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof unfolds the definition of `run_grundy` for a run of length 0, reducing the goal to evaluating `run_grundy_aux 1 0 α β`. By the definitional equation of `run_grundy_aux`, when the run length is 0, no moves are available and the function immediately evaluates to 0. The simplification tactic applies these two definitions to reduce both sides to 0 and completes the proof.
$\mathrm{run\_grundy}\,0\,\alpha\,\beta = 0$
Unfolding the definition of $\mathrm{run\_grundy}$ rewrites $\mathrm{run\_grundy}\,0\,\alpha\,\beta$ to $\mathrm{run\_grundy\_aux}\,1\,0\,\alpha\,\beta$. Applying the defining equation $\mathrm{run\_grundy\_aux.eq\_def}$ evaluates the outer match on $n = 1$ and triggers the $k = 0$ branch, which immediately yields $0$. The simplifier reduces the equality to $0 = 0$ and closes the goal.
uses
run_grundy,run_grundy_aux.eq_defsimp [run_grundy, run_grundy_aux.eq_def]
run_grundy- Defines the Grundy value of a run of length $k$ with boundary conditions $\alpha$ and $\beta$ as $\mathrm{run\_grundy\_aux}\,(k + 1)\,k\,\alpha\,\beta$.
run_grundy_aux.eq_def- The defining equation for $\mathrm{run\_grundy\_aux}$, stating that $\mathrm{run\_grundy\_aux}\,n\,k\,\alpha\,\beta$ evaluates to $0$ when $n = 0$ or $k = 0$, and otherwise recursively computes the mex of the values of all legal moves.
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.
/-- The Grundy value of an empty run (length 0) is 0 for all boundary conditions. -/theorem run_grundy_zero (α β : RunBoundary) : run_grundy 0 α β = 0 := by simp [run_grundy, run_grundy_aux.eq_def]