Problem 306: Paper-strip Game

Project Euler Problem 306 Solution

EulerSolve provides an optimized solution for Project Euler Problem 306, Paper-strip Game, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We play on a strip of length $n$. A move removes two adjacent cells, so the strip breaks into a left part and a right part. Under normal play, the player who makes the last legal move wins. The Project Euler question asks for how many lengths $1 \le n \le 10^6$ the starting player has a winning strategy. Mathematical Approach 1) This is an impartial splitting game If we remove the domino covering positions $\ell+1$ and $\ell+2$, the remaining cells split into two independent strips of lengths $$\ell \quad \text{and} \quad n-2-\ell.$$ Because the two sides no longer interact, the position after one move is the disjoint sum of two smaller games. That is exactly the setting where Sprague-Grundy theory applies. 2) Grundy recurrence Let $g(n)$ be the Grundy number of a strip of length $n$. The empty strip and the length-1 strip have no legal move, so $$g(0)=0,\qquad g(1)=0.$$ For $n \ge 2$, every legal move produces the xor of two smaller Grundy numbers, hence $$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$ The mex operator returns the smallest nonnegative integer that does not appear among the reachable xor-values....

Detailed mathematical approach

Problem Summary

Two players share a strip of $n$ white squares and move alternately. A move picks two contiguous white squares and paints both black. A player with no such pair left loses, so whoever paints the last pair wins. With both sides playing as well as possible, the task is to count the lengths $1\le n\le 10^6$ for which the player who starts can force a win. ^[1] The statement gives two counts: among $1\le n\le 5$ the first player wins for $3$ lengths, and among $1\le n\le 50$ for $40$ lengths.

The whole solution in one sentence: a move cuts the strip into two pieces that no later move can join again, so Sprague–Grundy theory compresses every length $n$ into a single number $g(n)$ that is zero exactly when the player to move loses, and this sequence repeats with period $34$ from $n=53$ onwards, which turns the count into arithmetic on residues.

Mathematical Approach

1. Positions, and the kind of game this is

Black squares never become white again, so after a few moves the white squares form separated runs. Two contiguous white squares always lie inside one run, and painting a pair inside a run of length $L$ leaves two new runs, of lengths $a$ and $L-2-a$ with $0\le a\le L-2$; a run of length $0$ or $1$ offers no move. A position is therefore just a multiset of run lengths: a move changes one of them, and where they sit on the strip carries no further information.

Both players have the same moves, the game is finite because every move paints two more squares, and whoever cannot move loses: such a game is impartial under the normal play convention. A position is losing when every move hands the opponent a winning position, and winning otherwise.

2. The Grundy value and the mex rule

In Nim a move takes any positive number of counters from one heap, and the player with no move loses. The Sprague–Grundy theorem says that every position $P$ of a finite impartial game behaves like a single Nim heap of some size $G(P)$, its Grundy value, and that $P$ is losing exactly when $G(P)=0$. ^[2] The value is read off the values reachable in one move by the minimum excludant $\operatorname{mex}$, the smallest non-negative integer missing from a set. ^[3] For example $\operatorname{mex}\{\,\}=0$, $\operatorname{mex}\{0\}=1$, $\operatorname{mex}\{1\}=0$ and $\operatorname{mex}\{0,1,2\}=3$; a position with no move gets $0$, matching the rule that it is losing.

3. Several runs at once: the exclusive-or rule

Two separated runs of length $2$ show why winning parts cannot simply be counted: whoever moves paints one pair, the opponent the other, and the first player is stuck. Each run alone has value $1$ and is winning, yet the pair is losing. The theorem's second half explains this: the Grundy value of independent parts is the nim-sum of their values, their binary exclusive-or $\oplus$, adding binary digits modulo $2$ with no carries, so $1\oplus1=0$ and $2\oplus3=1$ because $2=10_2$ and $3=11_2$. ^[2] ^[4] A position with runs of lengths $L_1,\dots,L_k$ is therefore losing precisely when

$$g(L_1)\oplus\cdots\oplus g(L_k)=0,$$

where $g(L)$ is the value of one run of length $L$. Only the one-run values $g(0),g(1),g(2),\dots$ are ever needed.

4. The recurrence for one run

Combining Sections 1, 2 and 3, a move on a run of length $n$ leads to two runs $a$ and $b$ with $a+b=n-2$, of value $g(a)\oplus g(b)$. Write

$$\begin{aligned} O(n)=\bigl\{\,&g(a)\oplus g(b)\ :\\ &a,b\ge0,\\ &a+b=n-2\,\bigr\} \end{aligned}$$

