In-depth Analysis of the Nim Game: Mathematical Principles and Algorithm Implementation

Core Logic and Mathematical Principles

The Nim game is one of the most classic foundational models in combinatorial game theory. Understanding the core of the Nim game lies in mastering the Nim-Sum and the underlying state space mapping.

1. Classic Nim Game Rules

There are $n$ piles of stones, with the number of stones in each pile being $a_1, a_2, \dots, a_n$. Two players take turns making moves, where each move can involve selecting any pile of stones and removing any positive integer number of stones (even taking the entire pile). The player who cannot make a legal move (i.e., all piles have zero stones) is declared the loser.

2. Bouton Theorem: The Mathematical Essence of Nim-Sum Judgement

For a specific state of the Nim game $(a_1, a_2, \dots, a_n)$, the Nim-Sum is defined as the bitwise XOR sum of all pile sizes, denoted as $S$:

$$S = a_1 \oplus a_2 \oplus \dots \oplus a_n$$

The Bouton theorem states:

• If $S = 0$, then the current state is a P-position (losing position).
• If $S \neq 0$, then the current state is an N-position (winning position).

Mathematical Proof of the Theorem (Based on the Three Axioms of P/N)

1. Verification of Terminal State: When the game ends, all $a_i = 0$, at this point $S = 0 \oplus 0 \dots \oplus 0 = 0$. This satisfies the axiom that the terminal state is a P state.
2. $S \neq 0$ Must Lead to $S = 0$: Assume the current $S = k \neq 0$. Let the highest bit of $k$ in binary be the $d$-th bit. Among all piles, there must be at least one pile $a_i$ whose $d$-th bit is also $1$ (otherwise, the $d$-th bit of the XOR sum cannot be $1$). At this point, we have:

$$a_i \oplus k < a_i$$

(because XORing $k$ will change the $d$-th bit of $a_i$ from $1$ to $0$, while higher bits remain unchanged). Thus, the player can certainly take some stones from pile $i$ to reduce its size exactly to $a_i' = a_i \oplus k$. At this point, the new XOR sum becomes:

$$S' = S \oplus a_i \oplus a_i' = k \oplus a_i \oplus (a_i \oplus k) = 0$$

This satisfies the axiom that "reaching P must be N". 3. $S = 0$ Will Always Transition to $S \neq 0$: If the current $S = 0$, the player chooses to change one of the piles $a_i$ to $a_i'$ (due to rule restrictions, $a_i' \neq a_i$). The new XOR sum is:

$$S' = S \oplus a_i \oplus a_i' = 0 \oplus a_i \oplus a_i' = a_i \oplus a_i'$$

Since $a_i' \neq a_i$, it follows that $a_i \oplus a_i' \neq 0$, i.e., $S' \neq 0$. This satisfies the axiom that "if all successors are N, then it must be P".

Algorithm Derivation and State Design

Since the Bouton theorem condenses the originally complex game tree into simple binary XOR operations, the complexity of maintaining the state drops from exponential to $O(N)$.

Decision Generation for Winning First Move

In actual competitions, problems not only require determining the winner for the first player but often ask to output how many perfect winning moves exist for the first player or specific strategy plans.

According to the proof of the second point, as long as $(a_i \oplus S) < a_i$ is satisfied, the current pile of stones can serve as a valid winning starting point. We only need to linearly scan all piles to count how many satisfy this inequality.

C++ Standard Source Code

#include <iostream>
#include <vector>

// Solving classic Nim game state determination and solution statistics
void solve_nim_game(const std::vector<int>& piles) {
    int nim_sum = 0;
    for (int count : piles) {
        nim_sum ^= count; // Calculate global nim sum
    }

    if (nim_sum == 0) {
        // Global XOR sum is 0, first player loses
        std::cout << "Second player wins (P-position)\n";
    } else {
        // Global XOR sum is not 0, first player wins
        std::cout << "First player wins (N-position)\n";

        int winning_moves_count = 0;
        // Count and output the number of winning options for the first player
        for (size_t i = 0; i < piles.size(); ++i) {
            // Check if modifying this pile to piles[i] ^ nim_sum is valid (i.e., size decreases)
            if ((piles[i] ^ nim_sum) < piles[i]) {
                winning_moves_count++;
            }
        }
        std::cout << "Number of winning options for the first step: " << winning_moves_count << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    if (std::cin >> t) { // Multiple test cases
        while (t--) {
            int n;
            std::cin >> n;
            std::vector<int> piles(n);
            for (int i = 0; i < n; ++i) {
                std::cin >> piles[i];
            }
            solve_nim_game(piles);
        }
    }
    return 0;
}

NOIP Practical Pitfall Guide

1. Confusing XOR and Comparison Operator Precedence In judging winning moves, the core expression is (piles[i] ^ nim_sum) < piles[i]. In C++, the comparison operator (<) has higher precedence than the bitwise operator (^). If written as piles[i] ^ nim_sum < piles[i], the compiler will first evaluate nim_sum < piles[i], resulting in a bool value, which will then be XORed with the number of stones. This will lead to a complete logical breakdown. Parentheses must be enforced on the outer layer.
2. Blindly Applying Classic XOR in Nim Variants Many problems may modify the rules of the Nim game, such as "can only take up to $M$ stones at a time" (combining with the Bash game) or "can only move stones to adjacent piles" (staircase Nim). The situations in these variant problems are no longer purely based on $a_i$ XOR. For example, staircase Nim only requires XORing the number of stones on odd steps. It is crucial to carefully examine the constraints of movement when reading the problem, avoiding rote memorization.