问题描述

KeyTo9_Fans于2013年愚人节提出一个问题 :
wayne在登一座山,在离山顶还有1步之遥的时候,
发现KeyTo9_Fans已经在山顶上恭候多时了。
KeyTo9_Fans决定给wayne出道难题,
于是拦住wayne,不让wayne登到山顶,如下图所示:
山顶
———————
Fans(满血:lol)
wayne(\frac13血) 1步之遥
———————
2步之遥
———————
3步之遥
———————
4步之遥
———————
5步之遥
———————
…………
登山之路只有1条,
Fans会一直在路上阻止wayne往上走,
wayne想要登到山顶,只能将Fans顶到山顶上去。
Fans目前拥有1体力值,
而wayne只有\frac13体力值。
Fans和wayne将进行N个回合的较量。
在每一回合里面:
————————————
Fans和wayne同时发力,
假设本回合Fans使出了a的体力值,wayne使出了b的体力值,
如果a>b,那么wayne就会被Fans往下推1步,于是离山顶又多了1步之遥,但Fans会消耗掉a的体力值,wayne的体力值则保持不变;
如果a,那么wayne就会把Fans往上顶1步,于是离山顶就少了1步之遥,但wayne会消耗掉b的体力值,Fans的体力值则保持不变;
如果a=b,那么上帝就会掷骰子决定1种结果(此时,上述2种结果发生的概率均为50%)。
————————————
注意:体力值只会减少或不变,无法增加。
体力值可以用光,但不能透支。
wayne会采取最佳策略登到山顶。
Fans会采取最佳策略阻止wayne登到山顶,如果阻止不了,则会让wayne登到山顶所用的回合数的期望值尽可能大。
问题1:当N\to\infty时,wayne能登到山顶的概率是多少?
问题2:在wayne能登到山顶的前提下,wayne所用回合数的期望值是多少?

#Fans的砖头
KeyTo9_Fans首先表示,
【抛砖】满血的Fans看起来坚不可摧,实际上……
可以预见地,wayne在第1回合就会不惜一切代价,使出所有的体力顶Fans。
Fans只能使出\frac13以上的体力阻止wayne(不然Fans就输啦!),
结果wayne一上来就耗掉了Fans共\frac13以上的血,如下图所示……
山顶
———————
1步之遥
———————
Fans(\leq\frac23血)
wayne(\frac13血)  2步之遥
———————
3步之遥
———————
4步之遥
———————
5步之遥
———————
…………
wayne接下来还有什么高招呢?

#zeroieme表示wayne必然赢
假设wayne离山顶还有n步,此时他计划把体力非平均分配为(W_1,W_2,\dots,W_n),各步体力总和\sum W_i=W_a,假设是第a次规划
前面Fans的砖头就是n=1的特例。

如果wayne前n-1步,都成功。wayne剩余体力W_a。如Fans砖头的分析,Fans为了最后一步阻止,必然使用W_a+ε,其中ε是无限逼近0的正数。
往前想,wayne为了W_a最大,就是消耗Fans最大体力。前n-1步只要用一点点力ε。Fans怎么办?保留体力用更小力。于是双方无限逼近0?干脆大家都是0算了,让上帝发声。
这样的话wayne回到n=1的概率长远说是100%,Fans再次消耗\frac13+ε

最后wayne赢。

可是KeyTo9_Fans问,如果Fans依次使用\frac18,\frac1{16},\frac1{32},\frac1{64},\dots的体力,wayne该如何应对呢?
然后zeroieme问了一个很好的问题,就是游戏中双方是否知道对方还剩余多少体力, Fans表示不知道对方每轮使用了多少体力,所以也不知道对方剩余多少体力。不过这个信息好像在后面倍大家忽略了。

#mathe给出了一个递推数列
mathe也表示wayne必赢 ,他说可以用动态规划来做,于是他抛出了一个递推数列:
a_{0,n}=0,a_{n,n}=n,a_{n,k+1}=\frac{1+a_{n-1,k}}{1+a_{n+1,k}}a_{n+1,k}
找出最小的n使得a_{1 ,n}\le \frac13即可.
这个数列实在有些莫名其妙, KeyTo9_Fans也表示看了很晕,但是他评论这个数列是正确的。
mathe提示上面表达式中k和n的差必须是偶数。

#动态规划初步分析
mathe表示
其实就是要计算出所有k步可以到达的状态集合。体力比表示wayne的体力和Fans体力之比。
显然其中一步达到的只有n=1,体力比p\ge 1,, 得到集合S_1={(n,p)|n=1,p\gt 1}
如果两步达到,wayne必然有办法使得一步后必然到达S_1,对于集合S_2={(n,p)|n=2,p\gt 2}可以达到。
同样,对于S_3,只能初始状态为n=3n=1.其中n=1的,wayne同样要想法达到S_2,
假设wayne使用策略体力x=p,而Fans使用一个略大于p但是非常接近p的策略,于是到达(2,\frac{p}{1-p}) \in S_2