for the values reachable from one run of length $n$. A run of $0$ or $1$ has no move, so $g(0)=g(1)=0$, and

$$g(n)=\operatorname{mex}O(n)\qquad(n\ge2).$$

Because $\oplus$ is commutative, a split and its mirror give the same number, so letting $a$ run over $0\le a\le\lfloor (n-2)/2\rfloor$ leaves $O(n)$ unchanged and halves the work. Every index used is smaller than $n$, so the values can be filled in increasing order.

5. The first values by hand

The smallest cases can be checked by hand.

$n=0,1$: no move, so $g=0$ and the player to move loses.
$n=2$: the single move leaves nothing, value $g(0)\oplus g(0)=0$, so $g(2)=\operatorname{mex}\{0\}=1$.
$n=3$: both moves leave one dead square, value $g(0)\oplus g(1)=0$, so $g(3)=\operatorname{mex}\{0\}=1$.
$n=4$: the three moves give $g(0)\oplus g(2)=1$, $g(1)\oplus g(1)=0$ and $g(2)\oplus g(0)=1$, so $g(4)=\operatorname{mex}\{0,1\}=2$. The move of value $0$ paints the two middle squares, exactly the winning move named in the statement.
$n=5$: the four moves give $g(0)\oplus g(3)=1$ and $g(1)\oplus g(2)=1$, each twice, so the reachable set is $\{1\}$ and $g(5)=\operatorname{mex}\{1\}=0$. Every move leaves a winning position for the opponent, which is the picture drawn in the statement.
$n=6$: the moves give $g(0)\oplus g(4)=2$, $g(1)\oplus g(3)=1$ and $g(2)\oplus g(2)=0$, so $g(6)=\operatorname{mex}\{0,1,2\}=3$.

Continuing in the same way gives the values $g(0)$ to $g(16)$:

$$\begin{aligned} &0,0,1,1,2,0,3,1,1,\\ &0,3,3,2,2,4,0,5. \end{aligned}$$

6. The checkpoints of the statement

A length is winning exactly when $g(n)\ne0$. Among the lengths $1\le n\le52$ the zeros sit at

$$\begin{aligned} n=\ &1,5,9,15,21,\\ &25,29,35,39,43, \end{aligned}$$

ten lengths in all. Among $1\le n\le 5$ only $n=1$ and $n=5$ are zeros, leaving $3$ winning lengths, and among $1\le n\le 50$ the same ten zeros leave $40$. Both counts of the statement are reproduced.

7. The game has a name

In the standard code $.d_1d_2d_3\dots$ the digit $d_k$ adds $1$ if a heap of exactly $k$ tokens may be taken entirely, $2$ if $k$ may be taken leaving one non-empty heap, and $4$ if $k$ may be taken and the rest split in two. ^[5] Here only $k=2$ is legal, and all three shapes occur: a run of exactly $2$ disappears, a pair at the end of a longer run leaves one piece, a pair in the middle leaves two. So $d_2=1+2+4=7$ and our game is the octal game $.07$, known as Dawson's Kayles. Its values are those of Dawson's Chess, the game $.137$ from a chess puzzle of Thomas Rayner Dawson, shifted by one index: in the numbering of OEIS A002187, $g(n)=a(n-1)$ for $n\ge1$. ^[6]

8. The sequence becomes periodic

Filling the recurrence up to $n=20000$ reveals a pattern: $g(n+34)=g(n)$ for every $n$ with $53\le n\le 19966$. It fails at $n=52$, where $g(52)=2$ and $g(86)=9$, so $53$ is the earliest possible start of a period of $34$. One full period, $g(53)$ to $g(86)$, reads

$$\begin{aligned} &3,3,0,1,1,3,0,2,1,\\ &1,0,4,5,3,7,4,8,1,\\ &1,2,0,3,1,1,0,3,3,\\ &2,2,4,4,5,5,9. \end{aligned}$$

Exactly five of these $34$ values are $0$, at $n=55,59,63,73,77$, whose residues modulo $34$ are $21,25,29,5,9$. Continued backwards, the block predicts most smaller values correctly, failing at exactly eight lengths,

$$\begin{aligned} n=\ &0,1,15,17,\\ &18,32,35,52. \end{aligned}$$

Apart from $n=0$, which has no counterpart in the shifted numbering of Section 7, these are exactly the exceptions recorded for A002187. ^[6]

9. Why a finite check proves the period

