Problem 665: Proportionate Nim

Mathematical Analysis

Sprague-Grundy Framework

In combinatorial game theory, every impartial game position has a Grundy value (nimber) $\mathcal{G}(n) = \text{mex}\{\mathcal{G}(m) : m \text{ reachable from } n\}$ where $\text{mex}$ is the minimal excludant.

Theorem (Sprague-Grundy). A position with multiple independent piles of sizes $n_1, \ldots, n_k$ is a losing position (P-position) if and only if $\mathcal{G}(n_1) \oplus \cdots \oplus \mathcal{G}(n_k) = 0$, where $\oplus$ is XOR.

Move Structure in Proportionate Nim

From pile size $n$, the allowed moves remove $\lfloor n/k \rfloor$ stones for each valid $k$, leaving a pile of size $n - \lfloor n/k \rfloor$. The reachable states from $n$ are:

Periodicity of Grundy Values

Lemma. For many Nim variants, the Grundy sequence $\{\mathcal{G}(n)\}_{n \ge 0}$ is eventually periodic. The period depends on the specific move rules.

For proportionate moves, since $\lfloor n/k \rfloor$ depends on $n \bmod k$, the Grundy values exhibit quasi-periodic behavior with period related to $\text{lcm}$ of the allowed $k$ values.

Concrete Grundy Values

(Exact values depend on specific problem parameters.)

Derivation

Editorial

Sprague-Grundy analysis for Nim variant with proportional moves. From pile n, remove floor(n/k) stones for allowed k values. We detect periodicity in the Grundy sequence to extrapolate. Finally, combine pile values via XOR.

Pseudocode

Compute Grundy values $\mathcal{G}(0), \mathcal{G}(1), \ldots, \mathcal{G}(N)$ iteratively
For each $n$, enumerate reachable states and compute $\text{mex}$
Detect periodicity in the Grundy sequence to extrapolate
Combine pile values via XOR

Optimization

The number of distinct values of $\lfloor n/k \rfloor$ as $k$ varies is $O(\sqrt{n})$ (divisor-sum trick). This accelerates the mex computation.

Proof of Correctness

Theorem (Sprague-Grundy, 1935/1939). Every impartial game under normal play convention is equivalent to a Nim heap of size $\mathcal{G}$.

Proof. By structural induction on game positions. A position with $\mathcal{G} = 0$ is a P-position (all successors have $\mathcal{G} > 0$). A position with $\mathcal{G} = g > 0$ can move to any position with $\mathcal{G} < g$. $\square$

Complexity Analysis

• Grundy computation: $O(N \sqrt{N})$ using the $\lfloor n/k \rfloor$ trick.
• Periodicity detection: $O(N)$ additional.
• Space: $O(N)$.

Answer

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

/*
 * Problem 665: Proportionate Nim
 *
 * Compute Sprague-Grundy values for Nim variant.
 * From pile n, remove floor(n/k) stones for k=1,2,...
 * G(n) = mex{G(n - floor(n/k)) : k >= 1, floor(n/k) > 0}
 */

int main() {
    const int N = 1000;
    vector<int> grundy(N + 1, 0);

    for (int n = 1; n <= N; n++) {
        set<int> reachable;
        // Remove floor(n/k) for k=1..n
        int prev_removal = -1;
        for (int k = 1; k <= n; k++) {
            int removal = n / k;
            if (removal == 0) break;
            if (removal == prev_removal) continue;
            prev_removal = removal;
            reachable.insert(grundy[n - removal]);
        }
        int mex = 0;
        while (reachable.count(mex)) mex++;
        grundy[n] = mex;
    }

    printf("Grundy values 0..20:");
    for (int i = 0; i <= 20; i++) printf(" %d", grundy[i]);
    printf("\n");

    // Count P-positions
    int p_count = 0;
    for (int i = 0; i <= N; i++)
        if (grundy[i] == 0) p_count++;
    printf("P-positions up to %d: %d\n", N, p_count);

    return 0;
}

"""
Problem 665: Proportionate Nim

Sprague-Grundy analysis for Nim variant with proportional moves.
From pile n, remove floor(n/k) stones for allowed k values.
"""

def compute_grundy(N, allowed_ks=None):
    """Compute Grundy values for pile sizes 0..N.

    Default move: from pile n, can remove floor(n/k) for k=2,3,...
    (leaving n - floor(n/k) stones).
    """
    grundy = [0] * (N + 1)

    for n in range(1, N + 1):
        reachable = set()
        # Can remove floor(n/k) stones for k >= 2
        seen_removals = set()
        for k in range(2, n + 1):
            removal = n // k
            if removal == 0:
                break
            if removal not in seen_removals:
                seen_removals.add(removal)
                new_size = n - removal
                reachable.add(grundy[new_size])
        # Also can remove all (k=1)
        reachable.add(grundy[0])

        # Compute mex
        mex = 0
        while mex in reachable:
            mex += 1
        grundy[n] = mex

    return grundy

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

print("Problem 665: Proportionate Nim")
print(f"Grundy values for n=0..20: {grundy[:21]}")

# Find P-positions (Grundy = 0)
p_positions = [n for n in range(N+1) if grundy[n] == 0]
print(f"P-positions up to {N}: {p_positions[:20]}...")
print(f"Number of P-positions: {len(p_positions)}")

# Detect periodicity
def find_period(seq, min_period=1, max_period=200):
    """Detect period in sequence."""
    n = len(seq)
    for p in range(min_period, max_period + 1):
        is_periodic = True
        for i in range(p, min(n, 3 * p)):
            if seq[i] != seq[i - p]:
                is_periodic = False
                break
        if is_periodic:
            return p
    return None

period = find_period(grundy[50:])  # skip initial transient
if period:
    print(f"Detected period: {period}")