[组合] 汉诺塔问题推广

450660879

原始汉诺塔问题是： 三根柱子 A,B,C，$n$个盘子由小到大（编号为1，2，...，$n$，大盘编号大）排在A柱上（大盘在下小盘在上），目标是将其移动到 C 柱上，每次只能移动一只盘子，且每一个中间状态都要满足大盘在下小盘在上，则完全移动到 C 柱上至少要$2^n-1$步。

现在稍微改变一下规则：初始盘子都在 A 柱上（大盘在下小盘在上），每次只能移动一只盘子，过程中要求编号为$i$的盘子上方至多有$i$个盘子（不要求大小顺序），最终移动到 C 柱，最终状态也只有满足编号为$i$的盘子上方至多有$i$个盘子（不要求大小顺序），问：完全移动到 C 柱上至少要多少步？

realnumber

回顾下汉诺塔问题：记所需最少步数为f(n).
n=1时,f(1)=1
假设$f(k)=2^k-1$
那么n=k+1时,把1~k移动到B盘所需最少步数为f(k),再把编号为k+1移动到C盘,再把B盘的1~k移动到C盘，这样$f(k+1)=2f(k)+1=2^{k+1}-1$.

推广问题中，对照以上解法，“再把B盘的1~k移动到C盘”无法实现，因为没有按顺序放好，不符合假设需要的条件.
即使推广中加条件“最后需要按顺序放置”，原解法也不一定能够照搬，因为最少步骤会不会出现1~k在B 盘这样一个中间状态.

这样要不先积累几个简单情景，记g(n)为推广问题的步数.
那么g(1)=1,g(2)=2,g(3)=g(1)+g(2)+g(1)=4,g(4)=g(2)+g(2)+g(2)=6,
g(5)=g(1)+g(2)+g(1)+g(2)+g(3)=10?试了3种都是10.
n=2k为偶数时，似乎可以把(1,2),(3,4),...,(n-1,n)看做k个整体，搬动k个整体（搬动一次，实际需要2步）就是汉诺塔问题,猜测答案是$2(2^k-1)$，证明不会，特别是最少步数什么的.
n=2k+1时,奇数情况似乎有些复杂

450660879

回复 2# realnumber


    试了g(5)=9， 1 A→C，2 A→B，1 C→B，3 A→B，4 A→C，5 A→C，3 B→C，1 B→C，2 B→C，最终2 1 3 5 4，根据新的规则，最下面两个只能是n-1,或n，并且猜测n-1在最下面时步数最少，没证出来。

450660879

回复 5# realnumber


    g(6)=14,g(7)=19,g(8)=30,g(9)=39,g(10)=62,g(11)=79

realnumber

n 偶数看来猜对了是$g(n)=2(2^{0.5n}-1)$,方法见2楼，为什么最小可以也许可以用数学归纳法配合说明.
n=3，5，7,9,11为奇数，从你列出来的看依次为5-1，10-1,20-1,40-1,80-1也很有规律啊,原因不晓得.
...你是怎么得出n>6的值的.

450660879

对偶数的情况我当时也是猜的这个结果，但是怎么证明：把(1,2),(3,4),...,(n-1,n)看做k个整体得到的结果是最少步骤呢？

450660879

回复 8# realnumber


对偶数的情况我当时也是猜的这个结果，但是怎么证明：把(1,2),(3,4),...,(n-1,n)看做k个整体得到的结果是最少步骤呢？

450660879

回复 8# realnumber


    n>6的情况我是一个个试出来的，给出了具体的移动盘子的方法，但也没能说明是最少步骤

450660879

回复 12# realnumber


    因为n-1一定在最下面，所以C柱必须清空，即前n-2个盘子必须到B柱上，这至少要g(n-2)步，然后n-1移到C柱，n移到C柱，最后将B柱上的n-2个盘子移动到C上，我猜测最后这一步也是至少要g(n-2)步，但没能证明。

realnumber

