AFTD Auto-Formalizing Theoretical Domains

op_1600_slow_exact_nim_k3_ones

theoremverifiedformalization

In slow exact 3-Nim on 5 piles, the all-ones position fun _ : Fin 5 => 1 has Sprague-Grundy value 1.

Statement

theorem op_1600_slow_exact_nim_k3_ones :
    slow_exact_nim_grundy 3 5 (fun _ : Fin 5 => 1) = 1
Formalizes
arXiv:2611.14546 after Corollary 1
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • slow_exact_nim_grundyThe Sprague-Grundy value slow_exact_nim_grundy k n x of a position x : Fin n → ℕ in slow exact k-Nim on n piles is defined as…

Read back from the Lean

The Grundy value slow_exact_nim_grundy 3 5 (fun _ : Fin 5 => 1) of the exact Nim game with parameter $k = 3$, $n = 5$ piles, and each pile having size 1, is equal to 1.

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 statement asserts that the Sprague-Grundy value of the state with one token on each of five piles in slow exact 3-Nim is 1. Because the Sprague-Grundy function is defined computably using fuel bounded by the total token count, the identity can be verified entirely by evaluation. The reflexivity tactic `rfl` triggers this definitional reduction in Lean's kernel, computing the follower states and their minimum excludant directly.

  1. The Sprague-Grundy value of the configuration $(1, 1, 1, 1, 1)$ in slow exact $3$-Nim on $5$ piles is $1$.

    The Sprague-Grundy function `slow_exact_nim_grundy` is defined recursively using the total number of tokens as fuel. From the state $(1, 1, 1, 1, 1)$, a valid move must decrement exactly $k = 3$ non-empty piles by $1$. Every such move leads to a configuration with two $1$s and three $0$s. From any such follower position, no legal move can be made because fewer than $3$ non-empty piles remain; hence their follower sets are empty and their Sprague-Grundy value is $\operatorname{mex}(\emptyset) = 0$. The follower values from the initial state therefore form the singleton set $\{0\}$, whose minimum excludant is $\operatorname{mex}(\{0\}) = 1$. Lean evaluates this entire finite computation definitionally via reflexivity (`rfl`).

    line 4

      rfl

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

/-- Sprague-Grundy value of the all-ones position in slow exact 3-Nim on 5 piles is 1. -/theorem op_1600_slow_exact_nim_k3_ones :    slow_exact_nim_grundy 3 5 (fun _ : Fin 5 => 1) = 1 := by  rfl
See it in the graphDiscuss this resultChallenge it