Additive Subtraction Games

This paper provides the first complete proof of a closed formula involving Beatty-type bracket expressions for determining P-positions in additive subtraction games within the primitive quadratic regime, while also establishing that the full nim-value structure resides on linear shifts of these classical P-positions.

The Gist

Imagine you are playing a game with a giant pile of stones. You and a friend take turns removing stones, but there's a catch: you can only remove specific numbers of stones at a time. Let's say the rules say you can only take $a$, $b$, or $a+b$ stones.

This is a Subtraction Game. The goal is to be the last person to move. If you are stuck and can't make a move (because there aren't enough stones left to match your allowed moves), you lose.

Mathematicians love these games because they can predict exactly who will win if both players play perfectly. They do this by assigning a "score" (called a Nim-value) to every possible pile size:

• 0: You are in trouble. If it's your turn and the pile is this size, you will lose (assuming your opponent plays perfectly). These are called P-positions (Previous player winning).
• 1, 2, 3: You are in a winning spot. You can make a move to force your opponent into a "0" spot.

The Big Mystery

For a long time, mathematicians knew the rules for simple versions of this game. But for a specific, slightly more complex version (called the "primitive quadratic regime"), they had a secret formula that seemed to work perfectly, but no one had ever proven it was actually true.

It was like having a map to a treasure that everyone used, but no one knew how the map was drawn. This paper finally draws the map and proves why it works.

The "Magic Formula" (The Beatty Bracket)

The authors focus on a specific relationship between the numbers $a$ and $b$. They set $b = a + \delta$, where $\delta$ is a number slightly larger than $a$ but less than twice $a$.

They found that the "losing piles" (the 0s) follow a very strange, rhythmic pattern described by a formula that looks like this:
$$w_n = n + a \times \lfloor \frac{n}{a} \rfloor + b \times \lfloor \frac{n}{\delta} \rfloor$$

The Analogy: Imagine you are walking down a street.

• Every time you take a step ($n$), you move forward 1 block.
• But, every time you pass a specific landmark (every $a$ blocks), you get a "bonus jump" of $a$ blocks.
• And every time you pass a different landmark (every $\delta$ blocks), you get another "bonus jump" of $b$ blocks.

The formula tells you exactly where you land after $n$ steps. The authors proved that if you land on these specific spots, you are in a losing position.

The Four Zones of the Game

The most exciting part of the paper is that they didn't just find the losing spots (0s); they figured out the entire landscape of the game. They discovered that every single pile size in the universe of this game falls into exactly one of four categories, like four different colored zones on a map:

1. Zone 0 (The Trap): The losing spots found by the magic formula.
2. Zone 1 (The Easy Win): These are just the Zone 0 spots, but shifted forward by $a$. If you are here, you can just take $a$ stones and dump your opponent into Zone 0.
3. Zone 2 (The Medium Win): These are the Zone 0 spots, but shifted backward by $b$. If you are here, you can take $b$ stones to land in Zone 0.
4. Zone 3 (The Tricky Win): This is the most complex zone. It's a mix of spots that are "almost" Zone 0 but shifted by a different amount.

The "Tetris" Metaphor:
Imagine the game board is a long strip of tiles. The authors proved that if you take the pattern of "losing tiles" (Zone 0) and slide copies of it to the right and left, these four patterns fit together perfectly like Tetris blocks. They fill the entire strip without any gaps and without any overlaps. Every single number belongs to exactly one zone.

How They Solved It: The "Gap" Detective Work

How did they prove this? They looked at the gaps between the losing numbers.

• In a simple game, the gaps between losing numbers are always the same (like 1, 1, 1, 1).
• In this complex game, the gaps are a mix of four different sizes: small steps (1), medium steps ($a+1$), and big jumps.

The authors realized these gaps follow a strict rhythm based on the remainders of numbers when divided by $a$ and $\delta$. They treated the problem like a puzzle:

1. They counted how many times the "losing spots" would accidentally overlap if you shifted the pattern by a certain amount (specifically by $\delta$).
2. They used a clever counting method (involving "collision windows") to prove that the number of overlaps was exactly what was needed to make the four zones fit together perfectly.

Why Does This Matter?

1. It Solves a 40-Year-Old Mystery: This formula appeared in the famous book Winning Ways for Your Mathematical Plays in 1982, but it was just a claim. This paper provides the first rigorous proof.
2. It Reveals Hidden Order: It shows that even in games that look chaotic and complex, there is a deep, beautiful mathematical structure (rhythms and patterns) that governs the outcome.
3. It Opens New Doors: The techniques they used to count these "collisions" might help solve other complex games or even problems in pure number theory that have nothing to do with games.

In a Nutshell

The authors took a complex game, found a secret rhythm that determines who wins, and proved that this rhythm divides the entire game into four perfect, non-overlapping zones. They did it by acting like detectives, counting the tiny gaps between the winning and losing moves to show that the pieces fit together like a perfect puzzle.

Technical Summary

Here is a detailed technical summary of the paper "Additive Subtraction Games" by Urban Larsson and Hikaru Manabe.

1. Problem Statement

The paper addresses a specific class of combinatorial games known as additive subtraction games.

