Game Variations

Pillar: Shape — "Grundy values of subtraction games are PERIODIC — the shape repeats with period = max allowed move + 1."

---

The Setup

Ch8 L2 gave you the Sprague-Grundy theorem: every impartial game position has a Grundy number, and compound games combine via XOR. That machinery is general — but the games you'll actually face in contests aren't always plain Nim.

Subtraction games restrict which moves are legal. Staircase Nim changes the board geometry. Wythoff's Game lets you remove from two piles at once. The Divisor Game turns number theory into a combinatorial game.

Each of these has a clean structure once you know where to look. The recurring theme: the Grundy values form a pattern, and the pattern is often simpler than you'd expect.

---

Subtraction Games with Periodic Grundy Values

In a subtraction game, two players alternate removing stones from a pile, but only amounts in a fixed set \(S \subseteq \mathbb{Z}_+\) are allowed. The player who cannot move loses. This is the same framework as Nim, except the move set is restricted.

Start with the simplest case: \(S = \{1, 2, 3\}\) (you can remove \(1\), \(2\), or \(3\) stones). Compute Grundy values from position \(0\) upward. Recall: the Grundy number of a position is the \(\text{mex}\) (minimum excludant) of the Grundy numbers of all positions reachable in one move.

Position	Reachable Grundy values	\(\text{mex}\)
\(0\)	\(\emptyset\)	\(0\)
\(1\)	\(\{0\}\)	\(1\)
\(2\)	\(\{0, 1\}\)	\(2\)
\(3\)	\(\{0, 1, 2\}\)	\(3\)
\(4\)	\(\{1, 2, 3\}\)	\(0\)
\(5\)	\(\{2, 3, 0\}\)	\(1\)
\(6\)	\(\{3, 0, 1\}\)	\(2\)
\(7\)	\(\{0, 1, 2\}\)	\(3\)

The Grundy values cycle: \(0, 1, 2, 3, 0, 1, 2, 3, \ldots\) with period \(4 = \max(S) + 1\). When \(S = \{1, 2, \ldots, k\}\), the Grundy value of position \(n\) is simply \(n \bmod (k+1)\). Losing positions are exactly the multiples of \(k+1\).

Non-contiguous move sets

The period is not always \(\max(S) + 1\) for arbitrary \(S\). Consider \(S = \{1, 3, 4\}\):

Position	Reachable Grundy values	\(\text{mex}\)
\(0\)	\(\emptyset\)	\(0\)
\(1\)	\(\{0\}\)	\(1\)
\(2\)	\(\{1\}\)	\(0\)
\(3\)	\(\{0, 1\}\)	\(2\)
\(4\)	\(\{0, 2\}\)	\(1\)
\(5\)	\(\{1, 0, 0\}\)	\(2\)
\(6\)	\(\{0, 1, 1\}\)	\(2\)
\(7\)	\(\{2, 2, 0\}\)	\(1\)
\(8\)	\(\{1, 2, 2\}\)	\(0\)
\(9\)	\(\{2, 1, 2\}\)	\(0\)
\(10\)	\(\{2, 0, 0\}\)	\(1\)
\(11\)	\(\{0, 0, 1\}\)	\(2\)
\(12\)	\(\{0, 1, 2\}\)	\(3\)
\(13\)	\(\{1, 2, 1\}\)	\(0\)
\(14\)	\(\{3, 0, 2\}\)	\(1\)

The Grundy sequence is: \(0, 1, 0, 2, 1, 2, 2, 1, 0, 0, 1, 2, 3, 0, 1, \ldots\) This is harder to spot by hand, but it does eventually become periodic. The Sprague-Grundy theory guarantees periodicity for all finite subtraction games — the period just depends on the specific move set.

The key fact: once you know the Grundy values are periodic, you don't need to compute them up to \(n = 10^{18}\). Compute enough values to find the period, then answer \(G(n) = G(n \bmod \text{period})\) in \(O(1)\).

For compound subtraction games (multiple independent piles, each with the same move set), compute the Grundy value for each pile using the period, then XOR them all together. This is just Sprague-Grundy from Ch8 L2 applied to periodic Grundy functions.

---

Staircase Nim

Staircase Nim has a sequence of stairs numbered \(0, 1, 2, \ldots, k\), each holding some stones. On each turn, a player picks a stair \(i \geq 1\) and moves any positive number of stones from stair \(i\) down to stair \(i - 1\). Stair \(0\) is the ground — stones that reach it are out of play. The player who cannot move loses (all stones are on stair \(0\)).

The result: the first player wins if and only if the XOR of stones on odd-indexed stairs is nonzero.

\[\bigoplus_{i \text{ odd}} \text{stones}[i] \neq 0 \implies \text{first player wins}\]

Why even-indexed stairs don't matter

Think about what happens when a player moves stones from an even stair to an odd stair. That changes the XOR of the odd stairs. But the opponent can immediately copy that exact move: take those same stones from the odd stair and push them down to the next even stair. This restores the XOR of the odd stairs to what it was before.

