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

[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修改

[reflectK]

3 分钟前，l1ll5说道:

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

来拆台了（逃

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