山顶的决斗

问题描述

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

Fans的砖头

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

zeroieme表示wayne必然赢

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

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

最后wayne赢。

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

mathe给出了一个递推数列

mathe也表示wayne必赢 ,他说可以用动态规划来做,于是他抛出了一个递推数列: a0,n=0,an,n=n,an,k+1=1+an1,k1+an+1,kan+1,ka_{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使得a1,n13a_{1 ,n}\le \frac13即可. 这个数列实在有些莫名其妙, KeyTo9_Fans也表示看了很晕,但是他评论这个数列是正确的。 mathe提示上面表达式中k和n的差必须是偶数。

动态规划初步分析

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

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

存在临界点

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

数学推导

mathe定义f0(x)=0,f1(x)=xf_0(x)=0,f_1(x)=x,fn+1(x)=fn(x)1fn(x)+fn1(x)f_{n+1}(x)=\frac{f_n(x)}{1-f_n(x)+f_{n-1}(x)}gn(x)=fn(x)fn1(x)g_n(x)=f_n(x)-f_{n-1}(x),于是gn+1(x)=fn(x)gn(x)1gn(x),fn+1(x)=fn(x)+gn+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都严格单调增(注意x1x\frac{x}{1-x}是增函数) 然后我们计算可以知道fn(13)=nn+2f_n(\frac13)=\frac{n}{n+2},由此可以知道limn+fn(13)=1\lim_{n\to+\infty}f_n(\frac 13)=1 反之,对于任意e>13e\gt\frac13,由于fn(e)=g1(e)+g2(e)+...+gn(e)(e13)+g1(13)+g2(13)++gn(13)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) 所以我们得出limn+fn(e)(e13)+limn+fn(13)=1+(e13)>1\lim_{n\to+\infty}f_n(e)\ge(e-\frac13)+\lim_{n\to+\infty}f_n(\frac13)=1+(e-\frac13)\gt 1 也就是13\frac13是题目中提到的界。

结论分析

KeyTo9_Fans最后做出总结 我们得到以下结论: 设wayne的初始体力是xx, 当x(1,+)x\in(1,+\infty)时,只需要11步登顶; 当x(23,1)x\in(\frac23,1)时,需要33步登顶; 当x(59,23)x\in(\frac59,\frac23)时,需要55步登顶; 当x(12,59)x\in(\frac12,\frac59)时,需要77步登顶; 当x(715,12)x\in(\frac7{15},\frac12)时,需要99步登顶; 当x(49,715)x\in(\frac49,\frac7{15})时,需要1111步登顶; 当x(37,49)x\in(\frac37,\frac49)时,需要1313步登顶; 当x(512,37)x\in(\frac5{12},\frac37)时,需要1515步登顶; 当x(1127,512)x\in(\frac{11}{27},\frac5{12})时,需要1717步登顶; 当x(25,1127)x\in(\frac25,\frac{11}{27})时,需要1919步登顶; 当x(1333,25)x\in(\frac{13}{33},\frac{2}{5})时,需要2121步登顶; 当x(718,1333)x\in(\frac{7}{18},\frac{13}{33})时,需要2323步登顶; …… 总之,NN步之内登顶所需的最小初始体力可以无限接近13\frac13,但达不到13\frac13。 当初始体力为13\frac13时,能登顶的概率是11,但所需步数的期望值是++\infty。 当初始体力小于13\frac13时,能登顶的概率是00。 所以,在这个游戏中,wayne能登顶的概率要么是00,要么是11, 不存在某个初始体力使得wayne能登顶的概率介于0011之间,除非上帝不公正。

© 2021 Blog Boost Starter