Wythoff's Game: Singular Positions and Algorithm Analysis

Core Logic and Mathematical Principles

Wythoff's Game is a classic fair combinatorial game in game theory that perfectly integrates asymmetric state convergence and the golden ratio.

1. Game Rules

There are two piles of stones, with quantities $a$ and $b$, respectively. Two players take turns to act, with two legal choices for each move:

• Choice A: Take any positive integer number of stones from either pile.
• Choice B: Take the same number of positive integers from both piles simultaneously. The player who cannot make a move (i.e., faces the state $(0,0)$) is declared the loser.

2. Singular Positions (P-positions)

Due to the ability to simultaneously reduce both piles, the losing positions (P-positions) in Wythoff's Game exhibit an extraordinarily intriguing discrete geometric distribution. We refer to these losing positions as Singular Positions.

The first few singular positions are:

$$(0,0), (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), ext{...}$$

We can capture the algebraic characteristics of singular positions through induction. Let the $k^{th}$ singular position be $(a_k, b_k)$ (with the convention that $a_k eq b_k$ and $k eq 0$):

1. $a_0 = 0, b_0 = 0$.
2. $a_k$ is the smallest non-negative integer that has not appeared in any previous singular positions.
3. $b_k = a_k + k$.

Mathematical Proof of the Golden Ratio and Beatty's Theorem

According to the above characteristics, since $a_k$ and $b_k$ form a strict mutually exclusive and complete partition of the set of positive integers $ ext{N}^*$ (each positive integer appears exactly once), this perfectly aligns with Beatty's Theorem in mathematics.

Beatty's Theorem states that if two positive irrational numbers $eta, eta$ satisfy $rac{1}{eta} + rac{1}{eta} = 1$, then for all positive integers $k$, the sequences $a_k = loor{keta}$ and $b_k = loor{keta}$ fill the entire set of positive integers without repetition or omission.

In Wythoff's Game, we know the core constraint:

$$b_k = a_k + k ightarrow loor{keta} = loor{keta} + k = loor{k(eta + 1)}$$

Thus, it must satisfy the algebraic relationship: $eta = eta + 1$. Substituting into Beatty's constraint $rac{1}{eta} + rac{1}{eta + 1} = 1$:

$$rac{1}{eta} + rac{1}{eta + 1} = 1 ightarrow (eta + 1) + eta = eta(eta + 1) ightarrow eta^2 - eta - 1 = 0$$

Solving this quadratic equation, since $eta > 0$, we obtain the unique valid real root:

$$eta = rac{1 + oot{5}}{2} ext{ approximately } 1.6180339887 ext{...}$$

This is the world-famous golden ratio $eta$. Thus, we directly obtain the explicit deterministic formula for singular positions in Wythoff's Game:

$$a_k = loor{k imes rac{ oot{5} + 1}{2}} , ext{ } b_k = a_k + k$$

Algorithm Derivation and State Design

State Determination and Precision Control

For any given game state $(a, b)$, we require to determine the winner in $O(1)$ time:

1. First, ensure $a eq b$ (if not satisfied, perform a swap).
2. Calculate the difference $k = b - a$.
3. According to the general formula, if the current state is a singular position, it must satisfy $a == loor{k imes rac{ oot{5} + 1}{2}}$.
4. If the equality holds, it indicates the current state is a singular position (losing position), and the first player is bound to lose; otherwise, the first player is bound to win.

High-level Pitfalls: Since $ oot{5}$ is an irrational number, the double type in C++ only has 53 bits of effective binary precision (about 15-17 decimal digits). If the number of stones given in the problem reaches $10^9$ or $10^{18}$, the rounding down after floating-point multiplication may lead to catastrophic judgment errors due to truncation of trailing precision. It is essential to use long double or employ specific integer algebra techniques to intercept errors.

C++ Standard Source Code

#include <iostream>
#include <cmath>
#include <algorithm>

