Problem 321: Swapping Counters

Project Euler Problem 321 Solution

EulerSolve provides an optimized solution for Project Euler Problem 321, Swapping Counters, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We have $n$ red counters, one empty square, and $n$ blue counters in a row of length $2n+1$. A legal move is either: 1) a slide into the adjacent empty square, or 2) a hop over exactly one counter into an empty square. Let $M(n)$ be the minimum number of moves needed to swap the two color blocks completely. We want those $n$ for which $M(n)$ is a triangular number, and we must sum the first 40 such $n$. Mathematical Approach 1) The minimal move count is $M(n)=n(n+2)$. This is the key fact. It comes from two separate lower bounds that are both forced, and both can be achieved. 2) Why there must be exactly $n^2$ hops. Initially every red counter lies to the left of every blue counter. In the final arrangement every red counter lies to the right of every blue counter. So each red-blue pair must reverse its order exactly once. There are $$n^2$$ such pairs. A slide never changes the order of two counters, while a hop over one counter changes the order of exactly one pair. Therefore every solution needs at least $$n^2$$ hops. 3) Why there must be exactly $2n$ slides. Consider total displacement. Each red counter moves from the left block to the right block, so each red moves $n+1$ squares to the right. Each blue counter moves $n+1$ squares to the left....

Detailed mathematical approach

Problem Summary

A row of $2n+1$ squares carries $n$ red counters at one end and $n$ blue counters at the other, separated by a single empty square in the centre. A counter may slide into the empty square beside it, or hop over exactly one counter into the empty square just beyond it. Let $M(n)$ be the smallest number of moves that reverses the two blocks, putting every red counter on the right and every blue counter on the left. The statement records $M(3)=15=1+2+3+4+5$, a triangular number, and lists the first five values of $n$ for which $M(n)$ is triangular as $1$, $3$, $10$, $22$, $63$, with sum $99$. We must add the first forty such values of $n$. ^[1]

The whole solution in one sentence: the puzzle always needs exactly $M(n)=n(n+2)$ moves, so asking when $M(n)$ is triangular becomes the Pell equation $x^2-8y^2=-7$, whose solutions form two chains that a two-line recurrence climbs until forty values of $n$ have been collected.

Mathematical Approach

1. Playing the puzzle by hand

For $n=1$ the row is R.B, the dot marking the empty square: the red slides into the centre, giving .RB, the blue hops left over it, giving BR., and the red slides right, giving B.R. So $M(1)=3$, and nothing shorter is possible, as Sections 3 and 4 show for every $n$.

For $n=2$ the row is RR.BB and $8$ moves suffice. One shortest line of play is

RR.BB, slide a red right: R.RBB;
hop the left blue over it: RBR.B, slide the last blue left: RBRB.;
hop a red right: RB.BR, hop the other red right: .BRBR;
slide a blue left: B.RBR, hop a blue left: BBR.R;
slide a red right: BB.RR.

Those $8$ moves split into $4$ hops and $4$ slides, and the $15$ moves of $M(3)$ split into $9$ hops and $6$ slides. The pattern $n^2$ hops and $2n$ slides is the key: Section 2 builds a solution of exactly that shape, and Sections 3 and 4 show that no solution of any kind can do better.

2. A strategy that attains $n^2+2n$

Write $R^a$ for a block of $a$ reds, $B^a$ for $a$ blues and $\circ$ for the empty square, with $R^0$ and $B^0$ empty. Everything rests on two local transformations:

$$\circ(RB)^j\longrightarrow(BR)^j\circ,$$

$$(RB)^j\circ\longrightarrow\circ(BR)^j.$$

The first is a run of $j$ blue hops to the left, the second a run of $j$ red hops to the right; in both, every hop jumps the next red-blue pair and leaves the empty square beside the following pair, so each move of the run is legal.

Open by sliding the red beside the empty square to the right, which gives $R^{n-1}\circ RB^{n}$, to which the first transformation with $j=1$ applies at once. After a run of $j$ hops the position is

$$R^{n-j}(BR)^j\circ B^{n-j}$$

for odd $j$, and

$$R^{n-j}\circ(BR)^jB^{n-j}$$

for even $j$. While $j\lt n$, one slide — a blue to the left for odd $j$, a red to the right for even $j$ — turns that position into a left-hand pattern with $j+1$ pairs, because $R(BR)^jB=(RB)^{j+1}$. Induction gives legal runs of lengths $1,2,\ldots,n$.

Then the alternating block shrinks. With $r$ pairs left the position is

