一道和调和级数有关的问题

最近碰到一个调和级数有关的问题,挺有意思的,这里记录一下,题目来自Mit公开课Session 23

问题

假设一个人在沙漠里探险,他随身最多携带$1$加仑水,行走一天需要消耗$1$加仑水(为方便讨论,假设一天行走的距离为$1$),但是可以在任意地点存储水,到达任意一个地点后需要返回,例如携带$1$加仑水最多到达距离出发点$\frac 12 $的位置,因为需要来回。假设最开始他在起始点$A$并且$A$处的水无限,现在问此人能否走到离$A$任意远的地方?

考虑$A$处有$n$加仑水,其能够行走的距离,其中$n\in \mathbb N$。

当$n=1$时,由提示可知最远距离为$\frac 12 $;当$n\ge 2$时,考虑出发点为$n$加仑水和出发点为$n-1$加仑水的关系,思路如下:

首先想办法存储$n-1$加仑的水,假设存储点距离出发点为$a$,那么来回一次可以存储的加仑数为

假设来回$k$次,那么总共存储的加仑数为

要使得上式为$n-1$,可取

即缓存点距离出发点的距离为$\frac 1{2n}$。注意最后一次运水后缓存点的加仑数为$n-1$,此时将身上剩下的$\frac 1 {2n}$加仑水也存储起来,利用剩下的$n-1$加仑水前进,前进距离为按此策略并且出发点为$n-1$加仑水前进的距离,最后回到存储点用剩下的$\frac 1{2n}$返回出发点$A$即可。如果记按这个策略操作,出发点为$n$加仑水达到的最远距离为$d_n$,那么不难看出

特别的,我们取

所以

其中

而调和级数$H_n$是发散的,所以只要$n​$充分大,按此策略就能达到任意远的距离。

本文标题:一道和调和级数有关的问题

文章作者:Doraemonzzz

发布时间:2019年05月01日 - 21:42:50

最后更新:2019年05月02日 - 20:50:41

原始链接:http://doraemonzzz.com/2019/05/01/调和级数有关的离散数学问题/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。