为叙述方便,称一排数中任何两个数的均值都不会和这两个数之间的任何数相等的排列为“好排列”
先证明引理：将数1,2,…,2^m 排成一排,总存在“好排列”
m=1时,排列为1,2,显然成立
假设m=k时,引理成立,对应的排列为a(1),a(2),a(3),……,a(2^k) （a后面括号里的数为下标）
当m=k+1时,考虑排列2*a(1)-1,2*a(2)-1,2*a(3)-1,……,2*a(2^k)-1,2*a(1),2*a(2),2*a(3),……,2*a(2^k),称之为“待证排序”（可以参考下答案最后的例子）
这个排列的后半段是n=k时的好排列每个数乘2,都是偶数；前半段是n=k时的好排列每个数乘2减1,都是奇数；显然他们俩段都分别是“好排列”
从排列中任意取相异两数p,q
若p,q同奇偶,则他俩同属于“待证排序”的前半段或后半段,因为前半段或后半段均为“好排列”,所以p,q的均值不在p,q之间
若p,q异奇偶,则p,q的均值也不在p,q之间
故,“待证排列”为“好排列”
m=k+1时引理成立
由数学归纳法任意m,引理均成立
对于1,2,……,n,总存在m使得2^m≥n,将数1,2,…,2^m 排成一排,取一种好排列,去掉比n大的数,剩下的仍为好排列,原命题得证
举个例子吧：
1,2是好排列
故1,3,2,4是好排列
故1,5,3,7,2,6,4,8是好排列
故1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16是好排列
……