第22题 “世界末日”何时到来

《第22题 “世界末日”何时到来》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第22题“世界末日”何时到来　　在贝那勒斯(佛教圣地，位于印度北部)的圣庙里，安放着一个黄铜板，板上插着三根宝石针(如图22—1)。梵天(印度教主神)在创造世界的时候，在其中的一根针上从下到上放置了由大到小的64片金片，这就是所谓的梵塔。不论白天黑夜，都有一名值班的僧侣按照梵天不渝的法则把这些金片在三根针上移来移去；一次只能移一片，并且要求不论在哪一根针上，小片永远在大片的上面。当所有的六十四片都从梵天创造世界时所放的那根针上移到另外一根针上时，“世界末日”即到来。假设每次移动需要1秒的时间，问“世界末日”何时到来？　　分析：要知道这个宗教传说中的“世界末日”何时

2、到来，只需考虑两个问题。首先是能否按照梵天的法则把这64片移到另一根针上；其次是如果能够完成上面的转移要求，共需对金片进行多少次移动。为了搞清上面的问题，我们首先考虑金片数n较小时的情况。　　当只有一个金片时，显然只需一次移动即可完成转移要求；当n=2时，如图22—2所示，共需3次移动即可完成转移。　　当n=3时，完成转移的过程如图22—3所示。即共需7次移动完成3个金属片的转移。4　　通过上面的试验不仅说明当金片个数为1，2，3时能够分别通过符合要求的1、3、7次移动完成转移，还可以从对转移过程的观察中得到下面的结论：n＝3时，前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个金片需做2

4、n-1次移动。　　解：为了得到金片个数n=64时的移动次数，首先考虑金片个数较小时的情况，并设金片数为n时的移动次数为hn。　　经试验发现，当金片个数为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针上，共需移动hk-1次。因此完成K片金片转移需要移动2hk-1＋

5、1次。4　　下面证明猜测的正确性：显然n=1，2，3，4时，猜测正确，设n=k-1时需2k-1-1次移动，则hk＝2hk-1＋1=2(2k-1-1)＋1=2k-1　　所以可知hn=2n-1。h64=264-1=18446744073709511615　　因为1年中共365×24×60×60＝31536000秒，所以完成64片金片　　太阳、行星(包括地球)是在大约30亿年前由不定形物质形成的。恒星，特别是给太阳提供能量的“原子燃料”还能维持100—150亿年。因此，整个太阳系的寿命无疑要短于200亿年，更远远短于5849亿年)。　　回顾：前面我们得到hk=2hk-1

6、＋1，由此递推关系式可知，该数列既非等差也非等比数列。由hk=2hk-1＋1可得：(hk＋1)＝2(hk-1＋1)　　所以｛hk+1｝为等比数列，即hk+1=(h1+1)·2k-1=2k所以hk=2k-1即hn=2n-1。　　一般地，递推关系式为an=an-1·q＋d(q≠1，d≠0)的数列｛an｝叫做等比差数列，其通项可以按如下方法得到。　　可得：数列｛an｝的通项为4　　注：在解决问题时，有时可以采用把总目标分解为若干子目标的策略，把总目标分解为一系列子目标，并一个个地去解决子目标，从而减轻问题解决者的工作负荷。本题可以采用此策略。以n=3时的情况(见图22—

7、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次

8、。　　在一