$$B^{n-r}(BR)^r\circ R^{n-r}$$

for odd $r$, and

$$B^{n-r}\circ(BR)^rR^{n-r}$$

for even $r$; at $r=n$ these agree with the forms above. A slide — a red to the right for odd $r$, a blue to the left for even $r$ — followed by the matching run of $r-1$ hops lowers $r$ by one, and at $r=1$ a final slide produces $B^n\circ R^n$. The hop runs are therefore $1,2,\ldots,n,n-1,\ldots,1$, with one slide before each run and one at the very end, so the strategy uses $2n$ slides and

$$n+2\sum_{j=1}^{n-1}j=n^2$$

hops, so $M(n)\le n(n+2)$; for $n=4$ the runs are $1,2,3,4,3,2,1$.

3. Every solution needs at least $n^2$ hops

Count the pairs consisting of one red and one blue counter in which the red stands to the left of the blue, and call this the crossing number $I$; it is the inversion number of the sequence of colours when blue is ordered before red. ^[5] At the start all $n^2$ red-blue pairs are counted, so $I=n^2$, and at the end $I=0$. A slide leaves the left-to-right sequence of colours unchanged, so $I$ stays put. A hop exchanges the jumper with the one counter it jumps over, altering that sequence by a single exchange of neighbours: $I$ changes by exactly $1$ when those two counters have different colours, and not at all when they have the same colour. No move lowers $I$ by more than $1$, so every solution contains at least $n^2$ hops, each over a counter of the other colour. Along the $8$-move play above $I$ runs through $4,4,3,3,2,1,1,0,0$, falling exactly at the four hops.

4. Every solution needs at least $2n$ slides

Leave the empty square out and number the remaining $2n$ places $1,\ldots,2n$ from the left; let $p$ be the number of counters to the left of the empty square. A slide changes $p$ by $1$ and leaves the colour sequence alone; a hop changes $p$ by $2$ and exchanges the two neighbours it steps across, at positions $p-1,p$ or $p+1,p+2$ — one odd and one even position either way. So while $p$ stays even the only exchangeable pairs are $(1,2),(3,4),\ldots$, while it stays odd they are $(2,3),(4,5),\ldots$, and only a slide changes its parity. Between two slides every counter is thus locked in one fixed pair of positions and can change places only with its partner there.

Label the counters $R_1,\ldots,R_n$ and $B_1,\ldots,B_n$ within each colour from the left, keeping that order when two of one colour change places — legitimate, since they are indistinguishable and such a hop leaves the labelled sequence untouched. Then $R_1$ is always the leftmost red and $B_1$ the leftmost blue. To reach the left of $R_i$, the counter $B_1$ must already be left of $R_{i+1},\ldots,R_n$, so its first crossings with the reds come in the order $R_n,\ldots,R_1$, and those of $R_1$ with the blues in the order $B_1,\ldots,B_n$. The lists share the crossing of $R_1$ with $B_1$: together $2n-1$ crossings in a forced order, consecutive ones sharing a label but giving it a different partner. By the first paragraph a slide separates them, so $2n-2$ slides.

One more slide comes before all of them: in the starting sequence $R^nB^n$, where $p=n$, every pair of the applicable pairing is monochromatic, since a straddling pair would be $(n,n+1)$, which belongs to the pairing for even $p$ only when $n$ is odd and to the pairing for odd $p$ only when $n$ is even. Nothing can cross before the first slide, so the count rises to $2n-1$. Finally the empty square begins and ends on the centre square, and a slide changes the parity of its position while a hop does not, so the number of slides is even — hence at least $2n$. For $n=2$: RRBB with $p=2$ is paired RR|BB, so the middle red and blue cannot cross before a slide.

5. The move count

Sections 3 and 4 count different moves, so every solution needs at least $n^2+2n$ of them, and Section 2 plays one with exactly that many:

$$M(n)=n(n+2)=(n+1)^2-1 .$$

The count is classical: the puzzle is the toads-and-frogs swap, it goes back at least to 1867, and Lucas published the move count for every $n$ in 1883. ^[2] It gives $M(1)=3$, $M(2)=8$ and $M(3)=15$, the statement's checkpoint.

6. When is $n(n+2)$ triangular?

The $k$-th triangular number is $T_k=k(k+1)/2$. ^[3] We need the integers $n\ge1$ for which

$$n(n+2)=\frac{k(k+1)}{2}$$

has an integer solution $k\ge0$. Multiply by $8$ and complete both squares:

$$8n^2+16n+8=4k^2+4k+1+7,$$

