DSA Mastery - 38,000+ problems across 14 topics

Deep Dive Tutorial

Combinatorial game theory analyzes two-player zero-sum games where players alternate moves and the last to move wins (normal play convention). The breakthrough insight: any position's winning/losing status can be computed by XOR of "Grundy values." Once you can compute Grundy values, you can solve arbitrary game combinations.

Nim Game — The Foundation

key

Nim theorem (Sprague-Grundy for Nim): Given piles of stones [n1, n2, ..., nk], the current player LOSES if and only if XOR(n1, n2, ..., nk) === 0.

If XOR ≠ 0, current player can always move to XOR = 0 (winning position for opponent becomes losing). If XOR = 0, every move creates XOR ≠ 0 (opponent now wins).

Nim winner

function nimWinner(piles) {
    // XOR all pile sizes
    // 0 → current player loses (all moves put opponent in winning position)
    // non-zero → current player wins
    return piles.reduce((xor, p) => xor ^ p, 0) !== 0;
}

Sprague-Grundy Theorem

lightbulb

Grundy value (nimber) G(position):
- G = 0: LOSING position (previous player wins, i.e., you lose)
- G > 0: WINNING position

G(pos) = mex({G(next) : next ∈ moves(pos)})
where mex = minimum excludant = smallest non-negative integer NOT in the set.

For combined games: G(game1 + game2) = G(game1) XOR G(game2).

Sprague-Grundy values with memoization

function computeGrundy(n, moves) {
    const memo = new Map();
    function grundy(pos) {
        if (memo.has(pos)) return memo.get(pos);
        const reachable = new Set();
        for (const move of moves) {
            if (pos - move >= 0) reachable.add(grundy(pos - move));
        }
        // mex: find smallest non-negative integer not in reachable
        let mex = 0;
        while (reachable.has(mex)) mex++;
        memo.set(pos, mex);
        return mex;
    }
    return grundy(n);
}

// Example: game where you can take 1, 2, or 3 stones
// grundy(0)=0 (lose), grundy(1)=1, grundy(2)=2, grundy(3)=3, grundy(4)=0 (pattern!)
// Pattern: Grundy(n) = n % 4 for moves {1,2,3}

Worked Problems

Easy

Medium

Medium

Game Theory

Deep Dive Tutorial

Nim Game — The Foundation

Sprague-Grundy Theorem

Worked Problems

More Worked Problems