Project Euler Problem 336

Solution

Answer: CAGBIHEFJDK

Let the operation $R_k$ mean:

• keep the first $k$ carriages fixed,
• reverse the order of the suffix starting at position $k$.

For example:

$$R_1(DACB)=DBCA$$

because the suffix $ACB$ becomes $BCA$.

---

1. Mathematical analysis

Simon’s strategy

Simon fixes the train from left to right.

Suppose we are fixing carriage $A_i$ into position $i$.

There are two cases:

1. If $A_i$ is already at the end, one reversal is enough:

$$R_i$$ 2. Otherwise Simon first sends $A_i$ to the end, then to its final position:

$$R_j,\quad R_i$$

where $j$ is the current position of $A_i$.

Thus:

• each stage uses at most 2 reversals,
• except the final stage, which can use only 1.

So for $n$ carriages the maximum possible number of reversals is

$$2(n-2)+1=2n-3.$$

A permutation achieving this is called a maximix arrangement.

---

Recursive structure of maximix arrangements

Assume we have a maximix arrangement on letters

$$B,C,D,\dots$$

and call it $q$.

We now insert $A$.

For Simon to require the maximum number of moves:

• $A$ must be neither first nor last.

Write the permutation as

$$P,A,S$$

with both $P,S\neq\emptyset$.

Simon performs:

1. reverse suffix beginning at $A$:

$$P,A,S \to P,S^R,A$$ 2. reverse the whole train:

$$P,S^R,A \to A,S,P^R$$

After fixing $A$, the remaining suffix must itself be a maximix arrangement. Therefore:

$$q = S,P^R.$$

Hence every maximix arrangement is obtained from a smaller one by:

$$P,A,S$$

where $q=S,P^R$.

If $q$ has length $m=n-1$, choose a split point $k$ with

$$1 \le k \le m-1.$$

Then:

• $S=q[:k]$
• $P^R=q[k:]$
• $P=(q[k:])^R$

giving

$$p=(q[k:])^R + A + q[:k].$$

This recursively generates all maximix arrangements.

The count satisfies:

$$M_n=(n-2)M_{n-1}, \qquad M_2=1,$$

so

$$M_n=(n-2)!.$$

For $n=11$:

$$M_{11}=9!=362880,$$

small enough to generate directly.

---

2. Python implementation

def maximix(chars):
    n = len(chars)

    # Base case: for two letters, only the reversed order is maximix
    if n == 2:
        return [chars[1] + chars[0]]

    first = chars[0]
    result = []

    # Generate all maximix arrangements of the remaining letters
    for q in maximix(chars[1:]):

        m = n - 1

        # Split q into S + P^R
        for k in range(1, m):

            # Reconstruct P A S
            p = q[k:][::-1] + first + q[:k]

            result.append(p)

    return sorted(result)

arrangements = maximix("ABCDEFGHIJK")

answer = arrangements[2010]   # 2011th lexicographic (1-indexed)

print(answer)

---

3. Code walkthrough

Base case

if n == 2:
    return [chars[1] + chars[0]]

For two carriages, only the reversed order is maximix.

Example:

$$AB \to BA$$

---

Recursive generation

for q in maximix(chars[1:]):

Generate all maximix arrangements of the smaller alphabet.

For $n=6$, this generates arrangements on $BCDEF$.

---

Splitting $q=S+P^R$

for k in range(1, m):

Every nontrivial split is valid.

---

Reconstruction

p = q[k:][::-1] + first + q[:k]

This constructs:

$$P,A,S$$

from:

$$q=S,P^R.$$

---

4. Verification on the sample

For 6 carriages:

arrangements = maximix("ABCDEF")
print(arrangements[9])

produces:

$$\texttt{DFAECB}$$

which matches the problem statement exactly.

So the recursion is correct.

---

5. Final verification

• Total arrangements generated:

$$9! = 362880$$

which matches the theoretical count.

• The sample case matches exactly.
• Lexicographic indexing uses zero-based Python indexing, so the 2011th item is index 2010.

Therefore the required arrangement is:

Answer: CAGBIHEFJDK