关于1到n的特殊排列存在性的证明问询

大家好，我最近碰到一个数论相关的问题，想向各位大佬求助：

证明：对于任意正整数$n$，我们总能找到$1,2,...,n$的一个排列，使得排列中任意两个数的平均值都不会出现在这两个数之间。

我自己尝试了小的数值例子，比如n=3、4的时候确实能找到符合要求的排列，但没法推广到所有正整数的情况，希望有人能帮忙梳理下证明思路，谢谢啦！

证明方案：数学归纳法构造 #

这个问题其实可以通过数学归纳法来构造出满足条件的排列，下面一步步拆解：

• 基础情况验证：

  • 当$n=1$时，排列就是[1]，显然没有两个数需要考虑，满足条件；
  • 当$n=2$时，[1,2]或[2,1]都符合要求——两个数的平均值是1.5，不是整数，自然不会出现在它们之间。

• 归纳假设：
  假设对于所有小于$n$的正整数$k$，都存在满足条件的排列$P_k$（即$1,2,...,k$的排列，任意两数的平均值不在两数之间）。

• 归纳步骤分情况构造：

  1. 当$n$是偶数时：设$n=2m$
     先根据归纳假设得到$1$到$m$的符合条件的排列$P_m$。接下来做两个变换：

     • 把$P_m$中每个数乘以2，得到由偶数$2,4,...,2m$组成的排列$Q_m$；
     • 把$P_m$中每个数乘以2再减1，得到由奇数$1,3,...,2m-1$组成的排列$R_m$；
       最后将$R_m$和$Q_m$拼接（顺序可以是$R_m + Q_m$或者$Q_m + R_m$），得到$1$到$2m$的排列。
       为什么这个排列符合要求？
     • 奇数和偶数的平均值是半整数，不是1到$2m$中的整数，所以不会出现在排列里；
     • 奇数之间的平均值如果是整数，必然是偶数，不在奇数子排列$R_m$中；
     • 偶数之间的平均值如果是整数，必然是偶数，而根据归纳假设，$Q_m$本身满足条件，所以这个平均值不会出现在两个偶数之间。

  2. 当$n$是奇数时：设$n=2m+1$
     先按照偶数的构造方法得到$1$到$2m$的符合条件的排列，然后把中间数$m+1$放在这个排列的最前端或者末尾。
     这样做的合理性：
     $m+1$和任意数$x$的平均值是$\frac{x+m+1}{2}$，如果这个值是整数，说明$x$和$m+1$同奇偶，但我们的排列里奇偶是分开的，所以这个平均值要么是半整数（不在排列中），要么是同奇偶的数——而根据之前的构造，这个数不会出现在$m+1$和$x$之间，因此整个排列依然满足条件。

举两个实际例子辅助理解：

• $n=3$（奇数）：先构造$1,2$的排列[1,2]，把3放在前面得到[3,1,2]。检查：3和1的平均值是2，不在两数之间；3和2的平均值是2.5，不在；1和2的平均值1.5，不在，完全符合要求。
• $n=4$（偶数）：由$1,2$的排列[1,2]得到奇数排列[1,3]、偶数排列[2,4]，拼接成[1,3,2,4]。逐一验证所有数对的平均值，都不会出现在对应数对之间。

通过这样的归纳构造，就能证明对于任意正整数$n$，都存在满足条件的排列啦！

备注：内容来源于stack exchange，提问作者train