第22题“世界末日”何时到来
在贝那勒斯(佛教圣地，位于印度北部)的圣庙里，安放着一个黄铜板，板上插着三根宝石针(如图22—1)。

梵天(印度教主神)在创造世界的时候，在其中的一根针上从下到上放置了由大到小的64片金片，这就是所谓的梵塔。

不论白天黑夜，都有一名值班的僧侣按照梵天不渝的法则把这些金片在三根针上移来移去；一次只能移一片，并且要求不论在哪一根针上，小片永远在大片的上面。

当所有的六十四片都从梵天创造世界时所放的那根针上移到另外一根针上时，“世界末日”即到来。

假设每次移动需要1秒的时间，问“世界末日”何时到来？
分析：要知道这个宗教传说中的“世界末日”何时到来，只需考虑两个问题。

首先是能否按照梵天的法则把这64片移到另一根针上；其次是如果能够完成上面的转移要求，共需对金片进行多少次移动。

为了搞清上面的问题，我们首先考虑金片数n较小时的情况。

当只有一个金片时，显然只需一次移动即可完成转移要求；当n=2时，如图22—2所示，共需3次移动即可完成转移。

当n=3时，完成转移的过程如图22—3所示。

即共需7次移动完成3个金属片的转移。

通过上面的试验不仅说明当金片个数为1，2，3时能够分别通过符合要求的1、3、7次移动完成转移，还可以从对转移过程的观察中得到下面的结论：n＝3时，前3次移动相当于最大的金片不动而将上面的两个金片从A针移到C针中，这等价于n＝2时的情况；第四次移动是将最大的金片从A针移到B针；最后的三次又是重复n＝2时的过程，即保持B针上的最大金片不动，将C针上的二片移到B针上。

同样地，我们可以用类似方法找到一种完成4个金片移动的方案：前7次保持A针上的最大金片不动，用n=3时的方法将最上面的三个金片移到B针上；第8次移动是将A针上的最大金片移到C针上；最后需要将B针上的三个金片移到C针上，这与n=3时的移动方法相同，共需7次。

所以要完成4片金片的转移共需15次移动。

由以上的结果可以知道，可以通过有限次的移动完成有限个金片的转移，且猜测转移n个金片需做2n-1次移动。

解：为了得到金片个数n=64时的移动次数，首先考虑金片个数较小时的情况，并设金片数为n时的移动次数为h n。

经试验发现，当金片个数为1，2，3，4时，完成转移要求分别需要1，3，7，15次移动，即h1=1，h2=3，h3=7，h4 =15，并猜测hn=2n-1。

一般地，要转移k块金片，只需通过hk-1次移动首先将最上面的k-1片(最大的一片不动)移到另外的一根针上，不妨设转移到B针上，然后将最大的一片移到C针上，最后仍然是保持C针上的最大金片不动，将B 针上的k-1片按要求移到C针上，共需移动h k-1次。

因此完成K片金片转移需要移动2hk-1＋1次。

下面证明猜测的正确性：显然n=1，2，3，4时，猜测正确，设n=k-1时需2k-1-1次移动，则
h k＝2h k-1＋1=2(2k-1-1)＋1=2k-1
所以可知h n=2n-1。

h64=264-1=18446744073709511615
因为1年中共365×24×60×60＝31536000秒，所以完成64片金片
太阳、行星(包括地球)是在大约30亿年前由不定形物质形成的。

恒星，特别是给太阳提供能量的“原子燃料”还能维持100—150亿年。

因此，整个太阳系的寿命无疑要短于200亿年，更远远短于5849亿年)。

回顾：前面我们得到hk=2hk-1＋1，由此递推关系式可知，该数列既非等差也非等比数列。

由hk=2hk-1＋1可得：
(h k＋1)＝2(h k-1＋1)
所以｛h k+1｝为等比数列，即h k+1=(h1+1)·2k-1=2k所以h k=2k-1即h n=2n-1。

一般地，递推关系式为a n=a n-1·q＋d(q≠1，d≠0)的数列｛a n｝叫做等比差数列，其通项可以按如下方法得到。

可得：数列｛a n｝的通项为
注：在解决问题时，有时可以采用把总目标分解为若干子目标的策略，把总目标分解为一系列子目标，并一个个地去解决子目标，从而减
轻问题解决者的工作负荷。

本题可以采用此策略。

以n=3时的情况(见图22—3)为例。

它的总目标是把3个金片从A针移到B针。

这个总目标可以分成若干子目标。

第一个子目标，是首先要把最大的金片(即金片3)
移到B针，而要实现这个子目标，只要将金片1从A针移到B针，金片2从A针移到C针，再将金片1从B针移到C针，接着，就能把金片3从A 针移到B针(如图22—3中前4次移动所示)。

在实现了把金片3移到B针这个子目标后，问题解决者就着手完成第二个子目标，即把金片2移到B针。

实现这个子目标比较容易，只需2次移动就可以了，即先将金片1从C针移到A针，再将金片2从C针移到B针。

最后一个子目标，只要将金片1从A针移到B针，1次移动就完成了。

总共需要移动7次。

在一般情况下，如果总目标是把n个金片从A针移到C针，则第一个子目标是把金片n移到C针，第二个子目标把金片n-1移到C针，……，共分成n个子目标来进行。

练习22
1．一般地，用两个砝码最多可以在天平上称出四种重量的重物，比如用1克和3克的砝码各1个可以称出质量分别为1，2，3，4克的重物，其中称2克重物的方法是在天平的一侧放重物和1克的砝码，另一侧放3克的砝码。

问为了称出1至1093克所有整数克的重物，除了1克和3克的砝码外，至少还需多少个砝码，它们的重量分别为多少？
2．已知数列｛a n｝由下列方式给出：任意写出两个自然数作为a1，a2，而后面的每一项均为前两项的和，即当n≥3时an=a n-1+a n-2。

问(1)若该数列中出现某一项恰好为5的倍数，以后是否还会有5的倍数出现？
(2)对于任意给出的a1、a2，是否该数列一定会有5的倍数出现？。