Detailed mathematical approach

Problem Summary

We consider positions made from piles of cookies whose total size is \(N\). Odd may move only on an odd pile: from a pile of size \(2m+1\), Odd eats one cookie and replaces that pile by two piles of size \(m\). Even may move only on an even pile: from a pile of size \(2m\), Even eats two cookies and replaces that pile by two piles of size \(m-1\).

A position is therefore an integer partition of \(N\). Let \(C(N)\) be the number of such partitions for which Even has a winning strategy when Odd moves first. Directly exploring all partitions together with all move trees is far too expensive for \(N=300\), so the solution converts each pile into an exact short partizan game and then counts partitions by the canonical sum of those games.

Mathematical Approach

Let \(G_n\) denote the game value of a single pile of size \(n\). Because every move strictly reduces pile sizes, these are finite short games, so Conway's recursive theory applies exactly.

Step 1: Derive the Single-Pile Recurrence

The empty pile has no moves, so

$G_0=0=\{\varnothing\mid\varnothing\}.$

If \(n=2m+1\) is odd, only Odd has a legal move, and that move replaces the pile by two piles of size \(m\). Therefore

$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$

If \(n=2m\) is even, only Even has a legal move, and that move replaces the pile by two piles of size \(m-1\). Hence

$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$

This recurrence is the mathematical core of the whole solution: every pile value is built from the value of a smaller pile doubled under disjunctive sum.

Step 2: Convert a Partition into a Disjunctive Sum

If a position has piles \(n_1,n_2,\dots,n_r\), then the players choose exactly one pile on each move, so the total position is the disjunctive sum

$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}.$

Equivalently, for a partition written in frequency form

$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots,$

the total game is

$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k.$

The outcome class of \(V(\lambda)\) is one of the standard four classes:

$L,\ N,\ P,\ R,$

where \(L\) means Odd wins regardless of who starts, \(R\) means Even wins regardless of who starts, \(N\) means the next player wins, and \(P\) means the previous player wins. Since the problem asks for positions where Odd starts and Even wins, the desired partitions are exactly those whose total game lies in class \(P\) or class \(R\).

Step 3: Reduce Each Game to Canonical Form

To compare and combine games exactly, the implementation stores every short game in canonical Conway form

$G=\{G^L\mid G^R\}.$

The recursive order relation is

$G\le H \iff \text{there is no left option } G^L \text{ with } H\le G^L,\ \text{and no right option } H^R \text{ with } H^R\le G.$

Using this order, one removes dominated options. For example, a left option \(A\) is unnecessary if another left option \(B\) satisfies \(A\le B\), because choosing \(B\) is always at least as good for Odd. Symmetrically, a right option \(A\) is unnecessary if another right option \(B\) satisfies \(B\le A\).

One also removes reversible options: if a move can be answered immediately by the opponent to reach a position no worse for the responder than the original game, then that move does not need to remain as a canonical option. After repeatedly applying these reductions, equivalent games collapse to the same canonical representative, which can then be interned under one shared identifier.

Step 4: Add Games and Determine the Winner

For short games, disjunctive sum is defined recursively by

$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$

This formula exactly models the rule “choose one pile and move in that pile only.” Once a total game has been built, winner detection is also recursive: a player wins from a position if that player has some legal move to a position winning for the opponent's turn. If no legal move exists, that player loses immediately.

Evaluating that rule with Odd to move and with Even to move gives the two booleans needed to place the game into \(L,N,P,\) or \(R\). That classification is what ultimately decides whether a partition contributes to \(C(N)\).

Step 5: Count Partitions by Dynamic Programming over Canonical Games

After the single-pile games \(G_1,G_2,\dots,G_N\) have been computed, the counting problem becomes a partition DP whose states are canonical game values. Let \(D_s(g)\) be the number of partitions of total size \(s\) currently known to have total game \(g\).

Initially, the empty partition contributes one way to total \(0\):

$D_0(0)=1.$

Now process part sizes \(k=1,2,\dots,N\) in increasing order. Every existing state of total \(s-k\) can be extended by one more pile of size \(k\):

$D_s(h)\leftarrow D_s(h)+D_{s-k}(g),\qquad h\text{ is the canonical form of }g\oplus G_k.$

Because sizes are processed in nondecreasing order, each multiset of pile sizes is counted exactly once, so this is a partition count rather than a composition count. At the end,

$C(N)=\sum_{g\in\{P,R\}} D_N(g),$

meaning we sum the counts of all total games whose outcome class is \(P\) or \(R\).

Worked Example: \(C(5)=2\)

The seven partitions of \(5\) are

$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$

Only two of these outcomes are favorable for Even when Odd starts: \((5)\), which is class \(R\), and \((2,2,1)\), which is class \(P\). Therefore

$C(5)=2.$

This is the first checkpoint used by the implementations, and a second small checkpoint is \(C(16)=64\).

How the Code Works

The C++, Python, and Java implementations all follow the same stages. First they build the single-pile table from \(0\) up to \(N\), using the recurrence above. Every newly created game is reduced to canonical form immediately, so equivalent positions reuse one shared canonical identifier rather than being rebuilt over and over.

Next, the implementations memoize three exact operations on short games: comparison in the Conway order, disjunctive addition, and winner detection for a specified player to move. Those memoized results are crucial, because the same subgames and the same game sums reappear many times across different partitions.

Finally, the implementations run the partition DP over totals \(0\) through \(N\). Each DP entry is a map from a canonical game identifier to the number of partitions that realize that game. After all part sizes have been processed, the map for total \(N\) is scanned and the counts in outcome classes \(P\) and \(R\) are added together. That final sum is the desired value \(C(N)\).

Complexity Analysis

Let \(S_s\) be the number of distinct canonical game values that appear in the DP map for total \(s\). The partition phase performs one state extension for each reachable pair \((g,s-k)\), so its transition count is

$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}.$

Each transition requires one memoized disjunctive sum lookup, plus a canonical-game construction only when that exact sum has not been seen before. Precomputing the single-pile games adds \(N\) more canonical constructions of the same kind. Hence the practical runtime is governed by the number of distinct game comparisons and sums that are actually reached, not by the astronomically larger number of raw game trees.

The memory usage is the total size of the canonical game database, the comparison/addition/winner caches, and the DP maps:

$O\!\left(\sum_{s=0}^{N} S_s\right)\ \text{plus memoized short-game data}.$

For \(N=300\), this exact method remains feasible because many different partitions collapse to the same canonical game value.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=859
2. Combinatorial game theory: Wikipedia — Combinatorial game theory
3. Partisan games: Wikipedia — Partisan game
4. Disjunctive sum: Wikipedia — Disjunctive sum
5. Integer partitions: Wikipedia — Partition (number theory)