Detailed mathematical approach

Problem Summary

We have \(n\) ordered stacks, each containing exactly two coins colored gold or silver. Gary may remove only gold coins, Sally may remove only silver coins, and removing a coin also removes every coin above it in the same stack. An arrangement is called fair if the first player loses regardless of whether Gary or Sally is the one who starts. The goal is to compute \(F(n)\), the number of fair arrangements, for \(n=9898\) modulo \(989898989\).

Mathematical Approach

The key simplification is that each height-2 stack has a small numerical game value. Since the full position is the disjunctive sum of the \(n\) stacks, counting fair arrangements becomes a coefficient-extraction problem for those local values.

Step 1: Evaluate the Four Possible Stack Types

Let \(0\) denote the empty stack. A single gold coin has value \(\{0 \mid\}=1\), because Gary can move to \(0\) while Sally has no move. Similarly, a single silver coin has value \(\{\mid 0\}=-1\).

Now consider a stack of height \(2\), written from bottom to top:

$\begin{aligned} GG&=\{0,1 \mid\}=2,\\ GS&=\{0 \mid 1\}=\frac{1}{2},\\ SG&=\{-1 \mid 0\}=-\frac{1}{2},\\ SS&=\{\mid -1,0\}=-2. \end{aligned}$

The implementations do not work with fractions. Multiplying every local value by \(2\) clears the denominators and does not change which total sums are zero, so the four stack types become the integer step set

$\{4,1,-1,-4\}.$

Step 2: Turn Fairness into a Zero-Sum Condition

The whole arrangement is the sum of the \(n\) local games. Because all four local games are numbers, their disjunctive sum is just ordinary addition. Therefore an arrangement is fair exactly when the sum of the scaled local values is \(0\).

If the stacks contribute scaled values \(a_1,\dots,a_n\in\{4,1,-1,-4\}\), then the fairness condition is simply

$a_1+\cdots+a_n=0.$

So \(F(n)\) is the number of ordered length-\(n\) sequences over \(\{4,1,-1,-4\}\) whose total is zero.

Step 3: Encode the Count with a Generating Function

Introduce the Laurent polynomial

$P(x)=x^4+x+x^{-1}+x^{-4}.$

Choosing one stack means choosing one monomial from \(P(x)\). After \(n\) stacks, the exponent records the scaled total, so the number of fair arrangements is the constant term

$F(n)=[x^0]P(x)^n.$

If one prefers ordinary polynomials only, multiply by \(x^{4n}\) and rewrite this as

$F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.$

The two forms are equivalent; the implementation follows the centered constant-term viewpoint.

Step 4: Convert Coefficient Extraction into Dynamic Programming

Let \(D_k(s)\) be the number of length-\(k\) stack sequences whose scaled total is \(s\). Then

$D_0(0)=1,$

$D_0(s)=0 \quad \text{for } s\ne 0,$

and each new stack contributes one of the four steps, giving

$D_{k+1}(s)=D_k(s-4)+D_k(s-1)+D_k(s+1)+D_k(s+4).$

The answer is therefore

$F(n)=D_n(0)\pmod{989898989}.$

After \(k\) stacks the total must lie in \([-4k,4k]\), so the reachable state space grows only linearly with \(k\).

Worked Example: \(n=2\)

With two stacks, we need ordered pairs from \(\{4,1,-1,-4\}\) whose sum is zero. The only possibilities are

$ (4,-4),\quad (-4,4),\quad (1,-1),\quad (-1,1). $

Hence

$F(2)=4.$

This is the first useful checkpoint for the recurrence, and a larger checkpoint is \(F(10)=63594\).

How the Code Works

The C++, Python, and Java implementations all use the same rolling dynamic program. They allocate two arrays large enough to hold every reachable total together with a small safety margin for the \(\pm 4\) transitions. A fixed center index represents total \(0\), negative totals sit to the left, and positive totals sit to the right.

The current layer starts with only the center entry equal to \(1\). For each of the \(n\) stacks, the implementation clears the next layer, restricts the loop to the currently reachable interval \([-4k,4k]\), and fills each state by summing the four predecessor states corresponding to the four possible stack types. Every update is reduced modulo \(989898989\), then the two layers are swapped. After the last stack, the center entry is exactly \(F(n)\).

Complexity Analysis

At step \(k\), there are \(8k+1\) reachable totals. Therefore the total number of state updates is

$\sum_{k=1}^{n}(8k+1)=4n(n+1)+n=O(n^2).$

Only two layers are stored, each of size \(O(n)\), so the memory usage is \(O(n)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=860
2. Combinatorial game theory: Wikipedia — Combinatorial game theory
3. Partisan game: Wikipedia — Partisan game
4. Generating function: Wikipedia — Generating function
5. Dynamic programming: Wikipedia — Dynamic programming