首先我们知道离山顶n步时,如果wayne体力是Fans的n倍以上,那么必胜。假设wayne体力是Fans的a(n)倍以上时,可以必胜,其中a(n)是上确界。那么当体力比a充分接近a(n)时,wayne必然可以有策略使用体力x,使得当Fans使用体力小于x时,得出a(n-1)\lt a-x,而当Fans使用体力大于x一点点时,有a(n+1)\lt \frac{a}{1-x},
于是x\lt a-a(n-1), a(n+1)\lt \frac a{1-x} \lt \frac a{1-a+a(n-1)},让a趋向a(n)得出关系式a(n+1)\le\frac{a(n)}{1-a(n)+a(n-1)}
反之,如果这个不等式对于某个n严格不成立,我们可以找出x改善a(n),同a(n)是确界矛盾。
于是得出a(n+1)=\frac{a(n)}{1-a(n)+a(n-1)}, a(n+1)-a(n)=a(n)\times\frac{a(n)-a(n-1)}{1-a(n)+a(n-1)}\gt a(n)(a(n)-a(n-1))
容易看出a(n)单调增,得出a(n+1)-a(n)越来越大,很快就可以大于1,但是这个是不可能的。由此得出只能a(n)=a(n+1),然后可以得出它们都是0,也就是wayne必胜。
于是在必胜的条件下用类似方法可以推导出前面的递推数列。

#存在临界点
mathe后来发现前面推理中有错误,也就是wayne不是必胜的。根据初步分析中的递推式,给定a_0=0,a_1为任意正数,然后
a_{n+1}=\frac{a_n}{1-a_n+a_{n-1}},如果递推到某一项出现负数,那么wayne是可以100%取胜。但是如果可以一直保持正数,那么Fans可以一直将wayne阻挡在山顶以外,
唯一的例外是存在一个体力值比值的临界点值,这时,wayne可以以100%的概率登顶,但是平均需要的步长是无穷步。
后来mathe经过计算发现\frac13就正好是这个临界点,所以在初始体力比大于\frac13时, wayne必然赢,但是小于\frac13时,Fans可以已知将wayne阻挡在山顶之外。
但是Fans给出的条件很有意思,正好在临界点,导致wayne必然会赢,但是必然会精疲力尽,Fans可以让wayne花费任意多步数后才能够赢。

#数学推导
mathe定义f_0(x)=0,f_1(x)=x,f_{n+1}(x)=\frac{f_n(x)}{1-f_n(x)+f_{n-1}(x)}
g_n(x)=f_n(x)-f_{n-1}(x),于是g_{n+1}(x)=\frac{f_n(x)g_n(x)}{1-g_n(x)}, f_{n+1}(x)=f_n(x)+g_{n+1}(x)
于是可以看出,在f,g连续的部分,必然有g和f都严格单调增(注意\frac{x}{1-x}是增函数)
然后我们计算可以知道f_n(\frac13)=\frac{n}{n+2},由此可以知道\lim_{n\to+\infty}f_n(\frac 13)=1
反之,对于任意e\gt\frac13,由于f_n(e)=g_1(e)+g_2(e)+…+g_n(e)\ge(e-\frac13)+g_1(\frac13)+g_2(\frac13)+\dots+g_n(\frac13)
所以我们得出\lim_{n\to+\infty}f_n(e)\ge(e-\frac13)+\lim_{n\to+\infty}f_n(\frac13)=1+(e-\frac13)\gt 1
也就是\frac13是题目中提到的界。

#结论分析
KeyTo9_Fans最后做出总结
我们得到以下结论:
设wayne的初始体力是x
x\in(1,+\infty)时,只需要1步登顶;
x\in(\frac23,1)时,需要3步登顶;
x\in(\frac59,\frac23)时,需要5步登顶;
x\in(\frac12,\frac59)时,需要7步登顶;
x\in(\frac7{15},\frac12)时,需要9步登顶;
x\in(\frac49,\frac7{15})时,需要11步登顶;
x\in(\frac37,\frac49)时,需要13步登顶;
x\in(\frac5{12},\frac37)时,需要15步登顶;
x\in(\frac{11}{27},\frac5{12})时,需要17步登顶;
x\in(\frac25,\frac{11}{27})时,需要19步登顶;
x\in(\frac{13}{33},\frac{2}{5})时,需要21步登顶;
x\in(\frac{7}{18},\frac{13}{33})时,需要23步登顶;
……
总之,N步之内登顶所需的最小初始体力可以无限接近\frac13,但达不到\frac13
当初始体力为\frac13时,能登顶的概率是1,但所需步数的期望值是+\infty
当初始体力小于\frac13时,能登顶的概率是0
所以,在这个游戏中,wayne能登顶的概率要么是0,要么是1
不存在某个初始体力使得wayne能登顶的概率介于01之间,除非上帝不公正。