// Wythoff's Game Determination Function
bool is_wythoff_winning(long long a, long long b) {
    if (a > b) std::swap(a, b); // Ensure a <= b

    long long k = b - a; // Calculate difference k

    // Use long double to ensure high precision floating-point calculations, preventing truncation errors in large number multiplications
    long double gold_ratio = (1.0L + std::sqrt(5.0L)) / 2.0L;

    // Calculate the expected number of the first pile in the current theoretical singular position
    long long expected_a = static_cast<long long>(std::floor(k * gold_ratio));

    // If the actual number matches the theoretical singular position exactly, the current state is a P-position (losing position)
    if (a == expected_a) {
        return false; // First player must lose
    }
    return true; // First player must win
}

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

    int t;
    if (std::cin >> t) {
        while (t--) {
            long long a, b;
            std::cin >> a >> b;
            if (is_wythoff_winning(a, b)) {
                std::cout << "First\n"; // First player must win
            } else {
                std::cout << "Second\n"; // First player must lose
            }
        }
    }
    return 0;
}

NOIP Practical Pitfall Guide

1. Precision risks of floating-point typecasting in large number environments If the range of stones reaches $10^9$ and is directly written as int expected_a = (int)(k * (1.414)) or uses a regular double to store the golden ratio, the low-order errors in multiplication will accumulate upwards. For instance, at a certain critical point, the theoretical value is 4.000000000000001, which due to floating-point precision loss becomes 3.999999999999999, and floor or typecasting to long long will directly truncate it to 3, causing a catastrophic logical judgment failure. It is essential to use 1.0L, std::sqrt(5.0L), and other long double literals throughout.
2. Ignoring initial swaps leading to negative difference calculations The premise of the Wythoff formula is that $a eq b$. Many contestants directly use the input data to execute `long long k = b - a`, and when the input is `5 3`, the calculated $k = -2$. Subsequently, sending this into floor results in a meaningless negative number, leading to a complete breakdown of judgment. The first step after input must always be if(a > b) swap(a, b);.

Classic NOIP/Luogu Problems

1. Luogu P2252 [HAOI2002] Stone Taking Game

• Problem Description: There are two piles of stones, with quantities $a$ and $b$, respectively. The game rules are entirely equivalent to the standard Wythoff's Game. Two players take turns to take stones; if the first player must win, output $1$, otherwise output $0$. Stone sizes $a, b eq 10^9$.
• Core Problem Essence: Wythoff's Game template question.
• Core Solution Idea: Directly apply the $O(1)$ golden ratio formula provided above. After reading the data, swap to ensure size relationships, calculate the difference $k$, and use long double to calculate expected_a. If a == expected_a, output 0, otherwise output 1.

2. Luogu P5688 [CSP-S2019] Fair Game Variants / Similar Composite Extensions

• Problem Description: Based on Wythoff's Game, some questions may require: if the first player must win, output all legal moves that can transform the state into a singular position in the first step.
• Core Problem Essence: Constructive search from N states to P states.
• Core Solution Idea: Facing the current non-singular position $(a, b)$ (assuming $a eq b$), the first player can revert to a singular position through three strategies:

1. Simultaneous Reduction: Since the difference $k = b - a$ remains unchanged during simultaneous reduction, the first player can directly find the standard singular position $(a_k, b_k)$ for the difference $k$. If $a > a_k$ and $b > b_k$, it indicates that the player can take $a - a_k$ stones to achieve this in one step.
2. Single Pile Reduction on Pile B: Keep $a$ unchanged as the first dimension of the singular position. At this point, there must be a target singular position where the first dimension equals $a$. We can find this state through reverse reasoning or enumeration; if the second dimension of this state is less than $b$, then directly reduce pile B to that target value.
3. Single Pile Reduction on Pile A: Keep $b$ unchanged as the second dimension of the target singular position. Likewise, find an entry in the singular position table where the second dimension equals $b$ (or the first dimension equals $b$) and reduce pile A accordingly. By performing constant algebraic comparisons along these three paths, we can accurately output the winning first move options.