nimsum

Nimsum, or nim-sum, is the bitwise exclusive OR (XOR) of the pile sizes in the impartial combinatorial game Nim. It represents the nimber or Sprague-Grundy value of a Nim position and is used to determine optimal play: with standard Nim rules, a position is losing for the next player if and only if the nim-sum is zero.

Calculation is done by writing each pile size in binary and computing the XOR across all piles. For example, piles of sizes 3, 4, and 5 have nim-sum 3 XOR 4 XOR 5 = (3 XOR 4) XOR 5 = 7 XOR 5 = 2. Since 2 is nonzero, the position is winning for the player to move under optimal play.

Strategy follows from the nim-sum value. If the nim-sum is nonzero, there exists a move that makes the nim-sum zero by reducing one pile from a_i to a_i' = a_i XOR nim-sum, which is always smaller than a_i for at least one pile. After making such a move, the nim-sum becomes zero, placing the opponent in a losing position under standard Nim. If the nim-sum is zero, any legal move changes it to a nonzero value, giving the opponent a winning position.

Variations and broader context: In misère Nim, the nim-sum technique still informs analysis, but the endgame strategy changes when all remaining piles have size one. The nimsum remains the XOR of pile sizes and, within Sprague-Grundy theory, corresponds to the nimber of the position. The concept is central to understanding Nim and related impartial games.

See also Nim, Sprague-Grundy theorem, misère Nim.