Paperlane

no. 14 · Friday 13 November 2026

The Sprague–Grundy Function of Slow Exact $k$-Nim with $k+1$ Piles

Vladimir Gurvich and Mariya Naumova

math.CO

Abstract

We give an explicit formula for the normal-play Sprague–Grundy (SG) function of slow exact $k$-Nim with $k+1$ piles. A move removes one stone from each of exactly $k$ nonempty piles. A truncation preserves every legal move sequence. The SG value depends only on the total of the truncated coordinates modulo $2k$, their number of odd entries, and the parities of the two smallest piles. For every $k\geq2$, the set of the SG values is $\{0,1,2,3\}$. We prove the formula by the mex characterization, including the reductions needed after boundary moves. We also prove a unit-shift identity and use it with a known optimal-move theorem to explain the four-value bound independently of the explicit formula.

fields
Combinatorics
pdf ↗ page arXiv:2611.14546 ↗