Problem 1434

1. **Base Case: $n = 2$**

For $n = 2$, we have the permutations $(1, 2)$ and $(2, 1)$. Clearly, $(2, 1)$ is a friendly permutation of $(1, 2)$ by reversing the first 2 elements. Thus, the base case holds.

2. Inductive Step:

Assume the statement is true for some $n$. That is, we can enumerate all permutations of $(1, 2, \ldots, n)$ as $P_1, P_2, \ldots, P_{n!}$ such that $P_{i+1}$ is a friendly permutation of $P_i$ for all $i = 1, 2, \ldots, n!$, and $P_{n!+1} = P_1$.

3. **Constructing the Sequence for $n+1$:**

Start with $P_1 = (1, 2, \ldots, n, n+1)$. By the inductive hypothesis, we can generate a sequence of friendly permutations up to $P_{n!} = (n, n-1, \ldots, 2, 1, n+1)$.

4. Algorithm for Generating Friendly Permutations:

- If $c \cdot n! = j$ for some positive integer $c \leq n+1$, reverse the sequence of $P_j$ to get $P_{j+1}$.
- Turn $P_{j+1}$ into $P_{j+n!}$ by reversing the first $n$ terms of $P_{j+1}$ and fixing the last term. All $P_i$ for $j+1 \leq i \leq j+n!$ are distinct by the inductive hypothesis.

5. **Generating $(n+1)!$ Permutations:**

Each time we apply the algorithm, we take the string of numbers $(n+1-c, n-c, \ldots, 2, 1, n+1, n, \ldots, n+2-c)$ and produce $(n+2-c, n+3-c, \ldots, n, n+1, 1, 2, \ldots, n-c, n+1-c)$. This process will generate $(n+1)!$ distinct permutations.

6. Completing the Induction:

By induction, we have shown that for any $n$, we can enumerate all permutations of $(1, 2, \ldots, n)$ such that $P_{i+1}$ is a friendly permutation of $P_i$ for all $i = 1, 2, \ldots, n!$, and $P_{n!+1} = P_1$.

$\blacksquare$