$$8(n+1)^2=(2k+1)^2+7 .$$

So with $x=2k+1$ and $y=n+1$ the condition is exactly

$$x^2-8y^2=-7 .$$

The correspondence is reversible for $x\ge1$ and $y\ge2$: the equation forces $x^2=8y^2-7$ to be odd, so $x$ is odd, $k=(x-1)/2$ is a non-negative integer, $n=y-1\ge1$, and substituting back returns $n(n+2)=k(k+1)/2$. The solution $(1,1)$ belongs to $n=0$ and is kept only as a seed. Small cases: $(5,2)$ gives $n=1$ with $M(1)=3=T_2$, and $(11,4)$ gives $n=3$ with $M(3)=15=T_5$.

7. The Pell machinery

An equation $x^2-Dy^2=N$ with $D$ a positive non-square integer and $N$ fixed is a generalised Pell equation, to be solved in integers; its solutions arise from finitely many seeds multiplied by solutions of $x^2-Dy^2=1$. ^[4] Here $D=8$, and the smallest solution of $x^2-8y^2=1$ with $x,y\ge1$ is $(3,1)$: for $y\ge1$ we have $x^2=8y^2+1\ge9$, and $(3,1)$ attains that bound. Multiplying $x+y\sqrt8$ by $3+\sqrt8$ gives $(3x+8y)+(x+3y)\sqrt8$, and

$$(3x+8y)^2-8(x+3y)^2=x^2-8y^2,$$

because the cross terms $48xy$ cancel. So

$$(x,y)\longmapsto(3x+8y,\;x+3y)$$

turns one solution of $x^2-8y^2=-7$ into a larger one. It is the only engine we need.

8. Every solution, and only two chains

Run the engine backwards: $(x,y)\mapsto(3x-8y,\,3y-x)$, which is multiplication by $3-\sqrt8$ and preserves the equation for the same reason. Let $x,y\ge1$ satisfy $x^2-8y^2=-7$ with $y\ge3$. Then

$9x^2=72y^2-63\gt64y^2$ because $8y^2\gt63$, so $3x\gt8y$ and the new $x$ is positive;
$x^2=8y^2-7\lt9y^2$, so $x\lt3y$ and the new $y$ is positive;
$x^2\gt4y^2$ for $y\ge2$, so $x\gt2y$ and the new $y=3y-x\lt y$ is strictly smaller.

Descending therefore ends at a solution with $y\le2$, and there are only two: $y=1$ with $x=1$, and $y=2$ with $x=5$. Every solution in positive integers consequently lies in one of the two chains that start at $(1,1)$ and $(5,2)$:

$$(1,1),(11,4),(65,23),(379,134),(2209,781),\ldots$$

$$(5,2),(31,11),(181,64),(1055,373),\ldots$$

For $1\le y\lt20000$, testing whether $8y^2-7$ is a perfect square finds twelve pairs, all on these two chains: the nine above plus $(6149,2174)$, $(12875,4552)$, $(35839,12671)$. Both chains satisfy $y_{i+1}=6y_i-y_{i-1}$, since $3+\sqrt8$ is a root of $u^2=6u-1$; in terms of $n=y-1$ that reads $n_{i+1}=6n_i-n_{i-1}+4$.

9. The sequence of $n$

Subtracting $1$ from the $y$ values gives $n=0,3,22,133,780,\ldots$ and $n=1,10,63,372,2173,\ldots$. The value $n=0$ is dropped: the puzzle needs at least one counter of each colour, and the statement's list indeed starts at $1$. The rest interleave. Write $A_i$ and $B_i$ for the pairs reached after $i$ steps from $(1,1)$ and from $(5,2)$. Both coordinates of $(x,y)\mapsto(3x+8y,\,x+3y)$ have positive coefficients, so the map preserves strict coordinatewise inequalities; since $A_0=(1,1)$, $B_0=(5,2)$ and $A_1=(11,4)$ satisfy $A_0\lt B_0\lt A_1$, induction gives $A_i\lt B_i\lt A_{i+1}$ for every $i\ge0$. Once $A_0$ is discarded the merged order is $B_0,A_1,B_1,A_2,\ldots$, so forty terms are twenty from each chain. The sequence begins

$$1,3,10,22,63,133,372,780,2173,4551,\ldots$$

