**2_n数最高层数与对应解数的证明 **
◆◆◆◆◆◆
一、文章名词解释
取斐波那契数列前n个不同元素的集合为Un={an|a1=1，a2=2，ak=ak-1+ak-2，2<k≤n}，取一个子集Pn，补集为Qn：
①设Pn元素总和为SPn的Qn元素总和为SQn，如SPn≤SQn，我称Pn为左子集，Qn为右子集。
②如果存在ak-2、ak-1属于Pn，ak不属于Pn，则我称这个Pn为可合成集。否则称为不可合成集，初始集。
Pn={…ai，…，ak-2，ak-1，…，aj…}可合成为Pn’={…ai，…，ak，…，aj…}
例：Pn={1，2，3，5}可合成为Pn’={1，2，8}
反过来
③如果存在ak属于Pn，ak-2、ak-1不属于Pn，则我称这个Pn为可分解集。否则称为不可分解集，终止集。
Pn={…ai，…，ak，…，aj…}可分解为Pn’={…ai，…，ak-2，ak-1，…，aj…}
例：Pn={1，2，8}可分解为Pn’={1，2，3，5}
Pn可经过若干次分解或合成变成Pn’，则Pn’也可经过若干次分解或合成变成Pn，我称Pn’为Pn的互换集（Pn也为Pn的互换集）。
容易知道，Pn的任一互换集的元素总和均为定值SPn。

二、与魔法塔游戏的联系
取一个适当的左子集Pn，使得Pn的互换集个数最多，其个数为魔法塔游戏中的最高层数，以Rn表示，其对应的SPn/SQn为魔法塔游戏中的最高层的解，当有多个不可互换的左子集Pn的互换集个数最多，其不可互换的左子集的个数为魔法塔游戏中的最高层的解的个数，以Xn表示。