So any move on an even stair is "free" for the opponent to neutralize. The real game is played entirely on the odd stairs. From the perspective of the odd stairs, moving stones from odd stair \(i\) to even stair \(i-1\) is equivalent to removing them from the game. This reduces to standard multi-pile Nim on the odd-indexed piles.

Example. Stairs: \([3, 5, 2, 7, 1]\) (indices \(0\) through \(4\)).

• Odd-indexed stairs: stair \(1\) has \(5\), stair \(3\) has \(7\).
• XOR: \(5 \oplus 7 = 2 \neq 0\).
• First player wins.

---

Wythoff's Game

In Wythoff's Game, there are two piles of stones. On each turn, a player can either:

1. Remove any positive number of stones from one pile (standard Nim move), OR
2. Remove the same positive number of stones from both piles simultaneously.

The player who takes the last stone wins.

This second option — removing equal amounts from both — breaks the standard Nim analysis. The losing positions (cold positions where the player to move loses) follow a remarkable pattern involving the golden ratio.

Losing positions. Define \(\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\). The losing positions are the pairs:

\[(\lfloor n\phi \rfloor, \lfloor n\phi^2 \rfloor) \quad \text{for } n = 0, 1, 2, 3, \ldots\]

Since \(\phi^2 = \phi + 1\), the second coordinate is always the first coordinate plus \(n\).

\(n\)	\(\lfloor n\phi \rfloor\)	\(\lfloor n\phi^2 \rfloor\)	Pair
\(0\)	\(0\)	\(0\)	\((0, 0)\)
\(1\)	\(1\)	\(2\)	\((1, 2)\)
\(2\)	\(3\)	\(5\)	\((3, 5)\)
\(3\)	\(4\)	\(7\)	\((4, 7)\)
\(4\)	\(6\)	\(10\)	\((6, 10)\)

These pairs (and their reverses, like \((2, 1)\)) are all the losing positions. The pairs are also called Beatty pairs — every positive integer appears exactly once across all first coordinates and all second coordinates. This is a consequence of the Beatty sequence theorem applied to \(\phi\) and \(\phi^2\).

Why \(\phi\)? The golden ratio is the unique positive root of \(x^2 = x + 1\). The "remove equal from both" move means that if \((a, b)\) is a losing position, then \((a + k, b + k)\) cannot also be a losing position for any \(k > 0\). This "no two cold positions share the same difference" constraint, combined with the requirement that every non-negative integer appears exactly once as a first or second coordinate, forces the Beatty sequence structure with ratio \(\phi\).

From any position not in this set, the current player can move to one of these losing positions. From any position in this set, every possible move leads to a position outside the set. That's the definition of a P-position (previous player wins).

Checking a position. Given piles \((a, b)\) with \(a \leq b\), compute \(n = b - a\). The position is a loss iff \(a = \lfloor n \cdot \phi \rfloor\). This gives an \(O(1)\) check per query.

---

Divisor Game

The Divisor Game starts with a number \(n\). On each turn, the current player chooses a proper divisor \(d\) of the current number (\(1 \leq d < n\), \(d \mid n\)) and replaces \(n\) with \(n - d\). The player who cannot move (stuck at \(n = 1\), which has no proper divisor less than itself to subtract — \(d\) must satisfy \(d < n\)) loses.

The key insight: even wins, odd loses.

Trace the logic:

• \(n = 1\): no valid move. Losing position.
• \(n = 2\): subtract \(1\) (the only proper divisor), leaving \(1\). The opponent is stuck. Winning.
• Any odd \(n\): all divisors of an odd number are odd. Subtracting an odd \(d\) from odd \(n\) gives even \(n - d\). You're forced to hand your opponent an even number.
• Any even \(n\): \(1\) is always a divisor. Subtracting \(1\) from even \(n\) gives odd \(n - 1\). You can always hand your opponent an odd number.

By induction: odd positions are losing, even positions are winning. The first player with an even \(n\) can always subtract \(1\), forcing the opponent into an odd number. The opponent must subtract an odd divisor, returning an even number. This continues until the opponent receives \(1\).

No Grundy computation needed — pure parity analysis.

This is a common interview problem (LeetCode 1025). The proof is clean enough to explain in two sentences: odd numbers only have odd divisors, so odd minus odd is even. Even numbers always have \(1\) as a divisor, so even minus \(1\) is odd. First player with even \(n\) forces a parity trap.

---

When Sprague-Grundy Doesn't Apply

Everything in this chapter assumes impartial games: both players have the same moves available from every position. Nim, subtraction games, Staircase Nim, Wythoff's Game — all impartial.

Partisan games break this assumption. In a partisan game, the two players have different move sets. Chess is partisan — White moves white pieces, Black moves black pieces. Go is partisan. Most "real" games are partisan.

The theory for partisan games uses surreal numbers, developed by John Conway. Positions are assigned surreal number values (not just non-negative integers like Grundy numbers), and the algebra is substantially more complex. Sums of partisan games still decompose, but via surreal number addition rather than XOR.

