op_1600_slow_exact_nim_bounded_grundy
In the normal-play game of slow exact k-Nim on k+2 piles, for every integer k ≥ 3, the range of the Sprague-Grundy function is bounded: there exists an integer C such that every position x : Fin (k + 2) → ℕ satisfies slow_exact_nim_grundy k (k + 2) x ≤ C.
Statement
theorem op_1600_slow_exact_nim_bounded_grundy (k : ℕ) (hk : 3 ≤ k) :
∃ C : ℕ, ∀ x : Fin (k + 2) → ℕ, slow_exact_nim_grundy k (k + 2) x ≤ C- Formalizes
- arXiv:2611.14546 after Corollary 1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- slow_exact_nim_stepGiven a natural number n, a position x : Fin n → ℕ on n piles, and a subset of pile indices S : Finset (Fin n), the follower position…
- slow_exact_nim_grundy_compFor natural numbers k and n, fuel : ℕ, and position x : Fin n → ℕ, the fuel-bounded Sprague-Grundy value slow_exact_nim_grundy_comp k n…
- finset_mexThe minimum excluded natural number (mex) of a finite set of natural numbers s, defined as the smallest natural number not belonging to s.
- slow_exact_nim_followersFor natural numbers k and n and a position x : Fin n → ℕ, the finite set of legal followers slow_exact_nim_followers k n x is the set of…
Read back from the Lean
For any natural number $k$ with $k ≥ 3$, there exists a natural number bound $C$ such that for all positions $x : Fin (k + 2) → ℕ$ (representing the pile sizes of $k + 2$ piles), the Sprague-Grundy value slow_exact_nim_grundy k (k + 2) x is at most $C$. In other words, the Grundy values of slow exact $k$-nim on $k + 2$ piles are uniformly bounded.
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 establishes that the Sprague-Grundy function for slow exact k-Nim on k + 2 piles is uniformly bounded by C = 2^(k + 2). In slow exact k-Nim, a move decrements exactly k positive piles by 1, meaning that any position has at most (k + 2).choose k ≤ 2^(k + 2) valid follower positions. Because the Sprague-Grundy value is defined as the minimal excluded value (mex) over the Grundy values of all followers, and the mex of any finite set is at most its cardinality, the Grundy value can never exceed the total number of followers.
The minimal excluded value of any finite set s of natural numbers is at most |s|.
By definition, finset_mex s searches the list [0, ..., |s|] for the first element not in s, returning 0 if none is found. If no element is found (the none case), the default 0 is at most |s|. If an element y is found (the some y case), List.mem_of_find?_eq_some and List.mem_range guarantee y < |s| + 1, so simplifying with Option.getD_some and basic natural arithmetic yields y ≤ |s|.
uses
List.mem_of_find?_eq_some,List.mem_range,Option.getD_someunfold finset_mex cases h : List.find? (fun x => decide (x ∉ s)) (List.range (s.card + 1)) with | none => simp | some y => have hy : y ∈ List.range (s.card + 1) := List.mem_of_find?_eq_some h rw [List.mem_range] at hy simp only [Option.getD_some] omega
From any position x on n piles, the number of follower positions in slow exact k-Nim is at most 2^n.
Unfolding slow_exact_nim_followers shows that follower positions are obtained by choosing a k-element subset of the n piles (each with positive tokens) and subtracting 1 from each. By Finset.card_image_le, the number of followers is at most the number of valid k-subsets. By Finset.card_le_card and Finset.filter_subset, this is at most the total number of k-element subsets of an n-element set, which by Finset.card_powersetCard, Finset.card_univ, and Fintype.card_fin equals n.choose k. Finally, Nat.choose_le_two_pow bounds n.choose k by 2^n.
uses
Finset.card_image_le,Finset.card_le_card,Finset.filter_subset,Finset.card_powersetCard,Finset.card_univ,Fintype.card_fin,Nat.choose_le_two_powunfold slow_exact_nim_followers calc (Finset.image (slow_exact_nim_step x) {S ∈ Finset.powersetCard k (Finset.univ : Finset (Fin n)) | ∀ i ∈ S, 0 < x i}).card ≤ ({S ∈ Finset.powersetCard k (Finset.univ : Finset (Fin n)) | ∀ i ∈ S, 0 < x i}).card := Finset.card_image_le _ ≤ (Finset.powersetCard k (Finset.univ : Finset (Fin n))).card := Finset.card_le_card (Finset.filter_subset _ _) _ = (Finset.univ : Finset (Fin n)).card.choose k := Finset.card_powersetCard k _ _ = n.choose k := by rw [Finset.card_univ, Fintype.card_fin] _ ≤ 2 ^ n := Nat.choose_le_two_pow n k
With 0 fuel, the fuel-bounded Grundy computation slow_exact_nim_grundy_comp k n 0 x is at most 2^n.
By definition, the Grundy computation with 0 fuel returns 0. Since 0 ≤ 2^n by Nat.zero_le, the bound holds for the base case.
uses
Nat.zero_lecases s with | zero => rw [show slow_exact_nim_grundy_comp k n 0 x = 0 from rfl]; exact Nat.zero_le _
With fuel t + 1, the fuel-bounded Grundy computation slow_exact_nim_grundy_comp k n (t + 1) x is at most 2^n.
At fuel t + 1, the Grundy value is defined as the mex of the image of follower positions under the Grundy computation at fuel t. By op_1600_slow_exact_nim_bounded_grundy_mex_le_card, this mex is at most the cardinality of the image set. By Finset.card_image_le, the size of the image is at most the number of follower positions, which is at most 2^n by op_1600_slow_exact_nim_bounded_grundy_followers_card_le.
uses
op_1600_slow_exact_nim_bounded_grundy_mex_le_card,Finset.card_image_le,op_1600_slow_exact_nim_bounded_grundy_followers_card_le| succ t => rw [show slow_exact_nim_grundy_comp k n (t + 1) x = finset_mex (Finset.image (fun y => slow_exact_nim_grundy_comp k n t y) (slow_exact_nim_followers k n x)) from rfl] calc finset_mex (Finset.image (fun y => slow_exact_nim_grundy_comp k n t y) (slow_exact_nim_followers k n x)) ≤ (Finset.image (fun y => slow_exact_nim_grundy_comp k n t y) (slow_exact_nim_followers k n x)).card := op_1600_slow_exact_nim_bounded_grundy_mex_le_card _ _ ≤ (slow_exact_nim_followers k n x).card := Finset.card_image_le _ ≤ 2 ^ n := op_1600_slow_exact_nim_bounded_grundy_followers_card_le k n xThere exists an integer bound C such that every position x on k + 2 piles satisfies slow_exact_nim_grundy k (k + 2) x ≤ C.
We choose the constant C = 2^(k + 2). By definition, the Sprague-Grundy value of a position x is slow_exact_nim_grundy_comp evaluated with fuel equal to the sum of pile sizes ∑ i, x i. Applying op_1600_slow_exact_nim_bounded_grundy_comp_le with n = k + 2 and fuel s = ∑ i, x i immediately gives the desired upper bound.
uses
op_1600_slow_exact_nim_bounded_grundy_comp_lerefine ⟨2 ^ (k + 2), fun x => ?_⟩ exact op_1600_slow_exact_nim_bounded_grundy_comp_le k (k + 2) (∑ i, x i) x
List.mem_of_find?_eq_some- If searching a list for an element satisfying a predicate returns some a, then a is an element of the list.
List.mem_range- A natural number m is in List.range n if and only if m < n.
Option.getD_some- Extracting the value of some a with a fallback default returns a.
Finset.card_image_le- The cardinality of the image of a finite set under any function is at most the cardinality of the domain set.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to that of the superset.
Finset.filter_subset- Filtering a finite set by a predicate yields a subset of the original set.
Finset.card_powersetCard- The number of k-element subsets of a finite set s is equal to |s|.choose k.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The type Fin n of natural numbers strictly less than n has cardinality n.
Nat.choose_le_two_pow- For any natural numbers n and k, the binomial coefficient n.choose k is at most 2^n.
Nat.zero_le- Zero is less than or equal to any natural number.
op_1600_slow_exact_nim_bounded_grundy_mex_le_card- The minimal excluded natural number (mex) of any finite set s is at most the cardinality of s.
op_1600_slow_exact_nim_bounded_grundy_followers_card_le- From any position x on n piles in slow exact k-Nim, the number of follower positions is at most 2^n.
op_1600_slow_exact_nim_bounded_grundy_comp_le- The fuel-bounded Sprague-Grundy computation for slow exact k-Nim on n piles with fuel s is at most 2^n at any position.
- The hypothesis hk : 3 ≤ k is completely unused in the proof: the bound of 2^n on the Sprague-Grundy value holds for slow exact k-Nim on n piles for any k, n ∈ ℕ. This is because from any position, a player can choose at most n.choose k ≤ 2^n subsets of piles to decrement, and the mex of any set never exceeds its cardinality.
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 mex of a finite set of naturals is at most its cardinality. -/lemma op_1600_slow_exact_nim_bounded_grundy_mex_le_card (s : Finset ℕ) : finset_mex s ≤ s.card := by unfold finset_mex cases h : List.find? (fun x => decide (x ∉ s)) (List.range (s.card + 1)) with | none => simp | some y => have hy : y ∈ List.range (s.card + 1) := List.mem_of_find?_eq_some h rw [List.mem_range] at hy simp only [Option.getD_some] omega/-- From any position on `n` piles there are at most `2 ^ n` distinct followers. -/lemma op_1600_slow_exact_nim_bounded_grundy_followers_card_le (k n : ℕ) (x : Fin n → ℕ) : (slow_exact_nim_followers k n x).card ≤ 2 ^ n := by unfold slow_exact_nim_followers calc (Finset.image (slow_exact_nim_step x) {S ∈ Finset.powersetCard k (Finset.univ : Finset (Fin n)) | ∀ i ∈ S, 0 < x i}).card ≤ ({S ∈ Finset.powersetCard k (Finset.univ : Finset (Fin n)) | ∀ i ∈ S, 0 < x i}).card := Finset.card_image_le _ ≤ (Finset.powersetCard k (Finset.univ : Finset (Fin n))).card := Finset.card_le_card (Finset.filter_subset _ _) _ = (Finset.univ : Finset (Fin n)).card.choose k := Finset.card_powersetCard k _ _ = n.choose k := by rw [Finset.card_univ, Fintype.card_fin] _ ≤ 2 ^ n := Nat.choose_le_two_pow n k/-- The fuel-bounded Grundy value at any position on `n` piles is at most `2 ^ n`: it is a mexover the (at most `2 ^ n`) follower values. -/lemma op_1600_slow_exact_nim_bounded_grundy_comp_le (k n : ℕ) (s : ℕ) (x : Fin n → ℕ) : slow_exact_nim_grundy_comp k n s x ≤ 2 ^ n := by cases s with | zero => rw [show slow_exact_nim_grundy_comp k n 0 x = 0 from rfl]; exact Nat.zero_le _ | succ t => rw [show slow_exact_nim_grundy_comp k n (t + 1) x = finset_mex (Finset.image (fun y => slow_exact_nim_grundy_comp k n t y) (slow_exact_nim_followers k n x)) from rfl] calc finset_mex (Finset.image (fun y => slow_exact_nim_grundy_comp k n t y) (slow_exact_nim_followers k n x)) ≤ (Finset.image (fun y => slow_exact_nim_grundy_comp k n t y) (slow_exact_nim_followers k n x)).card := op_1600_slow_exact_nim_bounded_grundy_mex_le_card _ _ ≤ (slow_exact_nim_followers k n x).card := Finset.card_image_le _ ≤ 2 ^ n := op_1600_slow_exact_nim_bounded_grundy_followers_card_le k n x/-- OP-1600: Boundedness of Sprague-Grundy values for slow exact k-Nim with k+2 piles. -/theorem op_1600_slow_exact_nim_bounded_grundy (k : ℕ) (hk : 3 ≤ k) : ∃ C : ℕ, ∀ x : Fin (k + 2) → ℕ, slow_exact_nim_grundy k (k + 2) x ≤ C := by refine ⟨2 ^ (k + 2), fun x => ?_⟩ exact op_1600_slow_exact_nim_bounded_grundy_comp_le k (k + 2) (∑ i, x i) x