定义：从上到下放置成这样的盘子称为M序列，（1,2），（3,4），...，（n-1,n），同一个小括号的次序可以任意，不同小括号内的两个盘子的不能交换，又n是偶数.n为奇数时，没有定义.
A柱的n个盘子编号后，放置成M序列，按1楼要求借助ABC，都移动到C柱的，当步骤最少时，用数学归纳法证明以下猜想
1.最后结束时C盘上的也是M序列.
2.所需步数记为$g(n)=2(2^{0.5n}-1)$.

证明：(1).n=2时，M序列就两种1,2或2,1显然就2步完成,两步是最少的，因为2个盘子至少搬2下，且完成后C盘上也成M序列.
(2).假设n=2k时，猜想成立.
则当n=2k+2时，要移动编号为n-1,n到C盘，必须把1~n-2都移动到B盘，由归纳假设所需最少步数为g(n-2),且B盘上的1~n-2的盘子也是M序列.接下来就要2步把n-1,n依次移动到C盘（2步当然是最少的.），再接下来把B盘上的n-2个盘子移动到C盘，这点仍旧由归纳假设可得.且此时这n个盘子也成M序列.
因此$g(n)=2g(n-2)+2=4(2^{0.5(n-2)}-1)+2=2(2^{0.5n}-1)$,
因此n=2k+2时，猜想也成立
所以对任意正偶数n，猜想总成立.

450660879

回复 14# realnumber


    1.“不同小括号内的两个盘子的不能交换” 为什么要这样定义？
2.由任意一个M序列到另一个M序列用的最少步骤一定是不变的吗？

realnumber

回复 17# 450660879


    1.不考虑这样，比如n=4从上到下3124
2.最小步数似乎不变的，移动过程从证明过程看，看来也是唯一的.

realnumber

n为奇数情景这样尝试可不可以？n>=5
1~n-2移动到B（此时最上三个编号依次是2，1，3，最下2格是n-2,n-3，其它的似乎是递增编号，不过不需要了）,再n-1,n移动到C,再移动B上的盘子都到C盘（此时最上三个编号依次是2，1，3，最下2格是n,n-1）.
对比：1~n-1(偶数个，已经解决的)移动到B,再n移动到C,再B的都到C（也M序列移动）.




按上面步骤估计也可以用数学归纳法.

n为奇数($n\ge3$)时，某个柱上编号从上到下依次为2,1,3,4,...n,(就1,2换为2,1,其余按自然数递增排列)称为P序列,
按1楼规则，从A移动到C所需要最少步数记为g(n).
2,1,3,4,...,n-3,n-2,n,n-1称为Q序列(也即为"n-2个盘子的P序列再依次加n,n-1"),按1楼规则，从A移动到C所需要最少步数记为h(n)..

当n=3,5,7时，可以用穷举说明最小步骤依次为4,9,19
假设$n\le 2k+1$($k\ge 2$)时,A盘1~n移动到C盘,所需步数最少时，在C盘形成Q序列,步数为$h(n)=5\times 2^{n-3}-1$.
分解下$n\le 2k+1$的过程，也即为A盘1~n-2移动到B盘，所需步数最小时，在B盘形成Q序列（2,1,3,...,n-2,n-3）,再依次移动n-1,n到C盘，再把B柱上Q序列移动到C盘，此时1~n-2个盘子依次形成P序列$g(n-2)=5\times 2^{n-5}-2$，添上最下面的n,n-1整体是一个Q序列,所需步数就是$h(n)=h(n-2)+2+g(n-2)$.
n=2k+3时，需要说明会形成相应的P序列,Q序列，以及符合猜想的公式$h(n),g(n)$.
--有问题时再来考虑，先这样,话说自己也觉得不太靠谱，只是按n=3,5,7猜的，似乎也要与这种对比n,1,2,3,4,...,n-1.这样一来还有没遗漏别的呢？n=2k+3最少步数，看来每移动一次都要考虑各类可能.
ps.上面不重要帖子已经删去.