每日一题[328]世界末日

g(n)表示n的最大奇因数,如g(9)=9g(10)=5.那么g(1)+g(2)+g(3)++g(220151)=_____.


cover 正确答案是1420151

 根据g(n)的定义有g(n)={n,n,g(n2),n.

Sn=g(1)+g(2)+g(3)++g(2n1),则Sn=[g(1)+g(3)++g(2n1)]+[g(2)+g(4)++g(2n2)]=[1+3++(2n1)]+[g(1)+g(2)++g(2n11)]=4n1+Sn1.
由累加法知S2015=42014+42013++41+1=13(420151).
本题很难直接找到g(n)的表达式,但从g(n)满足的递推关系入手就容易很多,因为g(n)具有很好的递归结构.


递归是解决数列问题的一个常见思路,其中有递归结构的一个著名的问题是汉诺塔问题,这个问题是这样的:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽. 假设每秒钟可以移动一个金片,那么预言中的世界末日何时到来呢? 假设金片数量为n时,把一根针上的金片移动到另外一根针上需要an秒,则an就满足递推关系an=2an1+1,n2

从而可以由不动点法求得数列{an}的通项公式为an=2n1,
所以a64=18446744073709551615
秒,折成年约为5845.54亿年.

 汉诺塔问题参考百度百科.


最后给出一道练习:

数列{2n1}的前n1,3,7,,2n1组成集合An={1,3,7,,2n1}(nN),从集合An中任取kk=1,2,,n)个数,其所有可能的k个数的乘积的和为Tk(若只取一个数,规定乘积为此数本身),记Sn=T1+T2++Tn.例如当n=1时,A1={1}T1=1S1=1;当n=2时,A2={13}T1=1+3T2=1×3S2=1+3+1×3=7.则Sn=_______.

答案 2n(n+1)21

提示 可以得到Sn满足的递推关系Sn=Sn1+(2n1)+(2n1)Sn1,n2

从而得到Sn+1Sn1+1=2n,
由累乘法即可得到Sn的表达式.

 练习题另外一种解法见每日一题[308] 山重水复疑无路,似曾相识燕归来.递归结构的另外一个著名的例子是卡特兰数

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复