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)能否求出这两个极限值(用级数表示或常见的常数来表示)？

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$的关系。