三、证明
设3数，4数。。。n-1数的最高层数为R3，R4，……，Rn-1，其对应的左初始集为P3，P4，……，Pn-1，右初始集为Q3，Q4，……，Qn-1，且ai属于Pi。令n数的最高层数为Rn，对应的左初始集为Pn，对应的右初始集为Qn，为了方便讨论，以Tn表示Pn或Qn，以Rn(k)表示第k种情形下Rn的可能取值，Rn={max(Rn(1),Rn(2),...,Rn(n))，有：
(1)如果an-1、an属于Tn，因为an+an-1>an-a2=an-2+an-3+…+a1，所以Tn为右初始集Qn，且易知Rn(1)=Rn-1；
现在证明，Rn(1)<Rn(3)，即Rn-1<2Rn-3
由暴力求解的结果得出n=9~18时，均有Rn<Rn-1
现在假设存在一个k，使得
Rk-4=max（Rk-5，2Rk-7）=2Rk-7，且Rk-5<2Rk-7
Rk-3=max（Rk-4，2Rk-6）=2Rk-6，且Rk-4<2Rk-6
Rk-2=max（Rk-3，2Rk-5）=2Rk-5，且Rk-3<2Rk-5
Rk-1=max（Rk-2，2Rk-4）=2Rk-4，且Rk-2<2Rk-4
Rk=max（Rk-1，2Rk-3）=2Rk-3，且Rk-1<2Rk-3
成立
有Rk+1=max（Rk，2Rk-2）=max(2Rk-3，4Rk-5)=2max(Rk-3，2Rk-5)=2Rk-2，且Rk<2Rk-2，即k+1也成立，得证
所以Rn≠Rn(1)
(2)如果an-2、an属于Tn，an-1不属于Tn，因为an+an-2>2an-1-a2=an-1+an-3+…+a1，所以Tn为右初始集Qn。考虑Tn的补集，设Tn的补集的初始集为Wn，当Wn不包含an时，有Rn(2)=Rn-1，由(1)可知Rn≠Rn-1；当Wn包含an时，由于Tn为初始集，有an-3不属于Tn，有an-1、an-3属于Tn的补集，为了合成an，且为使Rn(2)最大，an-6、an-5、an-4必属于Tn的补集，此时Tn的补集={…am，an-6、an-5、an-4、an-3、an-1}可合成为{…am，an-4、an}，此时，Rn(2)=Rn(4)。所以Rn(2)=Rn(4)。说明：由于(2)中Tn为必为右初始集而(4)中必为左初始集，说明(2)与(4)是互补的情形。
(3)如果an-3、an属于Tn，an-2、an-1不属于Tn，当Tn的交换集包含an时，有Rn-3种；当Tn的交换集不包含an时，有Rn-3种，所以Rn(3)=2Rn-3
(4)如果an-4、an属于Tn，an-3、an-2、an-1不属于Tn，当Tn的交换集包含an时，最多有Rn-4种；当Tn的交换集不包含an时，an可分解为an-1和an-2，此时变成了n-2数的第(2)种情况，与n-2数的第(4)种情况互补，最多有Rn-2(2)种，必有Rn(4)=Rn-2(2)+Rn-4=Rn-2(4)+Rn-4=Rn-2+Rn-4；

(5)如果an-5、an属于Pn，an-4、an-3、an-2、an-1不属于Pn，利用(4)中降数的方法有：
Rn(5)≤Rn-2(3)+Rn-5=3Rn-5
现在假设Rn(5)取到最大值，即Rn(5)=3Rn-5
现在证明，Rn(5)<Rn(3)，3Rn-5<2Rn-3
由暴力求解的结果得出n=9~18时，均有Rn=max（3Rn-5，2Rn-3）=2Rn-3
现在假设存在一个k，使得
Rk-4=max（3Rk-9，2Rk-7）=2Rk-7，且3Rk-9<2Rk-7
Rk-3=max（3Rk-8，2Rk-6）=2Rk-6，且3Rk-8<2Rk-6
Rk-2=max（3Rk-7，2Rk-5）=2Rk-5，且3Rk-7<2Rk-5
Rk-1=max（3Rk-6，2Rk-4）=2Rk-4，且3Rk-6<2Rk-4
Rk=max（3Rk-5，2Rk-3）=2Rk-3，且3Rk-5<2Rk-3
成立
有Rk+1=max（3Rk-4，2Rk-2）=max(6Rk-7，4Rk-5)=2max(3Rk-7，2Rk-5)=2Rk-2，且3Rk-4<2Rk-2，即k+1也成立，得证
所以Rn≠Rn(5)
(6)如果an-6属于Pn，an-5、an-4、an-3、an-2、an-1不属于Pn，利用(4)中降数的方法有：Rn(6)≤Rn-2(4)+Rn-6；同(5)可证明Rn(6)<Rn(2)，有Rn≠Rn(6)
。
。
。
(k)如果an-k属于Pn，an-k-1、……、an-1不属于Pn，利用(4)中降数的方法有：Rn(k)≤Rn-2(k-2)+Rn-k；由于有Rn-2≠Rn-2(k-2)，Rn≤Rn-2(k-2)+Rn-k<Rn-2+Rn-k，有Rn≠Rn(k)

以上情形，只存在(1)(2)(3)(4)种情况，现在只讨论左初始集，由于(1)(2)两种情况为右初始集，舍去。
①现在证明，当n为偶数时，Rn(3)=Rn(4)
由暴力求解的结果得出n=12~18（7个数）且为偶数时，均有Rn=2Rn-3=Rn-2+Rn-4
现在假设存在一个k，使得
Rk-2=2Rk-5=Rk-4+Rk-6
Rk-1=2Rk-4=Rk-3+Rk-5
Rk=2Rk-3=Rk-2+Rk-4
成立
有2Rk-2=2Rk-4+2Rk-6=Rk-1+Rk-3，即Rk=2Rk-2=Rk-1+Rk-3
说明，当n为偶数是有Rn=Rn(3)=Rn(4)，有两种构造方法，所以Xn=2（n>12）
n为偶数的构造方法
1、(3)情形构造方法：在n-3数的左右子集加上an（或an-1和an-2）作为n数的左右子集
	解释：已知n-3数的最高层的解为SP/SQ
n数的最高层的解为SP+an/SQ+an（即SP+an/SQ+an-1+an-2）
2、(4)情形构造方法：在n-4数的4个不同的初始集中，和最大的初始集加上an作为左初始集。
解释：已知n-4数的最高层的解为SP1/SQ1与SP2/SQ2，SQ1与SQ2取一个较大的，由于对称性取SQ2
n数的最高层的解为SQ2+an/SP2+2an-1（即SQ2+an/SP2+an-1+an-2+an-3）

现在证明，当n为奇数时，Rn(3)<Rn(4)
由暴力求解的结果得出n=10~17（8个数）且为奇数时，均有Rn=max（2Rn-3，Rn-2+Rn-4）=Rn-2+Rn-4
现在假设存在一个k，使得
Rk-3=max（2Rk-6，Rk-5+Rk-7）=Rk-5+Rk-7，且2Rk-6<Rk-5+Rk-7
Rk-2=max（2Rk-5，Rk-4+Rk-6）=Rk-4+Rk-6，且2Rk-5<Rk-4+Rk-6
Rk-1=max（2Rk-4，Rk-3+Rk-5）=Rk-3+Rk-5，且2Rk-4<Rk-3+Rk-5
Rk=max（2Rk-3，Rk-2+Rk-4）=Rk-2+Rk-4，且2Rk-3<Rk-2+Rk-4
成立
有Rk+1=max（2Rk-2，Rk-1+Rk-3）=max（2Rk-4+2Rk-6，Rk-3+Rk-5+Rk-5+Rk-7），由于2Rk-4<Rk-3+Rk-5，2Rk-6<Rk-5+Rk-7，所以2Rk-4+2Rk-6<Rk-3+Rk-5+Rk-5+Rk-7，所以Rk+1=Rk-1+Rk-3，且2Rk-2<Rk-1+Rk-3
说明，当n为奇数是只有Rn=Rn(4)，只有1种构造方法，所以Xn=1（n>12）

n为奇数的构造方法
(4)情形构造方法：在n-4数的4个不同的初始集中，和最大的初始集加上an作为左初始集。
解释：已知n-4数的最高层的解为SP1/SQ1与SP2/SQ2，SQ1与SQ2取一个较大的，由于对称性取SQ2
n数的最高层的解为SQ2+an/SP2+2an-1（即SQ2+an/SP2+an-1+an-2+an-3）

所以Rn的递推公式为Rn=Rk-2+Rk-4，特别的n为偶数时，Rn=Rk-2+Rk-4=2Rk-3

由于在前面推导过程至少要已知Rn的前9项，所以从R3~R11我已暴力求出结果当n>11时，Rn=Rk-2+Rk-4（在3数与6数的解能为对称解时，经验证n>6均有Rn=Rk-2+Rk-4，这也是我建议包含对称解的原因）
在包含对称解的情况下，对于X6=1，X9=2，由于推导过程中，3~11数必须已知，所以X6=1，X9=2为已知；对于X12=3，12为偶数，有(3)(4)两种构造方法，由于X9=2，经(3)构造可得出2解，(4)构造可得出1解，所以Xn=3；对于X15=1，由于15为奇数，只能经(4)构造，取不到12数的对称解，此后将不再取到对称解，因此当n>12时，(3)(4)均只构造出1解，所以当n>12时，Xn={1（n为奇数），2（n为偶数）}
◆◆◆◆◆◆
作者：高明秋(广西)
发佈：万树军(香港)

ITPub博客

2_n数最高层数与对应解数的证明

最新文章