A computed pattern is not a theorem, and it is open whether every finite octal game, one whose code has finitely many non-zero digits, has an eventually periodic sequence of values. ^[5] For a fixed period, though, a finite check suffices, and the reason is short. ^[7]

Claim. Let $p\ge1$ and $n_0\ge0$. If $g(n+p)=g(n)$ for every $n$ with $n_0\le n\le 2n_0+2p+2$, then $g(n+p)=g(n)$ for every $n\ge n_0$.

Proof. Since $g=\operatorname{mex}O$ by Section 4, it is enough to show that the option sets $O(N)$ and $O(N+p)$ coincide. We use strong induction on $N$; the hypothesis of the claim settles every $N\le 2n_0+2p+2$. So let $N\gt 2n_0+2p+2$ and assume $g(m+p)=g(m)$ for all $m$ with $n_0\le m\lt N$. Since $N-2\gt 2(n_0+p)$, in any splitting $a+b=N-2$ the larger part exceeds $n_0+p$, and the same holds for $a+b=N+p-2$. Take $a+b=N-2$ with $b$ the larger part. Then $n_0\le b\lt N$, so $g(b+p)=g(b)$ by the hypothesis of the induction, and $a+(b+p)=N+p-2$; hence $g(a)\oplus g(b)\in O(N+p)$, so $O(N)\subseteq O(N+p)$. Conversely take $a+b=N+p-2$ with $b$ the larger part. Then $b-p\gt n_0$ and $b-p\le N-2\lt N$, so $g(b)=g(b-p)$, and $a+(b-p)=N-2$; hence $O(N+p)\subseteq O(N)$. The two sets are equal, so their minimum excludants agree and $g(N+p)=g(N)$. $\square$

The $+2$ in the bound is the number of squares a move removes. With $n_0=53$ and $p=34$ the claim asks for the pattern on $53\le n\le 176$; Section 8 covers that range, so the period is proved and $g(n)$ depends only on $n\bmod 34$ for every $n\ge53$. The largest Grundy value anywhere is therefore $\max\{g(0),\dots,g(86)\}=9$, attained at $n=86$.

10. Which lengths lose, and how to count

For $n\ge53$ the value vanishes exactly for the five residues of Section 8. Of the ten zeros below $53$, seven, namely $5,9,21,25,29,39,43$, are precisely the $n\le52$ with one of those residues; the others are $1,15,35$. With $R=\{5,9,21,25,29\}$ this proves, for every $n\ge1$, that $g(n)=0$ holds exactly when $n\bmod 34\in R$ or $n\in\{1,15,35\}$, and $n$ is winning otherwise. Counting is then immediate: for $M\ge35$ the number of winning lengths in $1\le n\le M$ is

$$\begin{aligned} W(M)&=M-3-\sum_{r\in R}c_r,\\ c_r&=\left\lfloor\frac{M-r}{34}\right\rfloor+1. \end{aligned}$$

At $M=50$ the five numbers $c_r$ are $2,2,1,1,1$, so $W(50)=47-7=40$, the checkpoint of the statement; $W(100)=82$ and $W(1000)=850$ agree with a direct scan too. In the long run $29$ of every $34$ lengths are winning, a density of $29/34\approx0.8529$.

How the Code Works

compute_grundy(n) implements Section 4. ^[8] It sets up grundy with $n+1$ zero entries and an array seen of $2048$ entries set to $-1$, then loops len from $1$ to $n$. The inner loop runs left while left <= len - 2 - left, the half range of Section 4; for len equal to $1$ it fails at once, so $g(1)$ keeps its initial $0$.

The mex is taken without clearing anything. For each reachable value the code writes seen[value] = len, a timestamp, then runs while (seen[grundy[len]] == len) ++grundy[len];, which walks up from the zero-initialised entry to the first integer not stamped with the current len; older stamps carry a smaller number and are ignored. Its index is an exclusive-or of two Grundy values, which by Section 9 never exceed $9$, so it stays below $16$: the $2048$ entries are a generous margin.

solve fixes prefix = 100 and period = 34, builds the table up to $\max(134,1200)=1200$ and counts. For a length up to $100$ it reads $g$ directly, otherwise g[(len - prefix) % period + prefix], an index in $100\dots133$. The prefix of $100$ is comfortably above the $53$ of Section 9, and the loop counts the lengths whose value is non-zero.

Only the C++ file carries run_checkpoints. It verifies g[i] == g[(i - 100) % 34 + 100] for $100\le i\le1200$, exactly the hypothesis of Section 9 with $n_0=100$ and $p=34$ over $100\le n\le1166$, far beyond the $270$ the claim demands: the program proves its periodicity assumption rather than sampling it. It then confirms the counts $3$ and $40$ of the statement, main exiting with status $2$ on failure. The options --limit= and --skip-checkpoints change the bound and drop the checks.

