Sprague-Grundy-Values of Additively Periodic Nim-Games

Let g : _{0}^{2} → _{0} be the Grundy function of a Nim-Game which constellations are unique characterized by a pair of natural numbers. Hint for the reader: The set operators \ and ˙∪ are leftassociative.

∀ i, j ∈ _{0} : P_{i,j} := {(h, k) | h, k ∈ _{0} ∃ move(i, j) to (h, k) in the Nim-Game}

Now consider only Nim-Games for which is valid: ∀ i, j ∈ _{0} : ∥P_{i,j}∥ < ∞ and ∀ h < j : (i, h) ∈ P_{i,j} and ∀ h ≥ j : (i, h) ∉ P_{i,j} and ∀ h > i : (h, j) ∉ P_{i,j} Then we bisect P_{i,j} and the corresponding Grundy values into two sets: P_{i,j} = {(i, k) | 0 ≤ k < j} ˙∪ Q_{i,j} with Q_{i,j} := {(h, k) | 0 ≤ h < i , (h, k) ∈ P_{i,j}} G_{i,j} := {g(i, k) | 0 ≤ k < j} H_{i,j} := {g(h, k) | (h, k) ∈ Q_{i,j}} and we can represent the Grundy function by g(i, j) := min _{0} \ G_{i,j} \ H_{i,j}

Remark: By induction over j we get immediatly: ∀ j ∈ _{0} : g(0, j) = j. Trivially from the definition of g(i, j) follows ∀ j, k ∈ _{0} : g(i, j) = g(i, k) ⇒ j = k . Or for each i ∈ _{0} and each q ∈ _{0} exists at most one j ∈ _{0} : g(i, j) = q. Therefore ∀ i ∈ _{0} : ∥G_{i,j}∥ = j.

The next restriction is, we demand that Q_{i,j} is additively periodic in j :⇔ ∀ i ∈ ∃ v ∈ _{0} ∃ p ∈ ∀ j ≥ v : (h, k) ∈ Q_{i,j} ⇒ (h, k + p) ∈ Q_{i,j+p} Let r(i) be the minimal such p . This implies ∀ i ∈ ∃ n(i) ∀ k ≥ v(i) : n(i) = ∑_{j=k}^{k+r−1} ∥Q_{i,j}∥ .

For Wythoff’s Game: ∀ i, j ∈ _{0} : ∥P_{i,j}∥ = i + j + min{i, j} and n(i) = 2i and r(i) = 1 , v(i) = i .

Because of the additive periodicity and the finiteness of Q_{i,j} we have: ∀ i, q ∈ _{0} ∃ j ∈ _{0} : q = g(i, j) . Or formulated differently, for each i each set G_{i} := {g(i, k) | k ∈ _{0}} is a permutation of _{0}.

Also from the definition of g(i, j) and the cardinalities of G_{i,j} and H_{i,j} it follows ∀ i, j ∈ _{0} : g(i, j) ≤ ∥G_{i,j}∥ + ∥H_{i,j}∥ = j + ∥H_{i,j}∥ ≤ j + ∥Q_{i,j}∥ ≤ j + n(i).

Now we want to derive a lower bound of g(i, j) depending on i and j. Assume g(i, j) < j and define q := g(i, j). Make a dissection of G_{i,j} using q as split index namely A := G_{i,q} ˙∪ B := {g(i, k)|q ≤ k < j}. Now bisect A in A^{−} := {g(i, k) | k < q , g(i, k) < q} and A^{+} := {g(i, k) | k < q , g(i, k) > q}, and bisect B in B^{−} := {g(i, k) | q ≤ k < j , g(i, k) < q} and B^{+} := {g(i, k) | q ≤ k < j , g(i, k) > q}.

Notice ∀ k < j with g(i, k) > g(i, j) ∃ (h, l) ∈ Q_{i,k} : g(h, l) = g(i, j) and ∥A^{−}∥+∥B^{−}∥ ≤ ∥{g(i, k) | g(i, k) < q}∥ = q = ∥A^{−}∥+∥A^{+}∥ ⇒ ∥B^{−}∥ ≤ ∥A^{+}∥.

