一个数字排列问题

kexin_xiao

记得还是上小学的时候了，是《科学画报》上登的一道题，当时觉得特难，后来就一直没做出来，看看哪位高手会做。
有1-9各两个数字，要求排列成一个数列，要求，2个1之间有1个数，2个2之间有2个数......2个9之间有9个数。
例：1-4可以排列成 41312432

[ 本帖最后由 kexin_xiao 于 2008-11-22 16:14 编辑 ]

kexin_xiao

国际惯例，沙发自己的

打死也不说

先做沙发题慢慢想

yzl-34

这不是数列，这不是数列

gozichen

算了半天，5都算不出来，都试过了好象不行

kexin_xiao

刚发现一个网上介绍好象说9无解，转贴一下，大家一起研究

在一个偶然的机会下,接触到一种特别的数列,这种数列是由1~7等数字组成,其中每
个数字都重复使用两次,在总共14格的格子里排列,而且要符合1与1之间有1个数,2与2
之间有2个数字,,,6与6之间有6个数字,7与7之间有7个数字.
例:2 3 7 2 6 3 5 1 4 1 7 6 5 4
依据此种排列规则也找出1~3组成的数列312132,1~4组成得数列41312432,将此数列改成
由1~n所组成的2n位数列,并讨论此2n位数列的各种特性,并将有此特别规则的数列命为"
挑剔数列".
目的 :
证明n=4k+1和4k+2(k为非负整数)时不存在挑剔数列.
找出一种排法能排出2n位的挑剔数列.
证明此排法并反推n=4k和4k+3时一定有挑剔数列存在.
为了达到这些目的,我们使用以下方法:
以数列对应序数的关系及序数总合证明n=4k+1和4k+2时无挑剔数列.
藉由现有的挑剔数列,发现每一种2n的挑剔数列中阶有一组挑剔数列有相似的排法.
将每一组相似的数列用化简法化简之后可得一有规律性的数列,再探讨其转变后的数列
的排列.
目前研究内容:
试著找出同一n值挑剔数列之间的推倒关系.
找出每个n与组数的关系.
虽然目前已经找到哪些n值有挑剔数列存在,也找到排法能排出至少一组挑剔数列,但对於在
2n位中可以排出多少挑剔数列以及每个挑剔数列之间的关系都还在研究阶段,这个挑剔数列
还有很多地方可以继续发展下去.
1
壹,研究动机
这次的主题探讨,灵感主要是来自国小同学间的游戏,当时只觉得这是个可以打发时
间的问题,但现在再次想起,突然发现这个数列好像满特别的,可能会有一些特定的组
成规律,希望能深入探讨,了解整个思考的过程,并找寻其中特定的组成与规律.
贰,挑剔数列之定义
2 3 7 2 6 3 5 1 4 1 7 6 5 4
在十四个空格中填入十四个数字,这十四个数字是从1到7的整数且每个数都重复一
遍,也就是1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7等十四个数字,填入时必须遵守1跟1之间
有一个数,2跟2之间有两个数,3跟3之间有三个数…7跟7之间要有七个数,必须将
十四个数字填入且符合上叙条件.
延伸此数列到2n个空格,总共填入数字1~n各两次,其中1和1中间要隔一个数字,
2和2中间要隔两个数字,以此类推,n和n中间要隔n个数字,符合以上条件的数列我
们就称之为挑剔数列.
举例(n=3) 举例(n=4)
挑剔数列: 3 1 2 1 3 2 4 1 3 1 2 4 3 2
参,研究目的
一, 证明n=4k+1和4k+2(k为非负整数)时不存在挑剔数列.
二, 找出一种排法能排出2n位的挑剔数列.
三, 证明此排法并反推n=4k和4k+3时一定有挑剔数列存在.
肆,研究方法
一,证明n之值为多少时挑剔数列不存在.
(一)用电脑排挑剔数列.
使用C语言设计程式让电脑试排到n=20,
其中n=1, 2, 5, 6, 9, 10, 13, 14, 17, 18 时挑剔数列皆不存在.
(二)寻找使挑剔数列不存在之n的规律.
经过观察,n=4k+1 or 4k+2 时挑剔数列皆不存在.
2
(三)证明n=4k+1 or 4k+2 时挑剔数列不存在.
方法1.
※『序数』之定义:
此挑剔数列从左边开始数来,第一位之序数=1,第二位之序数=2,依序递增,至第
2n位时序数=2n
※挑剔数列中数字与序数之对应关系:
每个数字都要填两次,所以一个数字会对应到两个序数,设一数字为r,则数字r中
序数较小的序数表示为Ar,序数较大的r则因为两个r之间相距r格所以序数表示为
Ar+(r+1),如下图所示
数列,,,,,,,,,, r,,,,,,,,,,,r,,,,,,,,,
↓ ↓ ↓ ↓ ↓ ↓
序数1 2 3 ,,,,Ar,,,,,,,,,Ar+(r+1),,,,,,2n
证明:
一个需填入1~n各两次的挑剔数列,其序数和为1+2+3+4+…+2n=2n2+n —
且 当r=1时,两个1分别对应序数A1,A1+(1+1)
当r=2时,两个2分别对应序数A2,A2+(2+1)
当r=3时,两个3分别对应序数A3,A3+(3+1)
, ,
, ,
当r=n时,两个n分别对应序数An,An+(n+1)
数字1~n分别对应了所有的序数,所以序数和也可表示为
A1+A1+(1+1)+A2+A2+(2+1)+…+Ar+Ar+(r+1) —
=
4n2+2n=4 (A1+A2+…+Ar)+n2+3n => n(3n-1)=4 (A1+A2+…+An)
得n(3n-1)必为4的倍数,且n有四种情况n=4k n=4k+1 , n=4k+2 , n=4k+3
分别代入n(3n-1),当n=4k+1 or 4k+2 分别代入n(3n-1)后,n(3n-1)并不是4
的倍数,
故得证: 当n=4k+1 or 4k+2时,挑剔数列不存在. ▓
方法2.
设n=4k+1
一个使用数字1~4k+1(k为非负整数)各两次的挑剔数列是由2k个偶数和
2k+1个奇数各填两次所成,共8k+2格,将空格由左而右编号为1~8k+2,
则其中编号为奇数的有4k+1格,编号为偶数的有4k+1格,
任一偶数填入的位置为a(设编号为奇数),则此偶数的第二次填入为a(奇
数)+数字本身(偶数)+1,则为偶数,所以全部的偶数填入后会用掉2k个编
号为奇数和2k个编号为偶数的格子,此时偶数格和奇数格都剩2k+1个.
(间隔r位)
3
任一奇数填入的位置为b(设编号为奇数),则此奇数的第二次填入为b(奇
数)+数字本身(奇数)+1,则为奇数,表示全部的奇数填入时会用掉2p个编
号为奇数的格子或2q个编号为偶数个格子(p+q=2k+1),今奇数格和偶数格
都剩下2k+1(奇数)格,所以全部的奇数无法完全填入,得证n=4k+1无法排
出挑剔数列. ▓
设n=4k+2
一个使用数字1~4k+2(k为非负整数)各两次的挑剔数列是由2k+1个偶数和
2k+1个奇数各填两次所成,共8k+4格,将空格由左而右编号为1~8k+4,
则其中编号为奇数的有4k+2格,编号为偶数的有4k+2格,
因为全部的偶数填入后会用掉2k+1个编号为奇数和2k+1个编号为偶数的
格子,所以偶数格和奇数格都剩2k+1个.
全部的奇数填入时会用掉2p个编号为奇数的格子或2q个编号为偶数个格
子(p+q=2k+1),今奇数格和偶数格都剩下2k+1(奇数)格,所以全部的奇数
无法完全填入,得证n=4k+2无法排出挑剔数列.