Python uses compute_grundy and Java computeGrundy; both implement the same recurrence and counting loop, return the count from solve as a string, and run no checkpoints. Python's half range range((length - 2) // 2 + 1) is empty for length equal to $1$, since its floor division gives $-1$; Java fills seen with $-1$ explicitly and keeps the limit at $10^6$. For the requested bound a 32-bit int suffices in C++ and Java, the counter staying below $10^6$ and every value below $10$, while Python uses arbitrary-precision integers. The guarantee is tied to that bound: the C++ --limit= parser accumulates digits in an int without an overflow check, so an argument of $2^{31}$ or more overflows while being parsed. Each call to solve also rebuilds the table, so a complete run with checkpoints builds it four times, once in run_checkpoints and once per solve.

Complexity and Verification

With $P$ the precomputed prefix, building the table costs

$$\sum_{\ell=2}^{P}\left(\left\lfloor\frac{\ell-2}{2}\right\rfloor+1\right)\approx\frac{P^2}{4}$$

inner steps, exactly $360\,000$ for $P=1200$, plus at most ten steps per length for the mex; the counting loop is $\Theta(N)$, so the program runs in $O(P^2+N)$ time. Storage is $O(P)$ and independent of $N$: one C++ or Java table build holds $1201$ plus $2048$ four-byte integers, $12\,996$ bytes of elements, with a peak of $17\,800$ bytes while run_checkpoints keeps its own table alive during a call to solve; Python's lists of object references are not described by that figure. The formula of Section 10 would make the counting step $O(1)$; the programs keep the linear scan, and all three finish in well under a second.

The following was also verified for this article. A direct game-tree search over multisets of run lengths, with no Grundy theory at all, agrees with the test $g(n)\ne0$ for every $1\le n\le26$ and finds $3$ winning lengths up to $5$ and $17$ up to $22$. The exclusive-or rule was checked on every position of three runs of length at most $8$: such a position is winning exactly when the nim-sum of the three values is non-zero. An independent table up to $n=20000$ confirms the periodicity of Section 8, the failure at $n=52$ included, and the characterisation of Section 10 throughout. Finally $W(M)$ gives $40$, $82$, $850$ and $1703$ for $M=50,100,1000,2000$, each also found by scanning the table, and the C++ binary prints $3$ and $40$ with --limit=5 and --limit=50.

Footnotes and References

The references below supply the background facts. The recurrence of Section 4, the periodicity claim of Section 9 with its proof, the characterisation of the losing lengths and the counting formula are derived here.

Project Euler 306 — Paper-strip Game. In the official statement two players alternately paint two contiguous white squares black on a strip of n squares and whoever cannot move loses. It gives 3 winning lengths for 1 ≤ n ≤ 5 and 40 for 1 ≤ n ≤ 50, notes the win at n = 4 by painting the two middle squares, and asks for the count up to 1000000.
Wikipedia — Sprague–Grundy theorem. Every impartial game under the normal play convention is equivalent to a one-heap game of Nim, or to an infinite generalisation of Nim when it is not finite; a position is a loss for the player to move exactly when its Grundy value is zero, that value is the mex of its options' values, and the value of a sum of positions is the nim-sum of their values.
Wikipedia — Mex (mathematics). The minimum excludant of a set is the smallest value absent from it; the mex of the empty set is 0 and the mex of {0, 1, 4, 7, 12} is 2. It also gives the rule used here: a position's nim-value is the mex of the values reachable in one move.
Wikipedia — Nim. A move takes any positive number of counters from one heap; the nim-sum of the heap sizes is their binary sum without carries, also known as bitwise exclusive-or, and in normal play the first player wins exactly when it is not zero.
Wikipedia — Octal game. The digit d_k adds 1 if a heap of k may be removed entirely, 2 if k may be removed leaving one heap, and 4 if k may be removed leaving two; in 0.07, called Dawson's Kayles, a move removes exactly two tokens from a heap, and Dawson's Chess has the code 0.137 and comes from a chess puzzle of Thomas Rayner Dawson. Whether every finite octal game is ultimately periodic is an open question.
OEIS A002187 — Sprague-Grundy values for Dawson's Chess (octal game .137). The entry notes that the octal game .07, Dawson's Kayles, has the values a(n − 1), and that the sequence has period 34 with the only exceptions at n = 0, 14, 16, 17, 31, 34 and 51; adding 1 to each gives the exceptional lengths of Section 8 other than 0.
A. Flammenkamp — Sprague-Grundy Values of Octal Games. The page tabulates computed periods and states that a period p is established by checking G(i + p) = G(i) over a finite window of successive values. Its bibliography lists R. K. Guy and C. B. Smith, The G-values of various games, Proc. Cambridge Philos. Soc. 52, pp. 514–526, where such criteria originate; the abstract of A. N. Siegel, Misère Games and Misère Quotients states that those notes prove the Guy–Smith–Plambeck periodicity theorem.
C++ — Euler306.cpp. The linked immutable revision contains compute_grundy, solve, run_checkpoints and the argument parsing described above. It is the implementation record for this article.

