【原】【数学趣闻】汉塔诺游戏，归纳推理

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。

  【游戏目标】：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。

  【操作规则】：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上

我们对题目进行一般化；假设A杠上自下而上、由大到小按顺序放置n个金盘，现将A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。设需要的最少步数为an

n=1时，

显然一步到位即a1=1

n=2时，

a2=3

当n=3时，

先将上面两个铜板移动到B杆需要3步，再将最后一块移动到C杆，此时将B杠上的铜板全部移动到C杆上同样需要三步

a3=7

经过以上分析我们不难归纳推理出an=2∧n－1

n个铜板我们可以先将n-1个铜板移到B杆上，至少需要an-1步

此时将最后一枚铜板移到C杆上，需要一步

最后将B杆上所有铜板全部移到C杆上同样需要an-1步

由此我们可以得到递推an=2an-1+1

an=2an-1+1

整理得到an+1=2（an-1+1）

即{an+1}为以2为首项，2为公比的等比数列

an=2∧n－1

春暖花开 万物复苏

不

好

春光