100个人的生存游戏

056254628

100个人，从1标号到100，面向圆心排成一个圆圈（2号在1号的右边，3号在2号的右边，依此类推，1号在100号的右边）。
初始在100号和1号之间有一个标志。
现在开始投骰子，投出几，就从标号开始逆时针数数，数到哪个人，就将他从圆圈队列中淘汰，标志移到他的位置。
接着投骰子。
这样一直进行下去，每投一次骰子就有一个人淘汰。
最后投了99次骰子后，必剩下最后一个人,若最后剩下的为k号，称作k号存活。
k号存活的概率记作P(k)    ($1<=k<=100$)
1. 求P(k)。
2. 哪个号码存活概率最高？

showjim

骰子能投出哪些数？概率是否均衡？

056254628

回2＃
1-6六个数，概率都相同

gxqcn

还应规定好初始标志位置，不妨假定为1号。

hujunhua

还应规定好初始标志位置，不妨假定为1号。
gxqcn 发表于 2011-4-28 10:44

应该是0号，也就是在1号与100号之间。因为按题意，标志是有有个立牌的，清除谁，就用标志牌代替他。

mathe

逆推吧。计算出k个人生存游戏的概率分步后，k+1个人情况的计算就很简单了。当然这个复杂度需要O(n^2)

056254628

记f(n,k)表示总数n个人的第k号的生存概率，用Y(m,n)表示m关于n的同余数( $0<=Y(m,n)<n)$)，比如Y(-1,n)=n-1
那么,按照mathe的递推方法，应该有
        f(n,0)=0
                 f(1,1)=1
                $f(n,k)=1/6*\sum_{i=1}^{6}f(n-1,Y(k-i,n))$
---------------------------------
计算得 f(100,6)  =0.00771126454402384，最小值
       f(100,100)=0.0118327195203688，最大值
-------------------------------------
记f(n,k)的最小值为fmin(n)，最大值为fmax(n)，平均值为1/n.
那么当n趋于无穷大时，
     最大值/平均值=$n*fmax(n)$，最小值/平均值=$n*fmin(n)$
极限存在.
能否求出这两个极限值(用级数表示或常见的常数来表示)？

showjim

逆推吧。计算出k个人生存游戏的概率分步后，k+1个人情况的计算就很简单了。当然这个复杂度需要O(n^2)
mathe 发表于 2011-4-28 18:35

要精确求解的话，涉及大数加法与乘法运算，时间复杂度O(x*n^3)

到处瞎逛

凭感觉最后剩下的概率应该是一样的吧。

不知道有没有人能算出最后的结果。

KeyTo9_Fans

$7$楼正解。

如果能够把$f(100,k)$的柱状图画出来就一目了然了。

取$n=1,2,4,8,16,32,...$，就可以看出$n*fmax(n)$和$n*fmin(n)$的大致趋势。

我们还可以对原问题做一个扩充：

骰子有$m$个面，可以掷出$1$到$m$的数，概率均为$1/m$。

考察两个极限值与$m$的关系。