• Game Rules: Two players alternate removing a number of counters $s$ from a heap, where $s$ must belong to a fixed set $S = \{a, b, a+b\}$. The game ends when a player cannot move (i.e., the heap size is smaller than the smallest element in $S$).
• Objective: Determine the nim-values (or nimbers) for every heap position $n \in \mathbb{N}_0$. The nim-value is defined recursively by the mex (minimum excluded value) rule: the smallest non-negative integer not present among the nim-values of the positions reachable in one move.
• Specific Regime: The authors focus on the primitive quadratic regime, defined by the parameters:
  • $b = a + \delta$
  • $a < \delta < 2a$
  • $\gcd(a, \delta) = 1$
• Context: This problem was previously posed in Winning Ways for your Mathematical Plays (Berlekamp et al., 1982). While a closed-form formula for the P-positions (positions with nim-value 0) involving Beatty-type bracket expressions was conjectured, a rigorous proof was missing. Previous work (Miklós and Post, 2024) established periodicity but did not provide the explicit closed-form structure for all nim-values.

2. Methodology

The authors employ a combination of game-theoretic induction and elementary number theory to solve the problem.

• Candidate Sets: They define a candidate set of P-positions ($W_0$) using a closed-form expression involving floor functions (bracket expressions):
  $$w_n = n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$$
  They hypothesize that the sets of positions for nim-values 0, 1, 2, and 3 are affine translations of $W_0$:

  • $W_0$: Nim-value 0 (P-positions)
  • $W_1 = W_0 + a$: Nim-value 1
  • $W_2 = W_0 - b$: Nim-value 2
  • $W_3 = (W_0 - \delta) \setminus W_0$: Nim-value 3

• Verification Strategy (Mex Rule): To prove these sets are correct, they must verify two conditions for every position $x$:

  1. Anti-collision: No move connects two positions within the same set $W_i$.
  2. Reachability: From any position in $W_i$ ($i > 0$), there exists a move to a position in $W_j$ for every $j < i$.

• Gap Analysis: A core technical component involves analyzing the gap sequence $g_n = w_{n+1} - w_n$. The authors prove that in the primitive quadratic regime, the gaps take only four possible values: $\{1, a+1, b+1, a+b+1\}$. The distribution of these gaps is determined by the residue classes of $n$ modulo $a$ and $\delta$.

• Collision Counting: A critical step is counting the "collisions" where a shift of the set $W_0$ overlaps with itself. Specifically, they count the size of the set $C = (W_0 - \delta) \cap W_0$. This requires analyzing "collision windows"—sequences of consecutive gaps that sum exactly to $\delta$.

3. Key Contributions and Results

A. Proof of the Closed-Form P-Positions

The paper provides the first complete proof that the set $W_0$ defined by the formula above constitutes exactly the set of P-positions (nim-value 0) for the game $\{a, a+\delta, 2a+\delta\}$ under the condition $a < \delta < 2a$.

B. Complete Nim-Value Classification (Main Theorem)

The authors establish a tetra-partition of the natural numbers $\mathbb{N}_0$ into four disjoint sets corresponding to nim-values 0, 1, 2, and 3:

1. Nim-value 0: $W_0 = \{w_n : n \ge 0\}$
2. Nim-value 1: $W_1 = W_0 + a$
3. Nim-value 2: $W_2 = W_0 - b$
4. Nim-value 3: $W_3 = (W_0 - \delta) \setminus W_0$

They prove that these sets are pairwise disjoint and their union covers all natural numbers.

C. The $\delta$-Collision Counting Theorem

A significant number-theoretic result derived in the paper is the exact count of collisions in one period.

• Theorem: In one heap-period of length $(3\delta + a)a$, the number of elements in the intersection $(W_0 - \delta) \cap W_0$ is exactly $a(\delta - a)$.
• Mechanism: The proof categorizes the $(a+1)$-gaps in the sequence based on their residue $r$ modulo $\delta$. It defines "collision windows" (sums of gaps equal to $\delta$) and counts how many such windows exist for each residue class. The total count is derived by summing these contributions across three residue regions (left-restricted, unrestricted, right-restricted), yielding the elegant result $ad$ (where $d = \delta - a$).

D. Periodicity Analysis

The paper clarifies the periodicity of the game:

• Index-period: $a\delta$ (the period of the sequence of indices $n$).
• Heap-period: $(3\delta + a)a$ (the period of the actual heap sizes $w_n$).
  The authors show that the arithmetic structure of the P-positions is driven by the regular gap structure determined by residues modulo $a$ and $\delta$.

4. Significance

• Resolution of a Long-standing Open Problem: The paper resolves a claim made in Winning Ways (1982) that had remained unproven for decades.
• Structural Insight: It demonstrates that the "quadratic complexity" of additive subtraction games with three moves is entirely captured by the primitive quadratic regime ($a < \delta < 2a$). Outside this regime, the problem simplifies to linear complexity or regular expansions.
• New Mathematical Tools: The introduction of "collision windows" and the detailed residue-based analysis of bracket expressions provides a new toolkit for studying affine translations of Beatty-type sequences.
• Game-Theoretic Partitioning: The work connects combinatorial game theory with number theory, showing how specific affine translations of a single bracket expression can partition the natural numbers into sets with distinct game-theoretic values.
• Future Directions: The paper opens questions regarding the extension of these bracket expressions to games with more than three moves (higher polynomial degrees) and the generalization of collision structures to arbitrary shifts $k$.

In summary, Larsson and Manabe provide a rigorous, complete characterization of the nim-values for a specific but complex class of subtraction games, proving that the solution relies on a precise interplay between floor functions, modular arithmetic, and the geometric distribution of gaps in the P-position sequence.