TOPICS
Search

Slow Exact k-Nim


Slow exact k-Nim is a two-player pile game in which a move removes exactly one counter from each of exactly k nonempty piles (Gurvich and Ho 2015, Gurvich and Naumova 2026). Under normal play, a player with no legal move loses. This differs from Nim, where a move can remove several counters from a single pile.

For k>=2 and n=k+1 piles, Gurvich and Naumova (2026) gave an explicit formula for the nim-value G_k(x) of every position. Sort the nonnegative pile sizes as x_1<=...<=x_n, put P_j=x_1+...+x_j, and define

 L=min_(2<=j<=n)|_(P_j)/(j-1)_|,
(1)

where |_x_| is the floor function. Replace x_i by y_i=min{x_i,L}, put s=(sum_(i)y_i)mod2k, and let o count the odd y_i. The residues s=k-1 and s=2k-1 give G_k(x)=0 and G_k(x)=1, respectively. For every other residue put r=min{s,2k-2-s}. Then

 G_k(x)={0   if o<=r; 1   if o>=r+4; 1   if o=r+2 and y_1 is even; 2   if o=r+2 and y_1,y_2 are odd; 3   if o=r+2, y_1 is odd, and y_2 is even.
(2)

Thus the range is exactly {0,1,2,3} for every k>=2. The truncation preserves all legal move sequences, and L is also the maximum length of play. The formula uses linearly many arithmetic operations once the pile sizes are sorted.

Adding one counter to every pile except a smallest pile changes G_k(x) to G_k(x)+(-1)^(G_k(x)). In particular, adding this shift twice preserves the nim-value. For slow exact 4-Nim with five piles, (1,2,3,3,m) has nim-value 3 for every m>=3, correcting an earlier reported value of 5 (Gurvich and Naumova 2026). The authors report ChatGPT assistance with computation and development of the mathematical arguments.


See also

Nim, Nim-Value

Explore with Wolfram|Alpha

References

Gurvich, V. and Ho, N. B. "Slow k-Nim." 24 Aug 2015. https://arxiv.org/abs/1508.05777v1.Gurvich, V. and Naumova, M. "The Sprague-Grundy Function of Slow Exact k-Nim with k+1 Piles." 27 Oct 2026. https://arxiv.org/abs/2611.14546v1.

Cite this as:

Weisstein, Eric W. "Slow Exact k-Nim." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SlowExactk-Nim.html

Subject classifications