Its first five terms sum to $99$, exactly the statement's checkpoint, and the first ten sum to $8108$. Spot checks: $M(10)=120=T_{15}$ and $M(63)=4095=T_{90}$. The recurrence $y_{i+1}=6y_i-y_{i-1}$ has roots $3\pm\sqrt8$, the smaller one between $0$ and $1$, so successive $y$ values approach the ratio $3+\sqrt8\approx5.83$; forty terms need forty steps.

How the Code Works

The C++ program ^[6] is a direct transcription of Sections 7 to 9. Options holds the number of terms, $40$ by default, and a flag for the self-checks; parse_arguments reads --skip-checkpoints and hands the digits after --terms= to parse_int_after_prefix, which accumulates them in an int without a range check, so an out-of-range argument overflows instead of being refused. PellState stores one pair $(x,y)$ as two 128-bit integers.

sum_first_terms seeds the two chains of Section 8 at {5, 2} and {11, 4}, that is at $n=1$ and $n=3$; the solution $(1,1)$ is skipped there, which is precisely how $n=0$ is excluded. The lambda next_state applies $(x,y)\mapsto(3x+8y,\,x+3y)$. The loop merges the chains: it forms na and nb as $y-1$ for the two current states, adds the smaller to the running sum and advances only that chain; by Section 9 the candidates are never equal, so the values of $n$ come out in increasing order without duplicates. run_checkpoints verifies the five-term sum $99$ and the one-term sum $1$ before the real computation, and main prints the result.

The Python solve(terms=40) keeps the four integers a_x, a_y, b_x, b_y, uses the same merge and returns the sum as a string, with unlimited precision; the Java solve fixes the count at $40$ and stores each state in a PellState whose fields are long. Only the C++ has command-line options and checkpoints, Python takes another count as a function argument, and Java's main ignores its arguments. For forty terms every port is safe: counting the advance that follows the last selected term, the largest stored values are $x\approx2.3\cdot10^{16}$ and $y\approx8.1\cdot10^{15}$, and no term exceeds $1.4\cdot10^{15}$, so forty of them sum to below $5.6\cdot10^{16}$, far inside the signed 64-bit range of about $9.2\cdot10^{18}$. Beyond the default neither port checks for overflow: Java's state arithmetic overflows at the $47$-th update if its count is raised, and in C++ both candidates are cast to a 64-bit unsigned integer before being compared, so at iteration $50$ the larger one wraps and is chosen as the smaller, making --terms=50 return a wrong sum silently. Python has neither problem.

Complexity and Verification

Each iteration forms the two candidates $y-1$, compares them, adds the smaller to the sum and advances one chain; next_state costs three multiplications by small constants and two additions. For $K$ terms that is $O(K)$ time and $O(1)$ memory in fixed-width arithmetic, and forty terms are a few hundred operations, less work than starting the process. In Python the integers grow by a constant number of bits per step, so there the loop costs $\Theta(K^2)$ bit operations. The difficulty of the problem sits in the formula $M(n)=n(n+2)$, not here.

The checks below were made for this article and are not built into the published programs. A breadth-first search over arrangements, whose first visit to the target gives $M(n)$, reaches $6$, $30$, $140$, $630$, $2772$, $12012$, $51480$ and $218790$ arrangements for $n=1,\ldots,8$ — every time all $(2n+1)!/(n!\,n!)$ of them — with distances $3,8,15,24,35,48,63,80$, matching $n(n+2)$ and the statement's $M(3)=15$. For $n\le6$, distances from both ends mark every move on a shortest solution, and each is a forward slide or a hop over the other colour, so every shortest solution has $n^2$ hops and $2n$ slides; a search over the pairs (arrangement, slides used so far) adds that no solution of any length manages with fewer than $2n$ slides. The exchange rule of Section 4 was tested on every reachable arrangement for $n\le5$, and the construction of Section 2 was replayed move by move for $n\le20$ with its position patterns and totals.

On the arithmetic side, testing whether $8n(n+2)+1$ is a perfect square for every $n\le300000$ returns exactly the fourteen values $1$, $3$, $10$, $22$, $63$, $133$, $372$, $780$, $2173$, $4551$, $12670$, $26530$, $73851$, $154633$ of the merged chains, so the Pell route loses nothing. All three implementations share the seeds, the recurrence and the merge; C++ with --terms=5, --terms=1 and --terms=10 prints $99$, $1$ and $8108$, and Python's solve(5), solve(1) and solve(10) return the same three values, each reproducible by hand from the terms above.

Footnotes and References

The references below supply the background facts used above. The construction of Section 2, the two lower bounds of Sections 3 and 4, the descent that produces exactly two chains and the operation counts are derived explicitly in this article.

