世界末日何时到来
第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时的情况;第四次移动是将最
2时的大的金片从A针移到B针;最后的三次又是重复n,过程,即保持B针上的最大金片不动,将C针上的二片移到B针上。同样地,我们可以用类似方法找到一种完成4个金片移动的
:前7次保持A针上的最大金片不动,用n=3时的方法将最上面的三个金片移到B针上;第8次移动是将A针上的最大金片移到C针上;最后需要将B针上的三个金片移到C针上,这与n=3时的移动方法相同,共需7次。所以要完成4片金片的转移共需15次移动。
由以上的结果可以知道,可以通过有限次的移动完成
n有限个金片的转移,且猜测转移n个金片需做2-1次移动。
解:为了得到金片个数n=64时的移动次数,首先考虑金片个数较小时的情况,并设金片数为n时的移动次数为h。 n
经试验发现,当金片个数为1,2,3,4时,完成转移要求分别需要1,3,7,15次移动,即h=1,h=3,h=7,123h =15,并猜测hn=2n-1。 4
一般地,要转移k块金片,只需通过hk-1次移动首先将最上面的k-1片(最大的一片不动)移到另外的一根针上,不妨设转移到B针上,然后将最大的一片移到C针上,最后仍然是保持C针上的最大金片不动,将B针上的k-1片按要求移到C针上,共需移动h次。因此完成K片金片转移k-1
需要移动2hk-1,1次。
下面证明猜测的正确性:显然n=1,2,3,4时,猜测
k-1正确,设n=k-1时需2-1次移动,则
k-1kh,2h,1=2(2-1),1=2-1 kk-1
n所以可知h=2-1。 n
64h=2-1=18446744073709511615 64
因为1年中共365×24×60×60,31536000秒,所以完成64片金片
太阳、行星(包括地球)是在大约30亿年前由不定形物质形成的。恒星,特别是给太阳提供能量的“原子燃料”还能维持100—150亿年。因此,整个太阳系的寿命无疑要短于200亿年,更远远短于5849亿年)。
回顾:前面我们得到hk=2hk-1,1,由此递推关系式可知,该数列既非等差也非等比数列。由hk=2hk-1,1可得:
(h,1),2(h,1) kk-1
k-1k所以,h+1,为等比数列,即h+1=(h+1)?2=2所以kk1
knh=2-1即h=2-1。 kn
一般地,递推关系式为a=a?q,d(q?1,d?0)的nn-1
数列,a,叫做等比差数列,其通项可以按如下方法得到。 n
可得:数列,a,的通项为 n
注:在解决问题时,有时可以采用把总目标分解为若
干子目标的策略,把总目标分解为一系列子目标,并一个个地去解决子目标,从而减轻问题解决者的工作负荷。本题可以采用此策略。以n=3时的情况(见图22—3)为例。它
个金片从A针移到B针。这个总目标可以分的总目标是把3
成若干子目标。第一个子目标,是首先要把最大的金片(即金片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
自然数作为a,a,而后面的每一项均为前两项的和,即12
当n?3时an=a+a。问(1)若该数列中出现某一项恰好为n-1n-2
5的倍数,以后是否还会有5的倍数出现,(2)对于任意给出的a、a,是否该数列一定会有5的倍数出现, 12
练习22
1(用1克和3克的砝码可以称出1至4克的重物,为了保证用尽可能少的砝码称出尽可能多的重物,第三个砝码
克重物的前提下重量尽可能地大,应是在保证能够称出5
所以选9克的进码,其中用下列方法可以称出5克的重物:一侧放重物及1克、3克的砝码,另一侧放9克的砝码。称6克重物的方法是天平一侧放重物和3克的砝码,另一侧放9克的砝码,依此类推,用1、3、9克的砝码可以称出81到13克的重物。同样地第四个砝码应选27克,这是能保证称出14克重物的重量最大的砝码,而用1、3、9、27克的砝码可以称出1到40克的重物;而再用81克的砝码可称出1至121克的重物。由上面的分析可得到本问题解答的一般
倍加规律:后一个砝码的重量为前面所有砝码重量和的2
n-11,且第n个砝码的重量为3克。因此,用1、3、9、27、、243、729克的7个砝码可以称出1至1093克的所有整数81
克重物。
2((1)设该数列中的第ak项为5的倍数,即ak=5m,(m?N)而 ak-1-l,则
a,5m+l k+1
a=a+a=10m,l k+2k+1k
a=15m,2l k+3
a,25m,3l k+4
ak,5,40m,5l,5(8m,l)
显然第a项为5的倍数,所以若该数列中出现5的倍k+5
数作为一项,则以后还会出现5的倍数,且每隔4项出现一次。
(2)考虑下面的这个数列:
1,3,4,7,11,18,29,47,„
该数列的每一项除以5的余数分别为
1,3,4,2,1,3,4,2„
即该数列中不可能出现5的倍数。
一般地,数列中不出现5的倍数的可能如下:
(数列中的数为该项除以5的余数)
1,3,4,2„
3,4,2,1„
2,1,3,4
4,2,1,3