[ 本帖最后由 kexin_xiao 于 2008-11-22 16:15 编辑 ]

kexin_xiao

二,找出一排法能排出2n位挑剔数列,并证明n=4k,4k+3至少能找到一组
挑剔数列.
(一)找出规律,如能证出k=任意值时皆能找到至少一组挑剔数列,则间接得知n=4k or
4k+3时挑剔数列必存在.
1.挑剔数列之化简
(1)先把挑剔数列中最大的数字n写下,再依造数字的大小顺序由第一个n的
右边开始空一格依序填入直到第2个n之左方.
例: 7_6_5_4_7 (n=7)
(2)把步骤一所填入的数字往其右方填入第二次,同时在第一个n之左方补上
此挑剔数列应有但尚未画上之空格.
例: _ _ 7_6_5_4_7 6 5 4 (n=7)
(3)把剩余数字的偶数由左到右递增填入偶数格中,这些偶数的第2次皆填入
原先填入之偶数的右方.
偶数格的定义为与第1个n之序数差为偶数的格子.
奇数格的定义为与第1个n之序数差为奇数的格子.
例: 2 _ 4 2 11_10 4 9_8_7_6 _ 11 10 9 8 7 6 (n=11)
(4)把剩余的数字与空格一起作化简,把剩余的奇数皆减一再除以二,空格与
空格间的距离也减一再除以二,使之变为一新的挑剔数列.
例:原n=11的挑剔数列化简为 _ X _ X _ _ _ _
X表示此格在原挑剔数列中已被填入过数字.
2.新挑剔数列之排法
※新挑剔数列之定义:
新挑剔数列之形式为 _ X _ _ _ 其中 X之数量为右方连续空格之
数量减2.
4
(1)num X =4a+1时的排法
先把偶数由右往左递增填入偶数格中,填入这些偶数的第2次时,最
大偶数的第2次往原来的右方填,其余的往左方填入.
例: _ X _ X _ X _ X _ X 2 4 _ 2 0 0 4
偶数格之定义改为与X之序数差为偶数.
奇数格之定义改为与X之序数差为奇数.
剩余的数字与空格一起作化简,剩余的奇数皆减一再除以二,空格与
空格间的距离也减一再除以二,使此挑剔数列再做变化.
例:原num(X)=5变为_ _ _ _ _ X _
再把偶数由左往右递增填入偶数格,这些偶数的第2次填入中最大的
偶数第2次往原来的左方填,其余的往右方填入
再化简一次,则此数列就会变回新挑剔数列,形成一循环过程,每次
循环后原num(X)=4a+1之a值减少2 (a≥0).
(2)num X =4a+2时的排法
把最大的偶数填在最右边的偶数格,其余的偶数由右往左递增填入偶
数格,这些偶数的第二次填入皆往原数之左填入,惟第2次往左填入
会碰到最大偶数的偶数往原数之右填入.
例: _ X _ X _ X _ X 4 X _ X 6 4 _ 2 0 0 2 6
把剩余的空格与数字用和前面一样的方法化简,则此数列就会变回新
挑剔数列,形成一循环过程,每次循环后 原 num (X ) = 4a+2 之a
值减少1 (a≥0).
(3)num X =4a+3与num X =4a+4时的排法
把偶数由右往左递增填入偶数格中,这些偶数的第2次填入往原数之
左方填入.
例: _ X _ X _ X _ X 6 X _ X 4 X _ 6 2 4 _ 2 0 0 _
把剩余数字与空格依前面所提之方法化简.
把偶数由左往右递增填入偶数格中,这些偶数的第二次填入皆填往原
数之右方,再执行一次化简的步骤,则此数列就会变回新挑剔数列,
每次循环后原4a+3 or 4a 之a值减少2 (a≥0).
(二)证明上述新挑剔数列之排列方式中{num(X)=4a,4a+1,4a+2,4a+3},a为任意非
负整数时此排列方式恒成立.
1.证明num X =4a+1,a为非负整数时,此排法皆成立.
(1)由於每个X之左方必有一个空格,所以设num[ _X]=4a+1
新挑剔数列中右方之连续空格数为num X +2,故num[ _ ]=4a+3
总空格为(4a+1)+4a+3=8a+4,故可填入数字0~4a+1.
(2)标定序数,最右方为1,至最左方为512a3)(4a21)(4a+=++×+.
(3)跟据排法,偶数皆先填入偶数格中.0 4a+1中偶数共有2a+1个,由於之
前已说数字第二次填入所对应之序数表示为Ar+(r+1),现在Ar位於偶数
格,而r又为偶数,故这些偶数的第二次填入会填入奇数格中,
5
形成[XXX_]的情况.
(4)把此数列由右至左每四个划为一组.
例:
最大偶数倒填使得前4格变为〔2 0 0 4a〕,0和4a都无法使〔XXX_〕的
情况出现,所以num[XXX_ ]=2a+1-2=2a-1 , 而num[XXXX]=1
故num[X_ ]={总格数-4num[XXX_]-4num[XXXX]-最左方一格
[ _ ]}÷2=2a+2.
(5)依之前所提方式化简:
XXX_ X_ XXXX 消失 X__ __
此时化简后新的数列与原挑剔数列左右颠倒 (连续空格在左方)
而num[ _X ]=2a-1 num[ _ ]=2a+2+1=2a+3
新的数列总空格=num[ _ ]+num[ _X ]=4a+2可填入的数字为0 2a.
(6)再重复一次偶数填偶数格之方法
则 num〔_ XXX〕=a+1-2=a-1 num〔XXXX〕=1
最右方之一格num〔_〕=1num〔_ X〕=(总格数 - 4(a-1) - 4 - 最右方一格
〔_〕)/2=a.
(7)再用之前的方法化简一次
则新的数列方向变为和原来的一样
且num〔_X〕=a-1 num [ _ ]=a+1
两者差为2,条件皆和原先的新挑剔数列相符,形成一循环过程.
(8)故得证a为任意非负整数时此排法皆成立. ▓
2.证明num X =4a+2,a为非负整数时,此排法皆成立.
(1)由於每个X之左方必有一个空格,所以设num[ _X]=4a+2
新挑剔数列中右方之连续空格数为X之数量+2,故num[ _ ]=4a+4
总空格数为(4a+2)+4a+4=8a+6,故可填入数字0~4a+2.
(2)标定挑剔数列的序数,最右方为1,至最左方为2×(4a+2)+(4a+4)=12a+8.
(3)跟据排法,偶数皆先填入偶数格中.0 4a+2中偶数共有2a+2个,数字第
二次填入所对应之序数表示为Ar+(r+1),现在Ar位於偶数格,而r又为偶
数,故这些偶数的第二次填入会填入奇数格中,形成[XXX_]的情况.
(4)把此数列由右至左每四个划为一组,惟起始时是5个一组,由於最大之偶数
4a+2是排在第一个偶数格上,使得偶数2a要倒填,故0和2a不会产生
〔XXX_〕的形式,而前5格之形式为〔XXXXX〕
所以num[XXX_ ]=2a+2-2=2a num〔XXXXX〕=1
最左方之空格num〔_〕=1
故num[X_ ]=(总格数-4×(2a)-5-1) ÷2=2a+1.
(5)依之前所提方式化简:
XXX_ X_ X__ __
此时化简后新的数列虽与原挑剔数列左右颠倒 (连续空格在左方)
6
但num[ _X ]=2a num[ _ ]=2a+1+1=2a+2
两者差为2,条件和原先的挑剔数列相符,可视为一循环过程.
(6)故得证a为任意非负整数时此排法皆成立. ▓
3.num X =4a+3,a为非负整数时,此排法皆成立.
(1)由於每个X之左方必有一个空格,所以设num[ _X]=4a+3
新挑剔数列中右方之连续空格数为num X +2,故num[ _ ]=4a+5
总空格数为(4a+3)+4a+5=8a+8,故可填入数字0~4a+3.
(2)标定序数,最右方为1,至最左方为2×(4a+3)+(4a+5)=12a+11.
(3)跟据排法,偶数皆先填入偶数格中.0 4a+3中偶数共有2a+2个,数字第
二次填入所对应之序数表示为Ar+(r+1),现在Ar位於偶数格,而r又为偶
数,故这些偶数的第二次填入会填入奇数格中,形成[XXX_]的情况.
(4)把此数列由右至左每四个划为一组
每个偶数的第2次填入皆会形成 〔XXX_〕
所以num[XXX_ ]=2a+2, 最左方之空格num〔_〕=1
故num[X_ ]=(总格数-4×(2a+2)-1) ÷2=2a+1.
(5)依之前所提方式化简:
XXX_ X_ X__ __
此时化简后新的数列与原挑剔数列左右颠倒 (连续空格在左方)
而num[ _X ]=2a+2 num[ _ ]=2a+1+1=2a+2
新的数列总空格数=num[ _ ]+num[ _X ]=4a+4
可填入的数字为0 2a+1.
(6)再重复一次偶数填偶数格之方法.
(7)一开始的〔0 0 2 _〕并不产生〔_XXX〕的情形
故 num〔_XXX〕=a+1-1=a, 最右边留有一空格num〔_〕=1
num〔_ X〕=(总格子数 - 4a -3 -1 ) ÷2=a+1.
(8)再用之前的方法化简一次.
(9)则新的数列左右方向变为和原来的一样
且num〔_X〕=a num [ _ ]=a+2
两者差为2,条件皆和原先的挑剔数列相符,形成一循环过程.
(10)故得证a为任意非负整数时此排法皆成立. ▓
4.num〔X〕=4a+4,a为任意非负整数时,此排法皆成立.
(1)由於每个X之左方必有一个空格,所以设num[ _X]=4a+4
新挑剔数列中右方之连续空格数为X之数量+2,故num[ _ ]=4a+6
总空格为(4a+4)+(4a+6)=8a+10,故可填入数字0~4a+4.
(2)标定序数,最右方为1,至最左方为(4a+4)×2+(4a+6)=12a+14.
(3)跟据排法,由小到大的偶数依序填入由右而左的偶数格.0 4a+4中偶数共
有2a+3个,之前已说过第二次填入数字时所对应之序数表示为Ar+(r+1),
现在Ar位於偶数格,而r又为偶数,故这些偶数的第二次填入会填入奇数
格中,形成[XXX_]的情况.
(4)把此数列由右至左每四个划为一组,惟一开始先三格一组

[ 本帖最后由 kexin_xiao 于 2008-11-22 16:16 编辑 ]

kexin_xiao

7
因为4a+4的最右边为偶数格,所以填入后的最右边是[XXX]
所以num[XXX_ ]=2a+3-1=2a+2,而num[XXX]=1
故num[X_ ]={总格数-4×num[XXX_ ]-3×num[XXX]-最右边的[_]}÷2
=2a+1.
(5)依之前所提方式化简
XXX_ X_ XXX 消失 X__ __
此时化简后新的数列与原挑剔数列左右颠倒 (连续空格在左方)
而num[ X_ ]=2a+2 num[ _ ]=2a+2
新的数列总空格=num[ _ ]+num[ _X ]=4a+4
可填入的数字为0 2a+1.
(6)再重复一次偶数填偶数格之方法
则 num〔_ XXX〕=a+1-1=a ,num〔XXX〕=1,最右方之一格num〔_〕=1
num〔_ X〕=(总格数 - 4(a) - 3 - 最右方一格〔_〕)/2=a+1.
(7)再用之前的方法化简一次
则新的数列方向变为和原来的一样,且num〔_X〕=a num [ _ ]=a+2
两者差为2,条件皆和原先的挑剔数列相符,形成一循环过程.
(8)故得证a为任意非负整数时此排法皆成立. ▓
伍,研究结果与讨论
一,我们所列的目的都达到了,第一我们已经证出n=4K+1和4K+2是绝对不存在挑剔数列
的.
二,为了要完成第二个目的,我们试著找出每个挑剔数列的共通性,也找到了以化减的
方法来分类,有效减少了繁杂的挑剔数列,藉由不断的化简,快速的找到至少一组挑
剔数列,当2n相当大时,也能藉由4,5次化简就能排出挑剔数列,这可说是目前最大
的突破.
三,证出当n=4K+3和4K+4是绝对存在挑剔数列的.原本挑替数列的n值是以四为一个循
环(4K+1,4K+2无挑剔数列;4K+3,4K+4有挑剔数列),经过化简后,新挑剔数列的
num(X)还是以四为循环(4a+1,4a+2,4a+3,4a+4),相当有规律.
四,当然,目前仍在继续找寻其它的规律,试图将挑剔数列分析到最清楚,可是目前还
再研究每一个2n位能排出多少组挑剔数列,不过从已经知道的组数(n=3有2解;n=4
有2解;n=7有52解;n=8有300 解)来看,我们推测n与挑剔数列组数之关系应该是成指数关系增加,希望能试著找出其奥妙.
8
陆,目前发展
一,试找出一推导方法使得一组解可以推出同一n值的所有解.
(一) 从前面所得的公式可以找出任意n的一组解,再找程式跑出来的n=7的所有解之
相似度.
(相似度的定义:两n值相同的数列,比较数字1~n,越多位置相同的相似度越高.)
n=7的所有解:
A: 73625324765141
B: 72462354736151
C: 71416354732652
D: 74151643752362
E: 27423564371516
F: 57416154372632
G: 57263254376141
H: 17126425374635
I: 26721514637543
J: 62742356437151
K: 51716254237643
L: 23726351417654
M: 35743625427161
N: 72632453764151
O: 72452634753161
: 71316435724625
Q: 73161345726425
R: 37463254276151
S: 57236253471614
T: 57141653472362
U: 17125623475364
V: 36713145627425
W: 52732653417164
X: 41716425327635
Y: 24723645317165
Z: 35723625417164
这26组是完全不重复的,所以总共有52组(数列左右颠倒也是一新的数列)
9
(二) 从这26组数列中比较之间位置相同的数字数量(相似度)制成下表:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
A2110021111113212100200001
B2411120040114412400001000
C1421301022202231211000200
D1120100000011312004201021
E0110211200000100221100020
F0131222002100110133111200
G2200121022011101322101010
H1010121001101031121310311
I1000200013210000000021111
J1420002011233200211012011
K1020022131200020121012311
L1120010122211011120112222
M1101001013011200202122223
N3421001103011221210001000
O2423111002002211201102011
1131010300210213010020310
Q2212001100010113101030110
R1420213102112220111110001
S0010232201220101012203101
T0014132101102010112302011
U2002111300011010012302013
V0000010121112002310001222
W0101011012222120003221134
X0020020310322003101002121
Y0002201111122011100112323
Z1001000111123010011132413
注:标黄底的为相似度较高者.
10
(三) 从表格中可以找出与每一个数列相似度最高的数列,从相似度的高低可以排
出一推导的顺序.
(四) 从这个推导顺序找出n=7的数列推导的过程.(参见附录)
(五) 从n=7的推导方法试著找出其它n值的推导方法.
二,找寻n与挑剔数列组数的关系
(一) 因为前提的数列找寻方式只能找出每个n当中的一组解,无法知道每个n确
实的组数.
(二) 设计程式,找出每个n值内符合挑剔数列定义的数列,并计算总数,
得到n=3有2解,n=4有2解,n=7有52解,n=8有300解…..等数据.
(三) 找寻n与挑剔数列组数之间的关系.


1～3，2个：
231213，312132

1～4，2个：
23421314，41312432

1～7，52个：
14156742352637，14167345236275，15146735423627，15163745326427
15167245236473，15173465324726，16135743625427，16172452634753
17125623475364，17126425374635，23627345161475，23726351417654
24723645317165，25623745361417，26325734615147，26327435614175
26721514637543，27423564371516，34573641512762，34673245261715
35723625417164，35743625427161，36713145627425，37463254276151
41617435263275，41716425327635，45671415362732，46171435623725
46171452632753，46357432652171，51716254237643，52462754316137
52472654131763，52642753461317，52732653417164，53647352462171
53672352461714，56171354632742，57141653472362，57236253471614
57263254376141，57416154372632，61517346532472，62742356437151
71316435724625，71416354732652，72452634753161，72462354736151
72632453764151，73161345726425，73625324765141，74151643752362

1～8，300个：（略）

[ 本帖最后由 kexin_xiao 于 2008-11-22 16:18 编辑 ]

longhan

这么牛的证明题也搞定了，厉害

金眼睛

<P>太强了，证明太长，看得晕啊，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/mad.gif" border=0 smilieid="11"> </P>
<P>&nbsp;</P>
<P>比较懒，把找结果的过程交给了计算机，随机寻找，5，6，9都没找到，4瞬间就找到了，7用了半小时，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border=0 smilieid="10"> </P>