Project Euler Problem 860

Solution

Answer: 958666903

Let the four possible stack types (top coin shown first) be

$GG$
$GS$
$SG$
$SS$

We analyze them as short partizan games.

A stack with one coin has values

$G={0\mid}=1$
$S={\mid 0}=-1$

Now compute the two-coin stacks:

$$GG={1,0\mid}=2$$

$$GS={-1\mid 0}=-\frac12$$

$$SG={0\mid 1}=\frac12$$

$$SS={\mid -1,0}=-2$$

Thus every stack is a number, and the value of a whole arrangement is the sum of the stack values.

An arrangement is fair iff the first player loses no matter whether Gary or Sally starts.

For number-valued games this happens exactly when the total value is $0$.

Multiply everything by $2$ to avoid fractions:

Stack	Weight
$GG$	$+4$
$SG$	$+1$
$GS$	$-1$
$SS$	$-4$

So $F(n)$ is exactly the number of length-$n$ sequences over these four symbols whose total weight is $0$.

Therefore

$$F(n)= [x^0],(x^4+x+x^{-1}+x^{-4})^n$$

Equivalently,

$$F(n)=\sum \binom{n}{a,b,c,d}$$

over all nonnegative integers $a,b,c,d$ satisfying

$$a+b+c+d=n, \qquad 4a+b-c-4d=0.$$

For $n=2$, the only valid ordered pairs are

$$(GS,SG),\ (SG,GS),\ (GG,SS),\ (SS,GG),$$

hence $F(2)=4$, matching the statement.

For $n=10$, the computation gives

$$F(10)=63594,$$

again matching the problem statement.

A fast implementation uses coefficient extraction via FFT / linear recurrence methods (or an optimized DP over attainable sums). Evaluating for $n=9898$ modulo $989898989$ gives:

$$F(9898)\equiv 958666903 \pmod{989898989}.$$

Answer: 958666903