Grundy Numbers & the Sprague–Grundy Theorem

Grundy(state) = mex({ Grundy(s') | s' is a valid move from state })

Where mex(S) = Minimum EXcluded non-negative integer in set S

Examples:
  mex({})        = 0   (empty set — smallest missing is 0)
  mex({0})       = 1   (0 is present, 1 is missing)
  mex({[0, 1]})    = 2   (0 and 1 present, 2 is missing)
  mex({[0, 1, 2]}) = 3   (0, 1, 2 present, 3 is missing)
  mex({[0, 2]})    = 1   (1 is missing even though 2 is present)
  mex({[1, 2, 3]}) = 0   (0 is missing!)

THEOREM: Any impartial game G composed of independent sub-games
G1, G2, ..., Gk can be analyzed as follows:

1. Compute Grundy(Gi) for each sub-game independently
2. Nim-sum = Grundy(G1) ⊕ Grundy(G2) ⊕ ... ⊕ Grundy(Gk)
3. If Nim-sum ≠ 0 → N-position (winning for current player)
4. If Nim-sum = 0 → P-position (losing for current player)

In other words: G ≅ Nim heap of size Grundy(G)

The XOR rule from standard Nim GENERALIZES to any impartial game!
This is the MOST IMPORTANT theorem in combinatorial game theory.

// Subtraction game: remove 1 or 2 stones (standard take-away)

Grundy(0) = mex({}) = 0           // Terminal state — no moves
Grundy(1) = mex({G(0)})          // Can move to 0
          = mex({0}) = 1
Grundy(2) = mex({G(1), G(0)})    // Can move to 1 or 0
          = mex({[1, 0]}) = 2
Grundy(3) = mex({G(2), G(1)})    // Can move to 2 or 1
          = mex({[2, 1]}) = 0       // 0 is missing!
Grundy(4) = mex({G(3), G(2)})    // Can move to 3 or 2
          = mex({[0, 2]}) = 1
Grundy(5) = mex({G(4), G(3)})
          = mex({[1, 0]}) = 2

Pattern: Grundy(n) = n % 3 for {[1, 2]} subtraction game

// Grundy's Game — Computing Grundy numbers

function computeGrundy(maxN) {
  const grundy = new Array(maxN + 1).fill(0);

  for (let n = 1; n <= maxN; n++) {
    const reachable = new Set();

    // Try all possible unequal splits
    for (let a = 1; a < n; a++) {
      const b = n - a;
      if (a !== b) {
        // Splitting n into (a, b) gives XOR of Grundy(a) and Grundy(b)
        reachable.add(grundy[a] ^ grundy[b]);
      }
    }

    // mex: find smallest non-negative not in reachable
    let g = 0;
    while (reachable.has(g)) g++;
    grundy[n] = g;
  }

  return grundy;
}

// Grundy(0) = 0, G(1) = 0, G(2) = 0 (no valid splits)
// G(3) = mex({G(1)⊕G(2)}) = mex({0⊕0}) = mex({0}) = 1
// G(4) = mex({G(1)⊕G(3)}) = mex({0⊕1}) = mex({1}) = 0
// (G(2)⊕G(2) is invalid — equal split not allowed)
// G(5) = mex({G(1)⊕G(4), G(2)⊕G(3)})
//      = mex({0⊕0, 0⊕1}) = mex({[0, 1]}) = 2
// Pattern: Grundy(n) = ? (depends on n, see diagram above)	

function grundysGame(n) {
  // Precompute Grundy numbers
  const grundy = computeGrundy(n);
  // Initial state: one heap of size n
  // Grundy of the whole game = Grundy(n)
  return grundy[n] !== 0 ? "First" : "Second";
}

// Since the game starts with ONE heap, Grundy(n) = 0 means
// the first player LOSES. Grundy(n) ≠ 0 means first player WINS.
// From the table above: G(8) = 2 → First player wins!

// Chalkboard XOR Game — Optimal Strategy

function chalkboardXORGame(nums, k) {
  // Count frequencies of each number
  const freq = new Map();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }

  // Alice needs pairs of equal numbers. Bob needs pairs (a, a⊕k).
  // The key insight: Alice can ALWAYS erase equal pairs UNLESS
  // every number appears exactly once (no pairs at all).
  //
  // But Bob can also create equal pairs by erasing complementary pairs!
  // If Alice erases (a, a), Bob might erase (b, b⊕k) which were previously
  // separated. The game reduces to a parity argument.

  // If n is ODD: Alice starts and will take the last move?
  // Actually, since each move removes 2 numbers, if the board starts
  // with n numbers, there are exactly n/2 turns total.
  // Alice makes turns 1, 3, 5, ... (odd turns)
  // Bob makes turns 2, 4, 6, ... (even turns)
  //
  // The player who makes the LAST move wins.
  // If n/2 is odd → Alice makes the last move → Alice wins (if all pairs found)
  // If n/2 is even → Bob makes the last move → Bob wins

  // But it's more nuanced — optimal play can shorten the game.
  // Alice's best strategy: erase numbers that Bob could pair with.
  // Bob's best strategy: create situations where Alice has no equal pairs.

  // The proven solution:
  // Alice wins if she can pair ALL numbers before Bob can trap her.
  // Since numbers are removed in pairs, the total moves = n/2.
  // Alice wins iff she makes the last move.
  // She makes the last move iff the total number of moves is ODD.
  //
  // But under optimal play, if k is chosen adversarially...
  // For any k, Alice wins if n is even and has equal pairs available
  // on her first turn. Otherwise Bob wins.

  // Simplified winning condition:
  // If there are any equal pairs → Alice can start → Alice wins
  // If no equal pairs exist → Alice loses immediately
  for (const count of freq.values()) {
    if (count >= 2) return "First"; // Alice wins
  }
  return "Second"; // Bob wins
}

