娱乐 奇怪的算法挑战【第④期】幸运的位置

[Muriya Tensei]

小羊遇到了一场试炼，与他一同参与的还有n个人。

试炼的内容如下：

1. 所有人（未被淘汰的人）站成一排，并从1开始按顺序编号

2. 随机等概率挑选一个编号为奇数的人淘汰

3. 所有人保持相对顺序不变，重复1,2直至只剩一人，这一人胜出

 

Q1：那么小羊站在几号位置，胜出的概率最大呢

 

如果试炼的内容改为：

1. 所有人（未被淘汰的人）站成一排，并从1开始按顺序编号

2. 随机等概率挑选一个编号为奇数的人淘汰，并给其余未被淘汰的人积1分

3. 所有人保持相对顺序不变，重复1,2直至只剩一人，一轮比赛完成，记录每个人的得分

4. 重复试炼m场（m足够大），积分高的人获胜

 

Q2：那么小羊站在几号位置，胜出的概率最大呢

 

例子：

如果共3人，编号后如下

1,2,3

进行一轮淘汰后（假设淘汰了1）变为

2,3

保持顺序不变重新编号

1,2

再进行第二轮淘汰（淘汰了1）

2

只剩一人，第一场试炼结束，此时最后剩下的是（初始的）3号选手，留至最后并积了两分

 

[chrisforest]

选出人之后，后面的人数字都会变，这个游戏，成为奇数的时间越长越危险，所以应该是2号最安全吧，除非抽到了1号，在1号被抽走之前都是绝对安全的

[Muriya Tensei]

6 分钟前，chrisforest说道:

选出人之后，后面的人数字都会变，这个游戏，成为奇数的时间越长越危险，所以应该是2号最安全吧，除非抽到了1号，在1号被抽走之前都是绝对安全的

看似如此，但并没有这么简单

（比如这两问，其实就是有区别的，只考虑一个方面显然并不全面）

[reflectK]

0.为什么不问问万能的AI呢？

引用

 

有n个人排成一排，按1到n编号。

 

 

在这n个人中，第一个人编号为1，最后一个人编号为n。

 

 

现在，重复以下过程：让一个编号为奇数的人出局，并重新编号，直到只剩下最后一个人为止

 

 

在重复过程中，每次会将编号为奇数的人出局，并将剩余人的编号重新按顺序排列。最后只会剩下一个人，此人的编号就是最后一个人的编号。

 

那么，初始编号为多少的人，成为最后一个人的几率最大呢？

 

初始编号为偶数的人会在每轮中被淘汰，所以初始编号为奇数的人有更高的几率成为最后一个人。具体而言，如果n为奇数，则初始编号为n的人有最高的几率成为最后一个人，因为他是唯一的奇数编号。如果n为偶数，则初始编号为n-1的人有最高的几率成为最后一个人，因为他是唯一的奇数编号且最后一个被淘汰。

——Generated by ChatGPT

呃，好吧。。。幸好这个问题不算很难，我们可以手动解决。

1.问题1——活下去

假设有N=2k个人参与游戏。

很显然地，1号不可能活到最后，因为最后一轮1号必然被淘汰。

那么2号生存的概率是多少呢？不难看出，如果有在2号之后的人能活下来，2号在最后一轮必定死亡，所以必然只有1,2号

2号生存的几率是(k-1)/k * (k-1)/k * (k-1)/(k-2) * (k-1)/(k-2) * ...... * 1/2 * 1/2 = 1/k^2

3号生存的几率，就是2号和3号在最后的几率，也是1/k^2

4号生存的几率，就是2号和4号加上3号和4号的几率，即2/k^2

5号生存的几率也是2/k^2

猜测生存的几率是ceil((m-1)/2)/k^2 (m是编号)

有因为m号的生存几率可以从前面的几率推出来

现在使用数学归纳法证明

p_m=1/k*ceil((m-1)/2)/(k-1)k + (k-ceil((m-1)/2)-1)/k*ceil((m-1)/2)/(k-1)k = ceil((m-1)/2)/k^2 m是奇数

p_m=1/k*（ceil((m-1)/2)-1）/(k-1)k + (k-ceil((m-1)/2))/k*ceil((m-1)/2)/(k-1)k = ceil((m-1)/2)/k^2 m是偶数

故当N为偶数时，最后一位最可能活到最后。

 

那么N为奇数呢？

假设有N=2k+1个人参与游戏。

事实上，使用类似的证明方法我们可以证明生存的几率是ceil((m-1)/2)/k(k+1)，读者可以仿照上文证明，把这题当做练习。

 

总之，我们有结论，如果人数为偶数，最后一个人几率最大，如果为奇数，最后两个人几率最大。

2.问题2——积分高

可以发现，这个问题每次由一个n人的问题变为一个n-1人的问题，且没有后效性。

所以可以使用概率动态规划的算法。对于某个人K，可以分类讨论是K之前的人死了还是K之后的人死了，亦或是K本人死了。

这里选取K=1000，运用计算机模拟可得2号存活轮数最高，存活轮数平均约为557.1轮。

因此，第二个问题的答案是2位。

剧透

 @Muriya Tensei 第二题的话因为时间原因可能写不出来详细的dp式子，但是我认为是可以推出第二个人存活轮数最高的，计算机模拟也支持这一点。

 

一月 14, 2023，由reflectK修改

[黔驴技穷]

按理来说2号应该是最安全的吧，在2号之后不管消耗几个人都不会动摇他的地位，只是1号倒了之后他就是下一个1号了

重新看了一下题目和别人的答案，思路应该错了

一月 14, 2023，由黔驴技穷修改

[l1ll5]

https://www.zhihu.com/question/55445739

来拆台了（逃

[reflectK]

3 分钟前，l1ll5说道:

https://www.zhihu.com/question/55445739

来拆台了（逃

啊 原来已经有答案了吗。。。

[Muriya Tensei]

于 2023/1/14 于 PM8点56分，l1ll5说道:

https://www.zhihu.com/question/55445739

来拆台了（逃

我超，知乎还真有这个问题的解，甚至两问都提到了，撞得彻底（没事，就当给正确答案站台了）