Problem 509: Divisor Nim

Mathematical Analysis

Sprague-Grundy Theory

Each position $n$ has a Grundy value $g(n)$:

• $g(1) = 0$ (losing position: no moves available since no proper divisor $< 1$… actually 1 has no proper divisors other than itself, but the move requires $d < n$).

Wait — let us re-examine: from pile $n$, you can remove any divisor $d$ of $n$ with $1 \leq d < n$. This leaves a pile of $n - d$.

• $g(0)$: terminal, no stones. If we define losing as “can’t move,” then position 0 has no moves, $g(0) = 0$.
• $g(1)$: can remove 1 (divisor of 1 is 1, but $d < n = 1$ means no valid move). So $g(1) = 0$.

Actually $d | n$ and $d < n$. For $n = 1$: divisors of 1 are $\{1\}$, but $d < 1$ gives no moves. So 1 is a losing position.

For $n = 2$: divisors are $\{1, 2\}$, $d < 2$ gives $d = 1$. Remove 1, leaving 1 (losing for opponent). So 2 is winning.

For $n = 3$: divisors are $\{1, 3\}$, $d < 3$ gives $d = 1$. Remove 1, leaving 2 (winning for opponent). So 3 is losing.

For $n = 4$: divisors of 4 with $d < 4$: $\{1, 2\}$. Remove 1 → 3 (losing for opp, win!). So 4 is winning.

Pattern

• Odd primes are losing (only move is to remove 1, reaching an even = winning position).
• Powers of 2 are winning.
• The pattern depends on the prime factorization.

Key Insight

A position $n$ is losing if and only if $n = 1$ or $n$ is an odd prime. More precisely:

• $n$ is a P-position (previous player wins = current player loses) iff all moves from $n$ lead to N-positions.
• $n$ is an N-position (next player = current player wins) iff some move leads to a P-position.

Computing this requires the full Sprague-Grundy recursion.

Derivation

We compute $g(n)$ for $n = 0, 1, \dots, N$:

where $\text{mex}(S) =$ minimum excludant (smallest non-negative integer not in $S$).

A position is winning iff $g(n) \neq 0$.

For counting purposes, we only need to know if $g(n) = 0$ (losing) or $g(n) > 0$ (winning).

Proof of Correctness

The Sprague-Grundy theorem guarantees:

1. Every impartial game position has a unique Grundy value.
2. A position is losing (P-position) iff its Grundy value is 0.
3. The Grundy value equals the mex of Grundy values of all positions reachable in one move.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Naive computation of $g(n)$ for all $n \leq N$: For each $n$, enumerate divisors ($O(\sqrt{n})$) and look up $g(n-d)$. Total: $O(N\sqrt{N})$.
• Sieve-based divisor enumeration: $O(N \log N)$ to precompute all divisors.
• Space: $O(N)$ for storing Grundy values.

Answer

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

int main() {
    const int N = 500;

    // Sieve proper divisors
    vector<vector<int>> pdivs(N + 1);
    for (int d = 1; d <= N; d++) {
        for (int m = 2 * d; m <= N; m += d) {
            pdivs[m].push_back(d);
        }
    }

    // Compute Grundy values
    vector<int> g(N + 1, 0);
    for (int n = 2; n <= N; n++) {
        set<int> reachable;
        for (int d : pdivs[n]) {
            reachable.insert(g[n - d]);
        }
        int mex = 0;
        while (reachable.count(mex)) mex++;
        g[n] = mex;
    }

    // Count winning positions
    int winning = 0;
    for (int n = 1; n <= N; n++) {
        if (g[n] > 0) winning++;
    }

    // Output
    cout << "First 30 positions:" << endl;
    for (int n = 1; n <= 30; n++) {
        cout << "  n=" << n << ": g=" << g[n]
             << " [" << (g[n] > 0 ? "W" : "L") << "]" << endl;
    }

    cout << "\nWinning positions for n=1.." << N << ": " << winning << endl;

    // List losing positions
    cout << "\nLosing positions: ";
    for (int n = 1; n <= N; n++) {
        if (g[n] == 0) cout << n << " ";
    }
    cout << endl;

    return 0;
}

"""
Problem 509: Divisor Nim
A Nim variant where from pile n, you remove d stones where d | n and d < n.
Uses Sprague-Grundy theory to classify winning/losing positions.
"""

def compute_grundy(N: int) -> list:
    """
    Compute Grundy values for Divisor Nim for positions 0..N.
    g(n) = mex{g(n-d) : d | n, 1 <= d < n}
    """
    g = [0] * (N + 1)

    # Precompute proper divisors for each n using sieve
    # proper_divs[n] = {d : d | n, 1 <= d < n}
    proper_divs = [[] for _ in range(N + 1)]
    for d in range(1, N + 1):
        for multiple in range(2 * d, N + 1, d):
            proper_divs[multiple].append(d)

    for n in range(2, N + 1):
        reachable = set()
        for d in proper_divs[n]:
            reachable.add(g[n - d])
        # mex
        mex = 0
        while mex in reachable:
            mex += 1
        g[n] = mex

    return g

def count_winning(N: int):
    """Count winning positions (g(n) > 0) for n = 1..N."""
    g = compute_grundy(N)
    return sum(1 for n in range(1, N + 1) if g[n] > 0)

def solve_brute_force(N: int) -> list:
    """Classify positions as W(in) or L(ose) for verification."""
    # P-position: all moves lead to N-positions (g = 0)
    # N-position: some move leads to P-position (g > 0)
    is_losing = [True] * (N + 1)  # Start assuming all losing

    for n in range(2, N + 1):
        # Find proper divisors of n
        for d in range(1, n):
            if n % d == 0:
                if is_losing[n - d]:  # Can move to a losing position
                    is_losing[n] = False
                    break

    return is_losing

# Compute Grundy values
N = 500
g = compute_grundy(N)

# Display small values
print("Position: Grundy value (W/L)")
for n in range(1, 31):
    status = "W" if g[n] > 0 else "L"
    print(f"  n={n:3d}: g={g[n]:2d} [{status}]")

# Count winning positions
W = count_winning(N)
print(f"\nWinning positions for n=1..{N}: {W}")
print(f"Losing positions for n=1..{N}: {N - W}")

# Verify against brute force for small N
N_small = 100
g_small = compute_grundy(N_small)
is_losing_bf = solve_brute_force(N_small)
match = all((g_small[n] == 0) == is_losing_bf[n] for n in range(1, N_small + 1))
print(f"\nBrute-force verification (n=1..{N_small}): {'PASS' if match else 'FAIL'}")

# Identify pattern: which numbers are losing positions?
losing = [n for n in range(1, N + 1) if g[n] == 0]
print(f"\nFirst 30 losing positions: {losing[:30]}")