// More formally: Alice wins iff the initial array has at least
// one pair of equal numbers. Because:
// 1. Alice erases an equal pair
// 2. Bob must find an XOR pair among remaining numbers
// 3. If Bob can't find one, Bob loses immediately
// 4. If Bob erases a pair, the game continues
// 5. Alice will always have at least one equal pair as long as
//    the total count is even and she plays optimally

// Stone Division I: split heap of n into (n/d) heaps of size d
// where d is a divisor of n, d > 1, and n/d ≥ 2

function stoneDivisionI(n) {
  const grundy = new Array(n + 1).fill(0);

  for (let size = 1; size <= n; size++) {
    const reachable = new Set();

    // Try each divisor d > 1 of 'size'
    for (let d = 2; d <= size; d++) {
      if (size % d === 0) {
        const k = size / d;  // number of heaps created
        if (k >= 2) {
          // XOR of k copies of Grundy(d)
          // If k is even: k copies XOR = 0
          // If k is odd: k copies XOR = Grundy(d)
          const xorVal = (k % 2 === 0) ? 0 : grundy[d];
          reachable.add(xorVal);
        }
      }
    }

    // mex
    let g = 0;
    while (reachable.has(g)) g++;
    grundy[size] = g;
  }

  return grundy[n] !== 0 ? "First" : "Second";
}

// Insight: When k is EVEN, the XOR of k copies of Grundy(d) is ALWAYS 0.
// So if n/d is even, that move always gives XOR = 0 in the reachable set.
// This means Grundy(n) can never be 0 if there's an even divisor move!
// (Because 0 is in the reachable set, so mex ≠ 0)

// Stone Division II: split heap of size n into k heaps of size d
// where d divides n, d < n, and k = n/d ≥ 2
// The KEY difference: you can choose ANY k ≥ 2, not just k = n/d.
// But actually in both versions, k IS determined by d: k = n/d.
// The difference is in WHAT moves are allowed.
//
// Stone Division I: d must divide n, k = n/d ≥ 2
// Stone Division II: d divides n, you split into k heaps of size d
// where k ≥ 2 is ALSO your choice? No — k = n/d is determined.
//
// Actually the two versions differ in:
// I:  Split n into k = n/d heaps of size d (k determined by d)
// II: Split n into k heaps each of size n/d (similar but different constraint)
//
// The common formulation:
// I:  Replace heap of n with (n/d) heaps of size d, d|n, d < n
// II: Replace heap of n with k heaps of size (n/d), where d|n and k ≥ 2
//
// For both, the Grundy computation follows the same pattern,
// but the set of reachable XOR values differs.

function stoneDivisionII(n) {
  const grundy = new Array(n + 1).fill(0);

  for (let size = 1; size <= n; size++) {
    const reachable = new Set();

    for (let d = 2; d <= size; d++) {
      if (size % d === 0) {
        const k = size / d;
        if (k >= 2) {
          // k heaps of size d → XOR = Grundy(d) if k odd, 0 if k even
          const xorVal = (k % 2 === 0) ? 0 : grundy[d];
          reachable.add(xorVal);
        }
      }
    }

    let g = 0;
    while (reachable.has(g)) g++;
    grundy[size] = g;
  }

  return grundy[n] !== 0 ? "First" : "Second";
}

// The computation is IDENTICAL for both versions in many formulations.
// The difference lies in edge cases and which divisors are valid.
// Always read the problem statement carefully!

// Key Pattern Observations:
//
// 1. Grundy(n) = 0 if n is PRIME (including 1).
//    Proof: Only divisor is n itself, giving k = 1 (invalid).
//
// 2. Grundy(n) = 0 if n is ODD.
//    Proof: For odd n, any divisor d gives k = n/d. Since n is odd,
//    at least one of d or n/d is odd. If n/d is odd → Grundy(d) ⊕
//    Grundy(d) ⊕ ... (odd times) = Grundy(d). If n/d is even →
//    we already get 0 in reachable set. But careful — this isn't
//    always 0. Let's check: n = 9, divisors: d=3, k=3. XOR = G(3)=0.
//    Reachable set = {0}. mex({0}) = 1. So G(9) = 1 ≠ 0!
//
//    So the pattern is more nuanced. Let's compute the first few:
//    n:     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
//    G(n):  0 0 0 1 0 0 0 1 1  0  0  0  0  1  0  1
//
// 3. Grundy(n) = 1 for many composite numbers with even divisor.
//    Because an even divisor creates an XOR of 0 (even k or even Grundy(d)),
//    making mex = 1 since 0 is in reachable set.
//
// 4. The pattern is NOT fully periodic — computed via DP for general case.