【报数拆区间】游戏的最佳策略

KeyTo9_Fans

【报数拆区间】游戏是一个有裁判参与的多玩家混战游戏。

游戏开始前，由随机数发生器产生一个$1$到$100$的随机数。

（产生$1$到$100$之间的任何一个数的概率均等，均为$1/100$）。

这个数只有裁判知道是多少，其余所有的玩家都不知道这个数是多少。

这个数生成后，所有玩家排成一圈，然后裁判转动转盘。

待转盘指针稳定后，指针指到的玩家开始报一个数。

所报之数必须是已知区间里的一个数。

该已知区间一开始是$[1,100]$。

假设所报之数是$y$，随机数发生器产生的数是$x$。

如果$y=x$，则游戏结束，报数的玩家输，接受惩罚（一般是头上的气球爆炸，或者是一个冰桶盖下来）。

如果$y\ne x$，则游戏继续，分两种情况讨论。

情况$1$、$y>x$，则已知区间缩小为$[1,y-1]$。

情况$2$、$y<x$，则已知区间缩小为$[y+1,100]$。

也就是说，已知区间被$y$劈成了两半，缩小后的已知区间是包含$x$的那一半。

然后游戏继续，由第二个玩家在新的已知区间内报一个数，重复上述流程。

直到某个玩家所报之数等于$x$为止，该玩家输，接受惩罚。

以下是所有玩家都具备的无穷阶公共知识：

$1$、最小化自己输的概率。

$2$、若存在多种方案使得自己输的概率最小，则最大化对面玩家输的概率（城中失火，殃及池鱼：旁边的玩家输，自己也遭殃。因此让离自己最远的玩家输，即让对面的玩家输，自己受到的伤害最小）。

$3$、若存在$2$个距离相等的【对面玩家】，则无所谓了，抛硬币决定让谁输的概率大。

$4$、在自己输的概率最小化，对面玩家输的概率之和最大化的前提下，还存在多种并列方案，则最大化第二远玩家输的概率之和，然后最大化第三远玩家输的概率之和，依次类推。

$5$、若还存在并列，就无所谓了，掷骰子决定报哪个数吧。

问这个游戏的最佳策略。

#####

郑重声明：

这个游戏是有策略可言的。举个简单的例子：$3$个数$\{1,2,3\}$，$2$个玩家。问先行报数的玩家报几？答案是$2$。因为报$2$只有$1/3$的概率输；若报$1$或$3$，输的概率均为$2/3$。

.·.·.

为啥是100个数而不限制玩家数量
比如如果有101个玩家呢（……）

mathe

两个玩家应该还是挺简单的，稍微多一些玩家就会比较复杂了。
但是我觉得很有可能每次挑选最中间就可以了，思路很简单，尽快结束游戏，降低下一轮还轮到自己的概率。当然在无法改变命运时，开始会为了欺负紧跟着自己的小弟而选择边上的数字了。
比如两个人，可以简单逆推。由于这时遇到多种方案概率相等时，怎么选择都不影响最终结果，所以
如果面对的区间只有一个数字了，那就100%失败，p[1]=1
   如果面对的区间有两个数字，那么选哪个都一样，50%失败，p[2]=1
而对于$n>=3$个数字,挑选第k个失败的概率是$1/n+(k-1)/n*(1-p[k-1])+(n-k)*(1-p[n-k])$
计算结果在选择k为$[(n+1)/2]$时最小，概率为$1/2+{cos((n-1)*pi/2)}/{2n}$,而如果要证明结论，也很简单，数学归纳法即可

mathe

三个玩家玩游戏时，除了计算各种方案下当前玩家输掉的概率，还需要记录其它玩家输掉的概率，所以计算相对要复杂一些。
如果只有1个或2个数，第一个显然选择第一个数即可（怎么选择都没有区别），自己输的概率分别是1或1/2
而如果三个数时，第一个选手怎么选择失败的概率都是1/3，所以为了害小弟，会选择数字2，让小弟有2/3概率输掉。
而如果四个数时，选择第一个数时，无论选择哪个数，自己失败概率为1/4（选择1号时，由于小弟的助攻，还是可以无恙），所以还是选择了2号迫害小弟，导致失败概率为1/4，但是小弟失败概率为1/2，而三号选手有1/4的概率失败。
但是如果五个数时，情况稍微有点变化了，如果选择第一个数，失败的概率就是1/5+4/5*1/4=2/5了，但是选择第二个数和第三个数的失败概率都为1/5。但是同样选择第二个数可以更好的害小弟，所以选了2号。依次类推下去，计算结果表示3个人时，总是要选择第一个或第二数来迫害小弟。应该是模6为周期，分别选择1,1,2,2,2,2。前提是相信无论你如何迫害小弟，他还是爱你依旧。

mathe

mathe 发表于 2019-3-11 14:14
三个玩家玩游戏时，除了计算各种方案下当前玩家输掉的概率，还需要记录其它玩家输掉的概率，所以计算相对要 ...

三个人情况前面算错了，结果很复杂，没有明显的规律

数论爱好者

