数学研发论坛

 找回密码
 欢迎注册
查看: 431|回复: 16

[原创] 【报数拆区间】游戏的最佳策略

[复制链接]
发表于 2019-3-6 15:35:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

游戏开始前,由随机数发生器产生一个$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$。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-7 15:29:29 | 显示全部楼层
为啥是100个数而不限制玩家数量
比如如果有101个玩家呢(……)

点评

人越多这个题(a.s.)越好做,比如当人数多于数字数两倍的时候,每个人都是掷骰子选择到底是报最小的数还是报最大的数  发表于 2019-3-7 18:34
电视节目上玩的就是$100$个数。这么多玩家搞不动的吧?一开始最好先研究$2$个玩家吧?  发表于 2019-3-7 16:14
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 13:49:06 | 显示全部楼层
两个玩家应该还是挺简单的,稍微多一些玩家就会比较复杂了。
但是我觉得很有可能每次挑选最中间就可以了,思路很简单,尽快结束游戏,降低下一轮还轮到自己的概率。当然在无法改变命运时,开始会为了欺负紧跟着自己的小弟而选择边上的数字了。
比如两个人,可以简单逆推。由于这时遇到多种方案概率相等时,怎么选择都不影响最终结果,所以
如果面对的区间只有一个数字了,那就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}$,而如果要证明结论,也很简单,数学归纳法即可
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 14:14:32 | 显示全部楼层
三个玩家玩游戏时,除了计算各种方案下当前玩家输掉的概率,还需要记录其它玩家输掉的概率,所以计算相对要复杂一些。
如果只有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。前提是相信无论你如何迫害小弟,他还是爱你依旧。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 14:35:59 | 显示全部楼层
mathe 发表于 2019-3-11 14:14
三个玩家玩游戏时,除了计算各种方案下当前玩家输掉的概率,还需要记录其它玩家输掉的概率,所以计算相对要 ...

三个人情况前面算错了,结果很复杂,没有明显的规律
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 15:49:25 | 显示全部楼层
改一下游戏规则
猜到与裁判一样的数为赢家
不管裁判的数多大,至多猜10次,就可以猜中裁判的数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 20:04:57 | 显示全部楼层
mathe 发表于 2019-3-11 14:35
三个人情况前面算错了,结果很复杂,没有明显的规律

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

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

……果然好麻烦
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-12 08:13:55 | 显示全部楼层
两个玩家时选择方案给的不正确。
事实上两个玩家时,面对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$时,那么去掉一个后,怎么选择都结果一样。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-12 08:35:24 | 显示全部楼层
但是切换到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完全不能相比
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-12 08:40:58 | 显示全部楼层
  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给出了编号最小的最优选择策略。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-5-24 07:45 , Processed in 0.058619 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表