Now we have ∥B∥ = j −q = ∥B^{+}∥+∥B^{−}∥ ≤ ∥B^{+}∥+∥A^{+}∥ ≤ ∑_{j=k}^{k+r−1} ∥H_{i,j}∥ ≤ n(i). Therefore ∀ i, j ∈ _{0} : j − n(i) ≤ g(i, j) and we get Theorem 1: ∀ i, j ∈ _{0} : j − n(i) ≤ g(i, j) ≤ j + n(i) and the corollary: ∀ i ∈ _{0} : ∥{ g(i, j) − j | j ∈ _{0} }∥ ≤ 2 ∑_{j=k}^{k+r−1} ∥H_{i,j}∥ + 1 ≤ 2n(i) + 1 < ∞.

Next we want to show by induction over i that g(i, j) is additively periodic in j for each fixed i ∈ _{0}. Precisely: ∀ i ∈ _{0} ∃v(i), p(i) ∈ _{0} ∀ j > v(i) : g(i, j + p(i)) = p(i) + g(i, j) and p(i) > 0.

Let v_{min}(i) := min {v ∈ _{0} | ∃p ∈ ∀ j > v : g(i, j + p) = p + g(i, j)}

p_{min}(i) := min {p ∈ | ∀ j > v_{min}(i) : g(i, j + p) = p + g(i, j)} = gcd {p ∈ | ∀ j > v_{min}(i) : g(i, j + p) = p + g(i, j)}

Let i be 0. Now g(0, j) − j = 0 ⇒ p_{min}(0) = 1, v_{min}(0) = 0.

Using the definition of g(i, j) we can state with J_{n,j} := {j− n(i), j− n(i)+ 1, …, j, …, j+ n(i)− 1, j+ n(i)} ∩ _{0} and T_{i,j} := J_{n,j} \ G_{i,j} that g(i, j) = min T_{i,j} \ H_{i,j} .

Now remember that ∀i ∈ _{0} G_{i} is a permutation of _{0} and with Theorem 1 follows j − n(i) ∈ G_{i,j+1} so we get T_{i,j+1} = T_{i,j} ˙∪ {j+ n(i)+ 1} \ {g(i, j)} .

Notice: ∀ j ∈ _{0} : ∥T_{i,j}∥ = n(i)+ 1 , but the largest element is always j+ n(i). This implies there are at most \binom{2n(i)}{n(i)} different sets T_{i,j} − j for fixed i.

Given ∀h < i ∀k ∈ _{0} the values g(h, k) and ∀h < j the values g(i, h). Regard the successive calculation of the r values g(i, j), g(i, j+1), …, g(i, j+r−1). This defines implicit an unique mapping f_{i,j} by the r sets H_{i,j}, H_{i,j+1}, …, H_{i,j+r−1} from T_{i,j} − j → T_{i,j} − j ⊂ { −n(i), −n(i)− 1, …, n(i) } .

By induction assumption ∀ h < i : g(h, j) is additively periodic in j.

p̄(i) := lcm {p_{min}(h) | 0 ≤ h < i}

v̄(i) − i := max {v_{min}(h) − h | 0 ≤ h < i}

If we look at an index j > v̄(i) then follows ∀ h < i from the additively periodicity of g(h, j) and of Q_{i,j} that of H_{h,j} with the common period p̄(i). This implies that iterating f_{i} m+1 fold we will get the p̄ values of g(i, j + mp̄), g(i, j + mp̄ + 1), …, g(i, j +mp̄+p̄−1). Because f_{i} is a mapping on a finite set, it will be caught in a cycle after at most \binom{2n(i)}{n(i)} iterations.

Now we can formulate Theorem 2 : ∀ i ∈ _{0} : g(i, j) is additively periodic with p_{min}(i) ≤ 2^{2n(i)}p_{min}(i − 1) ; with p_{min}(0) = 1, and

v_{min}(i) is bounded by v_{min}(i − 1) + 2^{2n(i)}(p_{min}(i) − 1) ; with v_{min}(0) = 0.

Exercise for the reader: Prove that for Wythoff’s Game: ∀ i, j ∈ _{0} : g(i, j) ≤ j +i. Conclude from this fact that ∀ i ∈ _{0} : p_{min}(i) ≤ \binom{3i}{i}p_{min}(i − 1).

It follows a table of values of i, p_{min}(i), v_{min}(i) ∀ i < 100 .

4. Version of 7. Mai 1993