改一下游戏规则
猜到与裁判一样的数为赢家
不管裁判的数多大,至多猜10次,就可以猜中裁判的数

.·.·.

mathe 发表于 2019-3-11 14:35
三个人情况前面算错了，结果很复杂，没有明显的规律

算4个人的就好
1-4，自己输掉的概率为1,1/2,1/3,1/4
为了更好地害小弟，大家不约而同地选择最边上的数字

5，我们可以知道，之后的人都是选择最边上的数字，所以这时候不能选靠边的数字(选最边上的数字，则在更靠后的时候有概率轮到自己，这样会增大自己输的概率)
5-8，为了更好地关爱小弟，选中间的数字

……果然好麻烦

mathe

两个玩家时选择方案给的不正确。
事实上两个玩家时，面对n个数，如果n是偶数，最有方案是平局，面对n=4k+1,先手输的概率略大，为${2k+1}/{4k+1}$.面对n=4k+3时，先手输的概率略小为${2k+1}/{4k+3}$。所以任何时候，玩家的对策是尽量产生4k+1型的局面。
比如如果面对的局面是$n=2m$,可以分拆为$2m=(4h+1)+1+(2(m-1-2h))$,得出输的概率为
$1/{2m}+{4h+1}/{2m}*{2h}/{4h+1}+{2(m-1-2h)}/{2m}*1/2={1+2h+m-1-2h}/{2m}=1/2$
如果$n=4m+3$,那么可以拆分为$4m+3=(4a+1)+1+(4(m-a)+1)$,得出输得概率为$1/{4m+3}+{4a+1}/{4m+3}{2a}/{4a+1}+{4(m-a)+1}/{4m+3}{2(m-a)}/{4(m-a)+1}={1+2a+2(m-a)}/{4m+3}={2m+1}/{4m+3}$
而如果$n=4m+1$时，那么去掉一个后，怎么选择都结果一样。

mathe

