调和级数的趣题

今天看《算法导论》中的随机算法段落的时候,看到了一个公式

。查了一下Wiki知道这是个调和级数,还知道了一个有趣的题目”橡皮筋上的蠕虫”。

“假设一条蠕虫沿着一条1米长的橡皮筋爬行,而橡皮筋每分钟之后均匀伸展1米。如果相对于其所在的橡皮筋,蠕虫的爬行速度是每分钟1厘米,那么它最终会到达橡皮筋的另一头吗?”

这里的橡皮筋伸展1米,不是说橡皮筋在一端延长1米,而是在橡皮筋每个点均匀伸展,所以每次伸展的时候,蠕虫和起点的距离都会等比的增大。

直觉上看,这只蠕虫永远到达不了橡皮筋的另一头,但是仔细算一下就知道这个答案是肯定的。

我们假设 \(g(n)\) 是表示n分钟之后蠕虫已经爬的距离的函数。

,其中\(g(0)=1\), 那么n分钟之后蠕虫爬行的距离和橡皮筋总长的比例是函数

, 所以

, 当$f(n)=1$的时候,蠕虫爬到了橡皮筋的另一端,这时用上面的求和公式可以知道当