2017 CMO 第 5 题

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$ .

令 $n \geq 2$ 为自然数。对于 $(1,2,\cdots,n)$ 的任意两个排列，假设 $\alpha = (a_1,a_2,\cdots,a_n)$ 和 $\beta = (b_1,b_2,\cdots,b_n),$ 如果存在一个自然数 $k \leq n$ 使得 $$b_i = \begin{cases} a_{k+1-i}, & \text{ }1 \leq i \leq k; a_i, & \text{} k < i \leq n, \end{cases}$$ 我们称 $\alpha$ 为 $\beta$ 的友好排列。

证明可以将 $(1,2,\cdots,n)$ 的所有可能排列枚举为 $P_1,P_2,\cdots,P_m$ ，这样对于所有 $i = 1,2,\cdots,m$ ， $P_{i+1}$ 是 $P_i$ 的友好排列，其中 $m = n!$ 且 $P_{m+1} = P_1$ 。