Let $n \geq 2$ be a natural number. For any two permutations of $(1,2,\cdots,n)$, say $\alpha = (a_1,a_2,\cdots,a_n)$ and $\beta = (b_1,b_2,\cdots,b_n),$ if there exists a natural number $k \leq n$ such that $$b_i = \begin{cases} a_{k+1-i}, & \text{ }1 \leq i \leq k; \\ a_i, & \text{} k < i \leq n, \end{cases}$$we call $\alpha$ a friendly permutation of $\beta$. Prove that it is possible to enumerate all possible permutations of $(1,2,\cdots,n)$ as $P_1,P_2,\cdots,P_m$ such that for all $i = 1,2,\cdots,m$, $P_{i+1}$ is a friendly permutation of $P_i$ where $m = n!$ and $P_{m+1} = P_1$.
Problem
Source: China Mathematical Olympiad 2017 Q4
Tags: combinatorics, permutations
24.11.2016 10:13
I claim if a sequence of permutations starts with $P_1 = (1, 2, ..., n)$, then we can obtain $P_{n!}=(n, n-1, ..., 1)$ through a sequence $P_1, P_2, ..., P_n$ where $P_{i+1}$ is a friendly permutation of $P_i$ for all $i=1, 2, ..., n$, and all $P_i$ are distinct. We proceed by induction, Base Case: $n=2$ obviously works by taking $P_1=(1,2)$ and $P_2=(2,1)$. Inductive step: Assume that the statement is true for some $n$. So we start with $P_1=(1, 2, ..., n, n+1)$ and we take a sequence of friendly sequences all of the way up to $P_{n!}=(n, n-1, ..., 2, 1, n+1)$ which we can do by our inductive hypothesis. Now construct an algorithm as follows: If $c \cdot n! = j$ for some positive integer $k \leq n+1$, then reverse the sequence of $P_j$ and make that $P_{j+1}$. We can then 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. Note that each time we put $P_{c \cdot n!}$ into the algorithm, we take the string of numbers $(n+1-c, n-c, ..., 2, 1, n+1, n, ..., n+2-c)$, and produce $(n+2-c, n+3-c, ..., n, n+1, 1, 2, ..., n-c, n+1-c)$ which in turn will make $P_{(c+1) \cdot n!} = (n+1-(c+1), n-(c+1), ..., 2, 1, n+1, n, ..., n+2-(c+1))$. Since we take $n!$ distinct permutations with the last terms ranging from $n+2-(c+1)$ for all $c$ from $1$ to $n+1$, we produce $(n+1)!$ distinct permutations where $P_{(n+1)!} = (n+1, n, ..., 1)$ which completes the induction. Note that since we are able to produce $n!$ distinct permutations of $(1, 2, ..., n)$ such that $P_{i + 1}$ is a friendly permutation of $P_i$ for all $i=1, 2, ..., n$ (by our claim), we have proved the problem statement.
24.11.2016 23:05
Define the permutation $f_i$ as the one that flips the first $i$ terms. We will prove that there exists such an enumeration with $P_m=(n,n-1,\ldots,1)$ by induction. The base case is clearly true. Let $a_1,a_2,\ldots,a_{k!}$ be the sequence of permutations $f_i$ for $n=k$. For the inductive step of $n=k+1$, first apply $a_1,a_2,\ldots,a_{k!-1}$. This makes a net permutation of $(1,2,\ldots,k+1)\rightarrow(k,k-1,\ldots,1,k+1)$. Then, applying $a_{k!}=f_{k+1}$ gives $(k+1,1,2,\ldots,k)$. The first $k!$ permutations consist of all the ones that end in $k+1$. Repeating $a_1,a_2,\ldots,a_{k!}$ cycles through the end term and generates all $k!$ permutations with that end term. The net permutation is $(1,2,\ldots,k+1)\rightarrow(k+1,1,2,\ldots,k)$, so after $k+1$ applications of this gives us the original permutation while going through all $k!$ permutations with all $k+1$ end terms, or all $m$ permutations, as desired.
02.02.2017 02:09
I may be wrong but does this imply that any graph(simple)with $n!$vertices and degree of each vertex exactly $n-1$ always has a hamiltonian cycle?
07.02.2017 21:46
mathdebam wrote: I may be wrong but does this imply that any graph(simple)with $n!$vertices and degree of each vertex exactly $n-1$ always has a hamiltonian cycle? This is a very specific graph. The edges of each vertice are well-defined. For a counter-example to your conclusion just take $(n-1)!$ cliques of n vertices and you won't have a Hamiltonian cycle.
25.03.2018 18:21
Induct on $n$ claiming that we can start with $\textbf{Id}$ and end with $\textbf{-{Id}}$.Make a $(n+1)\times n!$ table, first row starting with $\textbf{Id}(n+1)$ and ending with $\textbf{-{Id}}(n+1)$,note that we can do this by induction hypothesis.Now in the beginning of the second row take the conjugate of the ending of the previous row and repeat the induction step for $n$. By a straightforward induction the $i$-th row starts with $(n+3-i)(n+3-(i-1))...(n+1)123...(n+2-i)$ and hence the last one ends with $(n+1)n...1$ and we're done. $-\sigma$ means rotation by $\pi$ as i can't make the \overline work outside of math mode.
21.03.2022 04:17
Induct on $n$ to prove we can always end at $(n,n-1,\cdots,1)$ after $n!$ steps. Step 1: Visit all permutations with $\pi(n)=n$ and end at $n-1,\cdots,1,n$. Now reverse the entire permutation. Step $k$: visit all permutations with $\pi(n)=n+1-k$ and end at $n-k, n-k-1, \cdots, 1, n, \cdots, n-k+1$.
19.06.2022 00:36
We provide an inductive construction on $n$. The case $n=2$ is trivial. Now, fix the last element $n+1$ and permute the first $n$ elements in the exact same fashion as the construction for $n$ terms; the last such permutation of such a category will have $n$ as its first element. Next, flip the entire permutation and repeat the construction. In the end, after iterating through all possible last elements, we will reach $(n+1, n, n-1, \cdots, 2, 1)$, from where we can conclude.