Project Euler 321 — Swapping Counters. The official statement describes the row of 2n + 1 squares with n red and n blue counters and one empty square, allows a slide or a hop over one counter, defines M(n) as the minimum number of moves that reverses the two colours, records that M(3) = 15 is a triangle number, gives 1, 3, 10, 22, 63 with sum 99 as the first five values of n with M(n) triangular, and asks for the sum of the first forty.
OEIS A005563 — a(n) = n(n+2) = (n+1)² − 1. A comment by R. K. Guy (1 February 2008) gives these as the numbers of moves it takes n frogs to swap places with n toads on a strip of 2n + 1 squares when a move is a single slide or jump, notes that the puzzle goes back at least to 1867, and records that Édouard Lucas probably first published the move count for each n in 1883.
Wikipedia — Triangular number. The article gives the k-th triangular number as k(k + 1)/2 and states that an integer x is triangular if and only if 8x + 1 is a perfect square, the test used in Section 6 and in the brute-force check.
Wikipedia — Pell's equation. The article lists the fundamental solution of x² − 8y² = 1 as (3, 1), explains that all others follow algebraically from its powers, and states for the generalised equation x² − ny² = N that finitely many solutions generate the rest by multiplication with solutions of u² − nv² = 1.
Wikipedia — Inversion (discrete mathematics). An inversion of a sequence is a pair of entries that are out of order, and their number is a common measure of sortedness; the crossing number of Section 3 is the inversion count of the colour sequence with blue ordered before red.
C++ — Euler321.cpp. The linked immutable C++ revision contains PellState, sum_first_terms with the seeds {5, 2} and {11, 4}, the lambda next_state and the checkpoints. It is the implementation record for this article.

Problem 321 source code

C++

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

namespace {

using u64 = std::uint64_t;
using i128 = __int128_t;

struct Options {
    int terms = 40;
    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, "--terms=", options.terms)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.terms >= 1;
}

struct PellState {
    i128 x;
    i128 y;
};

u64 sum_first_terms(const int count) {
    PellState a{5, 2};    // Gives n=1
    PellState b{11, 4};   // Gives n=3

    auto next_state = [](PellState s) {
        // Multiply x + y*sqrt(8) by 3 + sqrt(8).
        const i128 nx = 3 * s.x + 8 * s.y;
        const i128 ny = s.x + 3 * s.y;
        return PellState{nx, ny};
    };

    u64 sum = 0ULL;
    int taken = 0;
    while (taken < count) {
        const u64 na = static_cast<u64>(a.y - 1);
        const u64 nb = static_cast<u64>(b.y - 1);
        if (na < nb) {
            sum += na;
            a = next_state(a);
        } else {
            sum += nb;
            b = next_state(b);
        }
        ++taken;
    }
    return sum;
}

bool run_checkpoints() {
    if (sum_first_terms(5) != 99ULL) {
        std::cerr << "Checkpoint failed for first five-term sample sum" << '\n';
        return false;
    }
    if (sum_first_terms(1) != 1ULL) {
        std::cerr << "Checkpoint failed for first term" << '\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 << sum_first_terms(options.terms) << '\n';
    return 0;
}

Python

def solve(terms=40):
    a_x, a_y = 5, 2
    b_x, b_y = 11, 4
    
    total = 0
    taken = 0
    while taken < terms:
        na = a_y - 1
        nb = b_y - 1
        if na < nb:
            total += na
            nx = 3 * a_x + 8 * a_y
            ny = a_x + 3 * a_y
            a_x, a_y = nx, ny
        else:
            total += nb
            nx = 3 * b_x + 8 * b_y
            ny = b_x + 3 * b_y
            b_x, b_y = nx, ny
        taken += 1
        
    return str(total)

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

Java

public class Euler321 {
    static class PellState {
        long x, y;

        PellState(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    public static String solve() {
        int terms = 40;
        PellState a = new PellState(5, 2);
        PellState b = new PellState(11, 4);

        long sum = 0;
        int taken = 0;
        while (taken < terms) {
            long na = a.y - 1;
            long nb = b.y - 1;
            if (na < nb) {
                sum += na;
                long nx = 3 * a.x + 8 * a.y;
                long ny = a.x + 3 * a.y;
                a.x = nx;
                a.y = ny;
            } else {
                sum += nb;
                long nx = 3 * b.x + 8 * b.y;
                long ny = b.x + 3 * b.y;
                b.x = nx;
                b.y = ny;
            }
            taken++;
        }
        return String.valueOf(sum);
    }

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