但是切换到3个人以后好像就完全没有规律了，n个数时3人输的概率分别为
[1 1/2 1/3 1/4 1/5 1/6 1/7 1/4 1/3 2/5 5/11 1/4 3/13 3/14 1/5 1/4 5/17 1/3 7/19 7/20 1/3 7/22 5/23 7/24 7/25 7/26 8/27 9/28 9/29 3/10 9/31 9/32 3/11 9/34 11/35 11/36 12/37 13/38 1/3 13/40 13/41 13/42 13/43 13/44 13/45 15/46 16/47 17/48 16/49 3/10 5/17 4/13 17/53 17/54 18/55 19/56 1/3 19/58 19/59 3/10 19/61 19/62 20/63 21/64 21/65 1/3 22/67 11/34 22/69 11/35 22/71 23/72 24/73 25/74 1/3 25/76 25/77 25/78 25/79 5/16 26/81 27/82 27/83 1/3 28/85 14/43 28/87 7/22 29/89 29/90 29/91 15/46 1/3 31/94 32/95 1/3 31/97 31/98 32/99 33/100]
[0 1/2 2/3 1/2 2/5 1/3 2/7 1/4 2/9 1/5 4/11 5/12 6/13 3/7 2/5 3/8 6/17 1/3 6/19 7/20 8/21 9/22 10/23 1/3 8/25 4/13 8/27 9/28 10/29 11/30 12/31 3/8 4/11 6/17 2/7 5/18 10/37 13/38 14/39 7/20 14/41 1/3 14/43 7/22 14/45 6/23 14/47 1/3 17/49 9/25 6/17 9/26 18/53 8/27 16/55 9/28 1/3 10/29 20/59 11/30 21/61 10/31 20/63 21/64 22/65 1/3 23/67 6/17 8/23 12/35 24/71 23/72 24/73 12/37 8/25 13/38 26/77 9/26 27/79 27/80 1/3 27/82 25/83 13/42 29/85 15/43 10/29 15/44 30/89 1/3 29/91 29/92 1/3 16/47 32/95 1/3 34/97 33/98 1/3 33/100]
[0 0 0 1/4 2/5 1/2 4/7 1/2 4/9 2/5 2/11 1/3 4/13 5/14 2/5 3/8 6/17 1/3 6/19 3/10 2/7 3/11 8/23 3/8 2/5 11/26 11/27 5/14 10/29 1/3 10/31 11/32 4/11 13/34 2/5 5/12 15/37 6/19 4/13 13/40 14/41 5/14 16/43 17/44 2/5 19/46 17/47 5/16 16/49 17/50 6/17 9/26 18/53 7/18 21/55 19/56 1/3 19/58 20/59 1/3 21/61 23/62 23/63 11/32 22/65 1/3 22/67 11/34 1/3 12/35 25/71 13/36 25/73 25/74 26/75 25/76 26/77 1/3 27/79 7/20 28/81 14/41 31/83 5/14 28/85 14/43 1/3 15/44 30/89 31/90 33/91 33/92 1/3 31/94 31/95 1/3 32/97 17/49 34/99 17/50]
而选择的对称在3个数是选中间，4个数也是选中间两个，但是5个数只要不选两边就可以。6，7，8个数还是选中间，9个数选中间3个，10个数选中间4个，11个数选两边各两个(1,2,10,11),12~18个数时都神奇的选择了12号数（或对称的数，比如12个数时1，12对称，18个数时，7，18对称）。
19个数时选择方案较多有(1,2,8,12,18,19),20个数时可以选择(1,2,9,12,19,20)，21个数选(2,10,12,20)  ,22个数选(11,12), 23个数只能选12，24个数可以选(2,3,4,12,13,21,22,23), 25个数选(3,4,12,14,22,23)
(需要注意神奇的12还没有退出）
但是26个数时，12号数终于退出最优选择，需要选(4,23)
27个数，选(5,23),  
但是到了28~34个数，神奇的12又回归了（只能选12以及对称数）
而35个数可以选(4,12,13,14,...)
总体上来说，12号数是很受欢迎的
比如前500个数里面找出编号最小的最优选择，结果如下（也就是如果还有比12更小的最优选择，12就不会被显示）
[1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 1, 1, 2, 3, 4, 5, 6, 7, 1, 1, 2, 11, 12, 2, 3, 4, 5, 12, 12, 12, 12, 12, 12, 12, 4, 14, 15, 19, 20, 2, 2, 3, 4, 22, 23, 23, 23, 10, 1, 12, 12, 4, 5, 23, 23, 3, 19, 20, 20, 12, 12, 23, 23, 12, 12, 18, 19, 12, 12, 12, 23, 4, 12, 21, 22, 12, 12, 12, 12, 12, 12, 12, 23, 23, 12, 12, 39, 12, 12, 12, 23, 23, 12, 12, 2, 1, 49, 12, 4, 4, 12, 12, 1, 1, 12, 12, 12, 12, 12, 23, 12, 12, 12, 12, 12, 12, 12, 23, 12, 12, 12, 1, 12, 12, 3, 4, 12, 12, 12, 22, 23, 3, 12, 12, 12, 4, 12, 23, 23, 12, 12, 2, 3, 12, 12, 4, 12, 12, 12, 2, 49, 12, 49, 12, 12, 12, 49, 12, 12, 12, 3, 12, 12, 12, 12, 12, 12, 12, 12, 12, 49, 3, 12, 12, 12, 23, 12, 12, 12, 12, 12, 4, 12, 12, 12, 2, 12, 4, 12, 12, 12, 12, 12, 23, 12, 12, 12, 12, 12, 49, 12, 12, 12, 12, 12, 22, 12, 104, 12, 12, 3, 12, 12, 12, 12, 12, 12, 49, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 23, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 122, 12, 2, 3, 4, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 23, 12, 12, 12, 12, 12, 22, 23, 23, 12, 12, 12, 49, 12, 12, 3, 12, 12, 23, 2, 1, 2, 3, 4, 12, 12, 12, 12, 12, 12, 49, 12, 12, 12, 12, 23, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 20, 12, 12, 12, 3, 12, 23, 12, 23, 12, 12, 12, 12, 12, 12, 12, 12, 12, 2, 12, 4, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 49, 12, 12, 12, 12, 12, 12, 12, 3, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 2, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 104, 12, 12, 3, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 3, 12, 12, 12, 12, 12, 12, 12, 12, 12, 49, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 23, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 49, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 244, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 49, 12]

而如果换成4个选手好像48号数比较受欢迎，但是受欢迎程度和3个选手时的12完全不能相比

mathe

1. sor(n,k)={
   
2.    local(a,b,c,d,p);
   
3.    a=matrix(k,n);
   
4.    a[1,1]=1;
   
5.    for(u=2,k,a[u,1]=0);
   
6.    b=vector(k);c=vector(k);
   
7.    d=vector(n);d[1]=1;
   
8.    for(u=2,n,
   
9.         b[1]=1/u+(u-1)/u*a[k,u-1];d[u]=1;
   
10.         for(v=2,k,
    
11.             b[v]=(u-1)/u*a[v-1,u-1]
    
12.         );
    
13.         for(h=2,floor((u+1)/2),
    
14.             c[1]=1/u+(h-1)/u*a[k,h-1]+(u-h)/u*a[k,u-h];
    
15.             if(c[1]>b[1], next());
    
16.             for(v=2,k,
    
17.                 c[v]=(h-1)/u*a[v-1,h-1]+(u-h)/u*a[v-1,u-h]
    
18.             );
    
19.            p=0;
    
20.            if(c[1]<b[1],p=1);
    
21.            for(v=2,k,
    
22.                if(c[v]<b[v],break());
    
23.                if(c[v]>b[v],p=1;break())
    
24.            );
    
25.            if(p,
    
26.                 for(v=1,k,b[v]=c[v]);d[u]=h
    
27.            )
    
28.         );
    
29.         for(v=1,k,a[v,u]=b[v])
    
30.    );
    
31.   [a,d]
    
32. }

复制代码

输入参数k表示人数,n代表数字数目，比如sor(100,3)就给出了100个数3个人时的结果。输出结果中a是k个人的输的概率。d给出了编号最小的最优选择策略。