Chapter 131

Home

Nim Games and Grundy Numbers

Nim is the simplest impartial combinatorial game: piles of stones, players take any number from one pile. The XOR of all pile sizes (nim-sum) determines the winner — non-zero = first player wins. This generalises to all impartial games via Grundy numbers.

Nim

C++ — Nim winner

bool nim_winner(vector& piles) {
    long long xor_sum = 0;
    for (long long p : piles) xor_sum ^= p;
    return xor_sum != 0;  // first player wins
}

// Grundy number for a Nim heap of size n: g(n) = n
// For general impartial games, compute mex of reachable Grundy numbers.