Problem 306 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

struct Options {
    int limit = 1000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

std::vector<int> compute_grundy(const int n) {
    std::vector<int> grundy(static_cast<std::size_t>(n + 1), 0);
    std::vector<int> seen(2048, -1);

    for (int len = 1; len <= n; ++len) {
        for (int left = 0; left <= len - 2 - left; ++left) {
            const int value = grundy[static_cast<std::size_t>(left)] ^
                              grundy[static_cast<std::size_t>(len - 2 - left)];
            seen[static_cast<std::size_t>(value)] = len;
        }
        while (seen[static_cast<std::size_t>(grundy[static_cast<std::size_t>(len)])] == len) {
            ++grundy[static_cast<std::size_t>(len)];
        }
    }
    return grundy;
}

int solve(const int limit) {
    const int prefix = 100;
    const int period = 34;
    const int max_precompute = std::max(prefix + period, 1200);
    const std::vector<int> g = compute_grundy(max_precompute);

    int wins = 0;
    for (int len = 1; len <= limit; ++len) {
        const int sg = (len <= prefix) ? g[static_cast<std::size_t>(len)]
                                       : g[static_cast<std::size_t>((len - prefix) % period + prefix)];
        wins += (sg != 0);
    }
    return wins;
}

bool run_checkpoints() {
    const std::vector<int> g = compute_grundy(1200);
    for (int i = 100; i <= 1200; ++i) {
        if (g[static_cast<std::size_t>(i)] != g[static_cast<std::size_t>((i - 100) % 34 + 100)]) {
            std::cerr << "Checkpoint failed for Grundy periodicity" << '\n';
            return false;
        }
    }
    if (solve(5) != 3) {
        std::cerr << "Checkpoint failed for [1,5]" << '\n';
        return false;
    }
    if (solve(50) != 40) {
        std::cerr << "Checkpoint failed for [1,50]" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

def compute_grundy(n):
    grundy = [0] * (n + 1)
    seen = [-1] * 2048
    
    for length in range(1, n + 1):
        for left in range((length - 2) // 2 + 1):
            right = length - 2 - left
            value = grundy[left] ^ grundy[right]
            seen[value] = length
            
        while seen[grundy[length]] == length:
            grundy[length] += 1
            
    return grundy

def solve(limit=1000000):
    prefix = 100
    period = 34
    max_precompute = max(prefix + period, 1200)
    g = compute_grundy(max_precompute)
    
    wins = 0
    for length in range(1, limit + 1):
        if length <= prefix:
            sg = g[length]
        else:
            sg = g[(length - prefix) % period + prefix]
        if sg != 0:
            wins += 1
            
    return str(wins)

if __name__ == '__main__':
    print(solve())

Java

public class Euler306 {
    static int[] computeGrundy(int n) {
        int[] grundy = new int[n + 1];
        int[] seen = new int[2048];
        for (int i = 0; i < 2048; i++) {
            seen[i] = -1;
        }

        for (int len = 1; len <= n; ++len) {
            for (int left = 0; left <= len - 2 - left; ++left) {
                int value = grundy[left] ^ grundy[len - 2 - left];
                seen[value] = len;
            }
            while (seen[grundy[len]] == len) {
                ++grundy[len];
            }
        }
        return grundy;
    }

    public static String solve() {
        int limit = 1000000;
        int prefix = 100;
        int period = 34;
        int maxPrecompute = Math.max(prefix + period, 1200);
        int[] g = computeGrundy(maxPrecompute);

        int wins = 0;
        for (int len = 1; len <= limit; ++len) {
            int sg;
            if (len <= prefix) {
                sg = g[len];
            } else {
                sg = g[(len - prefix) % period + prefix];
            }
            if (sg != 0) {
                wins++;
            }
        }
        return String.valueOf(wins);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}