= Nim heap
{c}
A <Nim heap> of size $n$ contains $n$ counters and permits removing any positive number, leaving a heap of any size $0\leq k<n$. Under the <normal-play convention>, its <Grundy number> is $n$: the reachable values are exactly $0,\ldots,n-1$, whose <mex> is $n$.
For several heaps, a turn changes exactly one heap. Their combined value is the <Nim-sum> of the heap sizes, so heaps of sizes three and three form a <losing position> even though either heap alone is winning. The ability to remove arbitrarily many counters is part of the rule; a bounded-removal <subtraction game> has different values.
Back to article page