For competitive programming, partisan games are rare. When they appear, they usually have special structure that avoids the full surreal number machinery. The takeaway: if a problem gives different moves to the two players, Sprague-Grundy does not directly apply — look for problem-specific structure instead.

---

The Code

Staircase Nim Solver

#include <bits/stdc++.h>
using namespace std;

int main() {
    int numStairs;
    cin >> numStairs;
    vector<int> stonesPerStair(numStairs);
    for (int i = 0; i < numStairs; i++) cin >> stonesPerStair[i];

    int xorOfOddStairs = 0;
    for (int i = 1; i < numStairs; i += 2) {
        xorOfOddStairs ^= stonesPerStair[i];
    }
    cout << (xorOfOddStairs != 0 ? "first" : "second") << "\n";
    return 0;
}

Periodic Grundy Detector

Given a subtraction game with allowed move set, compute Grundy values up to a search limit and detect the period.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int numMoves, searchLimit;
    cin >> numMoves >> searchLimit;
    vector<int> allowedMoves(numMoves);
    for (int i = 0; i < numMoves; i++) cin >> allowedMoves[i];

    int maxMove = *max_element(allowedMoves.begin(), allowedMoves.end());
    vector<int> grundy(searchLimit, 0);

    for (int position = 1; position < searchLimit; position++) {
        set<int> reachable;
        for (int move : allowedMoves) {
            if (move <= position) {
                reachable.insert(grundy[position - move]);
            }
        }
        int mexValue = 0;
        while (reachable.count(mexValue)) mexValue++;
        grundy[position] = mexValue;
    }

    int detectedPeriod = -1;
    int startOffset = -1;
    for (int period = 1; period <= maxMove + 1; period++) {
        int candidateStart = period;
        bool isPeriodic = true;
        for (int i = candidateStart; i + period < searchLimit; i++) {
            if (grundy[i] != grundy[i + period]) {
                isPeriodic = false;
                break;
            }
        }
        if (isPeriodic) {
            detectedPeriod = period;
            startOffset = candidateStart;
            break;
        }
    }

    cout << "Period: " << detectedPeriod << "\n";
    cout << "Starts at position: " << startOffset << "\n";
    cout << "Grundy values for first " << min(searchLimit, 2 * detectedPeriod + startOffset) << " positions:\n";
    for (int i = 0; i < min(searchLimit, 2 * detectedPeriod + startOffset); i++) {
        cout << "G(" << i << ") = " << grundy[i] << "\n";
    }
    return 0;
}

---

Complexity

• Staircase Nim: \(O(k)\) time, \(O(k)\) space where \(k\) is the number of stairs.
• Periodic Grundy detection: \(O(L \times |S|)\) time where \(L\) is the search limit and \(|S|\) is the number of allowed moves. Space \(O(L)\).
• Wythoff check: \(O(1)\) per query using floor and the golden ratio.
• Divisor Game: \(O(1)\) — just check parity.

---

Common Mistakes

• Staircase Nim: XORing all stairs instead of only odd-indexed ones. Even-indexed stairs are dummy positions. If you XOR everything, you get the wrong answer. Double-check your indexing — is stair \(0\) the ground or the first stair? The convention matters.

• Subtraction games: assuming the period is always \(\max(S) + 1\). That formula holds only when \(S = \{1, 2, \ldots, k\}\). For arbitrary \(S\), you must compute Grundy values and detect the period empirically. The period exists (guaranteed by theory), but its length depends on the specific move set.

• Wythoff's Game: using integer arithmetic for \(\phi\). The golden ratio is irrational. If you compute \(\lfloor n\phi \rfloor\) using floating-point, rounding errors creep in for large \(n\). For contest problems with large coordinates, use the characterization that \((a, b)\) with \(a \leq b\) is a losing position iff \(a = \lfloor (b - a) \cdot \phi \rfloor\). Even then, verify with extended precision or the Zeckendorf representation.

---

Quick Recap

• Subtraction games with move set \(S\) produce Grundy values that are eventually periodic. When \(S = \{1, \ldots, k\}\), the period is \(k+1\) and \(G(n) = n \bmod (k+1)\).
• Staircase Nim reduces to standard Nim on the odd-indexed stairs. Moves on even stairs are immediately countered by copying them one step down.
• Wythoff's Game losing positions are \((\lfloor n\phi \rfloor, \lfloor n\phi^2 \rfloor)\) where \(\phi\) is the golden ratio. The golden ratio appears because of the dual move structure.
• The Divisor Game is pure parity: even always wins by subtracting \(1\).
• Partisan games (different moves per player) require surreal numbers, not Sprague-Grundy. Rare in competitive programming.

---

Problems

Problem	Link	Difficulty	Focus
CSES — Grundy's Game	cses.fi/problemset/task/2207	Medium	Grundy number computation for a splitting game; requires detecting patterns
CSES — Stick Game	cses.fi/problemset/task/1729	Easy	Direct subtraction game; compute Grundy values with restricted move set
CSES — Another Game	cses.fi/problemset/task/2208	Medium	Staircase Nim variant; identify which positions matter for the XOR