找回密码
 欢迎注册
楼主: KeyTo9_Fans

[原创] 山顶上的决斗

[复制链接]
发表于 2013-4-4 18:21:50 | 显示全部楼层
这题简单些'wayne必胜'可以动态规划需要k步的集合
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-5 13:07:44 | 显示全部楼层
$a_{0,n}=0,a_{n,n}=n,a_{n,k+1}={1+a_{n-1,k}}/{1+a_{n+1,k}}a_{n+1,k}$
找出最小的n使得$a_{1 ,n}<=1/3$即可

评分

参与人数 1威望 +3 贡献 +3 鲜花 +3 收起 理由
KeyTo9_Fans + 3 + 3 + 3 虽然看得很晕,但它是对的……@_@

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-4-5 23:59:08 | 显示全部楼层
看来这题难不倒mathe呀~

为什么是这样的式子呀?

mathe没有解释,看得我很晕呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-6 08:11:36 | 显示全部楼层
现在没电脑不方便'注意k和n的差是偶数

评分

参与人数 1金币 +3 收起 理由
KeyTo9_Fans + 3 嘿!我还真没注意到!这样似乎木有问题鸟… ...

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-7 21:03:26 | 显示全部楼层
其实就是要计算出所有k步可以到达的状态集合。体力比表示wayne的体力和Fans体力之比。
显然其中一步达到的只有n=1,体力比p>1.得到集合S1={(n,p)|n=1,p>1}
如果两步达到,wayne必然有办法使得一步后必然到达S1,对于集合S2={(n,p)|n=2,p>2}可以达到。
同样,对于S3,只能初始状态为n=3或n=1.其中n=1的,wayne同样要想法达到S2,
假设wayne使用策略体力x=p,而Fans使用一个略大于p但是非常接近p的策略,于是到达(2,p/(1-p)) in S2

评分

参与人数 1贡献 +3 收起 理由
KeyTo9_Fans + 3 分析得不错。但$12$楼的式子是对的吗?

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-8 19:08:33 | 显示全部楼层
首先我们知道离山顶n步时,如果wayne体力是Fans的n倍以上,那么必胜。假设wayne体力是Fans的a(n)倍以上时,可以必胜,其中a(n)是上确界。那么当体力比a充分接近a(n)时,wayne必然可以有策略使用体力x,使得当Fans使用体力小于x时,得出a(n-1)<a-x,而当Fans使用体力大于x一点点时,有a(n+1)<a/(1-x),
于是x<a-a(n-1), a(n+1)<a/(1-x)<a/(1-a+a(n-1)),让a趋向a(n)得出关系式a(n+1)<=a(n)/(1-a(n)+a(n-1))
反之,如果这个不等式对于某个n严格不成立,我们可以找出x改善a(n),同a(n)是确界矛盾。
于是得出a(n+1)=a(n)/(1-a(n)+a(n-1)), a(n+1)-a(n)=a(n)*(a(n)-a(n-1))/(1-a(n)+a(n-1))>a(n)*(a(n)-a(n-1))
容易看出a(n)单调增,得出a(n+1)-a(n)越来越大,很快就可以大于1,但是这个是不可能的。由此得出只能a(n)=a(n+1),然后可以得出它们都是0,也就是wayne必胜。
于是在必胜的条件下用类似方法可以推导出12#的递推式
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-9 06:18:26 | 显示全部楼层
发现前面推理中有错误,也就是wayne不是必胜的。根据16#的递推式,给定$a_0=0$,$a_1$为任意正数,然后
$a_{n+1}={a_n}/{1-a_n+a_{n-1}}$,如果递推到某一项出现负数,那么wayne是可以100%取胜。但是如果可以一直保持正数,那么Fans可以一直将wayne阻挡在山顶以外,唯一的例外是存在一个临界点值,这时,wayne可以以100%的概率登顶,但是平均需要的步长是无穷步。不过这个临界值不大好计算。而对于$a_1=1/3$估计Fans可以获胜
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-9 18:25:51 | 显示全部楼层
试着计算了一下,数值计算结果表示$a_1=1/3$正好在临界点,也就是是wanye可以赢,但是绝对会筋疲力尽。Fans可以让wanye赢得任意慢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-4-10 08:58:06 | 显示全部楼层
嗯,数值计算是个好方法,虽然不太严谨,但至少给出了一个猜想。

那wayne可以赢的概率是多少呢?

给定$N$,如果Fans的目标只是阻挡wayne$N$步,那Fans能成功阻挡$N$步的概率是多少呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-10 10:21:55 | 显示全部楼层
收藏学习,再次感受到自身的浅薄,诚愿楼主教我。 高中之后就没学过数学了,但是真心希望能学习通过数学方法解决问题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 04:35 , Processed in 0.043377 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表