AFTD Auto-Formalizing Theoretical Domains

op_1600_slow_exact_nim_bounded_grundy

theoremverifiedformalization

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.

  1. 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|.

    lines 3–10

    uses List.mem_of_find?_eq_some, List.mem_range, Option.getD_some

      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
  2. 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.

    lines 15–24

    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_pow

      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
  3. 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.

    lines 30–31

    uses Nat.zero_le

      cases s with
      | zero => rw [show slow_exact_nim_grundy_comp k n 0 x = 0 from rfl]; exact Nat.zero_le _
  4. 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.

    lines 32–42

    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 x
  5. There 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.

    lines 47–48

    uses op_1600_slow_exact_nim_bounded_grundy_comp_le

      refine ⟨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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it