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

[分享] 上周很火的100枚硬币问题~

[复制链接]
发表于 2024-9-16 15:56:05 | 显示全部楼层 |阅读模式

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

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

×
小美连续抛100枚硬币,硬币标号从1到100。每一枚硬币落地后,就用一个不透明的盅扣在硬币上。
全部抛完并盖好后,就让小明和小红按特定顺序查看并记录硬币的正反:
小明是按 1、2、3、…、100的顺序揭开一个个盅,而小红先检查奇数号的硬币,然后检查偶数号码的硬币,即按1、3、5、…、99、2、4、6、…、100的顺序。
下文所谓先后,指的是在记录中出现的位置。

1. 两个人中先看到 2 个正面的人获胜( 注意,不是连续两个正面,是看到第一个正面后,不论中间连续多少反面,只要再看到第二个正面就算)。
问:谁的赢面大:

2. 两个人中先连续看到两个正面的人获胜( 翻开一个正面后,下一次翻开的必须还是正面,才算数)。
再问:谁的赢面大:
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-16 17:00:27 | 显示全部楼层
我们可以先查看前几个硬币状态。
比如如果硬币1是正面,那么
如果硬币2、3至少有一枚是正面,很容易分析,三种情况打平
但是如果2、3都是反面,显然后面对小红有利;所以可以猜测,小红应该占优。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-16 17:32:46 | 显示全部楼层
具体分析,如果奇数位前m枚硬币中至少有两枚硬币朝上,那么游戏必然在不超过m轮前结束。

所以我们可以对硬币状态进行分类,其中2k+1位置硬币朝上,1,3,5,...,2k-1位置有且只有一枚硬币朝上的分类记为S(2k+1,d), d=1,3,5,...,2k-1
容易计算这些分类的概率都为$1/{2^{k+1}}$。

另外我们知道对于所有的S(2k+1,d)中,如果前k枚硬币中至少有两枚朝上,小明赢;前k枚硬币中正好1枚朝上,第k+1枚硬币朝上,平;其余小红赢。
为方便起见,记$h=\floor{k/2}$。前k个位置中偶数位置正好h个,奇数位置k-h个。

当然余下还有所有50枚奇数位硬币种正面数目不超过1枚的情况,由于概率过低,我们直接忽略,可以不予计算。

在$d\le k$时,前k枚至少两枚朝上,前k枚偶数位置有$h$个,要求偶数位至少一枚朝上,所以前k枚至少两枚硬币朝上概率为$1-{C_h^0}/2^h=1-1/2^h$;
    前k枚奇数位已经正好一枚朝上,然后第k+1枚朝上概率,在k为偶数时为0,k为奇数时是 ${C_h^0}/2^{1+h}=1/2^{1+h}$,对应双方平; 余下情况小红赢。

而在$d=k+1$时(这时k必然为偶数), 那么前k枚有两枚以上正面概率为$1-(C_h^0+C_h^1)/2^h$,对应小明赢的概率;前k枚正好一枚正面朝上概率为${C_h^1}/2^h$,对应俩人平;其余小红赢。
而在$d>k+1$时,前k枚两枚以上正面概率为$1-(C_h^0+C_h^1)/2^h$,对应小明赢;而前k枚正好一枚正面朝上,而且k+1枚正面朝上,这在k为偶数时概率为0,k为奇数时,概率${C_h^1}/{2^{1+h}}$,对应俩人平;余下情况小红赢。

所以总结下来,对于所有的d,总是有概率$1-(C_h^0+C_h^1)/2^h$小明赢,而$d\le k$时,小明还有额外${C_h^1}/2^h$的概率赢。
所以小明赢的概率为
$\sum_{k=1,h=\floor{k/2}}^{49} ((1-(1+h)/2^h)k + (k-h)h/{2^h})/{2^{k+1}} \approx  0.3119533527696340032076354136$.
双方平的概率为
$\sum_{h=1,k=2h}^25 (h/2^h)/2^{k+1} +\sum_{h=0,k=2h+1}^24 ((k-h)/2^{1+h} + h^2/2^{h+1})/{2^{k+1}} \approx 0.2711370262390670553910466433$
于是小红赢的概率大概为$0.4169096209912989414013179431$,所以小红赢的概率更大。

点评

当硬币无限多的时候,平局的概率是93/343,100数字时,算出来是10243267239810542387617/37778931862957161709568≈0.271137,与你的式子完全一致,也是忽略了小概率  发表于 2024-9-21 01:10
这么聪明的人,幸福感应该很强吧!  发表于 2024-9-18 23:45
静下心来,终于看懂了,这么细腻的划分,没有遗漏,没有混乱,真神人!  发表于 2024-9-18 23:33
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-17 11:27:51 | 显示全部楼层
有了理论分析后可以再来一个模拟程序验证一下
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #define N 100
  5. char a[N];

  6. void genrand()
  7. {
  8.     int i;
  9.     for(i=0;i<N;i++){
  10.         a[i]=rand()&1;
  11.     }
  12. }

  13. #define SIMTIME 1000000
  14. int main()
  15. {
  16.     int i,j;
  17.     int cc0=0,cc1=0;
  18.     srand(time(NULL));
  19.     for(i=0;i<SIMTIME;i++){
  20.         genrand();
  21.         int c0=0,c1=0;
  22.         for(j=0;j<N/2;j++){
  23.             if(a[j]==1)c0++;
  24.             if(a[2*j]==1)c1++;
  25.             if(c0==2||c1==2){
  26.                     break;
  27.             }
  28.         }
  29.         if(c0==2&&c1==2){
  30.                 cc1++;
  31.         }else if(c0==2){
  32.                 cc0++;
  33.         }
  34.     }
  35.     printf("Win rate %f, equal rate %f\n",(double)cc0/SIMTIME,(double)cc1/SIMTIME);
  36.     return 0;
  37. }
复制代码

输出结果
Win rate 0.311646, equal rate 0.271073
和理论基本基本匹配,所以应该没有问题了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-18 18:45:11 | 显示全部楼层
本帖最后由 yigo 于 2024-9-18 19:00 编辑

对于小明来说,标号i的位置就是i,对于小美来说,标号i的位置用数列b(i)表示,i为奇数时,b(i)=(i+1)/2,i为偶数时,b(i)=50+i/2。
对于正面出现2次以下的,是平局,对于正面出现2次及以上的,设标号前两个依次为i,j,i<j,比较j和Max(b(i),b(j))的大小,j小则小明赢,相等则平,j大则小美赢,i,j的对数是C(100,2)=100*99/2,回去Excel拉一下,看结果如何,不知道理解的对不对。
-----------------------------
好像不太对,小美的前2个正面与小明的并不是对应的。
这只能说明j大时,小明输,另外两种情况,小美可能有其他标号更靠前。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-18 22:28:11 | 显示全部楼层
本帖最后由 yigo 于 2024-9-18 22:30 编辑

前面的思路虽然错了,但是我根据以上思路构造出一个题目:
把98个白球和2个红球随机分别装进100盲盒里(每个盲盒装一个球),给这100个盲盒从1编号到100,甲乙两人各自给盲盒选定一个开盒顺序,哪方先把2个红球开出来,哪方就赢了,如果第二个红球同时开出来就平局,假如乙知道了甲的开盒顺序,乙有没有什么策略,使得自己的开盒顺序的赢的概率更高。
因为甲的开盒顺序是随机的,那么可以把甲的开盒顺序编为1,3,5,...,49,50,52,54,...,100(若甲编号为1,2,3,4,5,...,100);此时乙的开盒顺序可定为1,2,3,4,5,...,100(则乙编号为1,51,2,52,3,53,...,50,100),则乙赢的概率为3002/4950,平的概率为124/4950,输的概率为1824/4950。
还有更好的策略吗,使得赢的概率比输的概率更大。

点评

别人告诉我,乙的排序,把1放在最后即可,即2,3,4,...,100,1,这样有98%的概率赢。  发表于 2024-9-20 17:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-20 15:22:23 | 显示全部楼层
本帖最后由 yigo 于 2024-9-20 23:21 编辑

我来尝试下第二问:出现2个连续正面的,先分析下平局的概率,与mathe的分析类似,去掉一部分小概率事件,由于硬币的数量很大,可以假定为无限硬币,序列可以转为:
小明:1,2,3,4,5...自然数顺序
小美:1,3,5,7,9...奇数顺序
如果小明和小美在(n,n+1)位出现平局的可能情况,n=1,2时,可以出现平局,n=3,4时不能出现平局,比如n=3,则小美的号码(5,7)为正面,那么前面的号码3也是正面,导致小美出现的连续正面号码为(3,5),
n=4的情况类似,当n≥5的时候均有满足平局的可能情况。

先给出一些事实,给定m个按1到m顺序排好的硬币,没有两个连续正面的情况数设为A(m),根据递归分析A1=2,A2=3,A(m+2)=A(m+1)+A(m),是斐波那契数列,
设斐波那契数列初值F1=F2=1,则A(m)=F(m+2)。

给定2m个按1到2m顺序排好的硬币,没有两个连续正面,然后从中挑出1,3,5,...2m-1依次排在一起,这个序列里出现连续2个及以上正面的数目为B(m),
B(m+1)=2B(m)+F(2m-1),B1=0,B(m)=F(2m)-2^(m-1) 。(这里有点问题,我再想下)

递推公式应该是B(m+2)=3B(m+1)-B(m)+F(2m),B1=0,B2=1。(A030267)(还是不对,脑袋混乱)

这次肯定对了,B(m+2)=2B(m+1)+B(m)+F(2m+1),B1=0,B2=1。(0,1,4,14,45,138,410没找到这个序列)

则给定2m个按1到2m顺序排好的硬币,没有两个连续正面,然后从中挑出1,3,5,...2m-1依次排在一起,这个序列里也没出现连续2个正面的数目为C(m),
C(m)=A(2m)-B(m)

---------------------------------------------------------
同理,给定2m-1个按1到2m-1顺序排好的硬币,没有两个连续正面,然后从中挑出1,3,5,...2m-1依次排在一起,这个序列里出现连续2个及以上正面的数目为D(m),

D(m+2)=2D(m+1)+D(m)+F(2m),D1=0,D2=1。(0,1,3,10,31,93,272,781没找到这个序列)
---------------------------------------------------------

根据下图看下规律,黄色的是正面,绿色表示必须为反面的位置,两个连续黄色前面的白色格子就是按上述方法计算可能数。

图

点评

难搞的很,估计只能动态规划法求,数值解了,也找不到递归方法  发表于 2024-9-20 19:03
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-21 00:47:06 | 显示全部楼层
本帖最后由 yigo 于 2024-9-21 01:52 编辑

查了下,满足B(m+2)=2B(m+1)+B(m)这个递推式的数叫Pell 数,初始值为0,1的记作P(n),初始值为1,1的记作Q(n) (Pell-Lucas numbers)
上一楼中
B(m)=F(2m+2)-Q(m+2),
则C(m)=A(2m)-B(m)=Q(m+2)
D(m)=F(2m+1)-2P(m+1),
则给定2m-1个按1到2m-1顺序排好的硬币,没有两个连续正面,然后从中挑出1,3,5,...2m-1依次排在一起,这个序列里也没出现连续2个正面的数目为E(m),
E(m)=A(2m-1)-D(m)=2P(m+1)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-21 10:49:19 | 显示全部楼层
本帖最后由 yigo 于 2024-9-21 11:03 编辑

所以平局的概率为:
\(p_2=\frac{1}{2^3}+\frac{1}{2^4}+\frac{F_1(2Q_3+Q_4)}{2^{10}}+\frac{F_2(2Q_4+Q_5)}{2^{13}}+\frac{F_3(2Q_5+Q_6)}{2^{16}}+...\)

\( =\frac{1}{2^3}+\frac{1}{2^4}+\frac{1}{2^7}\sum_{k=1}^{\infty}\frac{F_k(2Q_{k+2}+Q_{k+3})}{2^{3k}}=\frac{1087}{5218}=0.2083173629743196627\)

后面一堆用处不大,前两项精度就足够了。
对于题目中的100个硬币,求和上限改成23就可以了。

说明下,这个计算里,Pell 数,初始值为P1=0,P2=1的记作P(n),初始值为Q1=0,Q2=1的记作Q(n) (Pell-Lucas numbers),下标是从1开始,不是通常从0开始。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-9-21 13:32:03 | 显示全部楼层
本帖最后由 yigo 于 2024-9-21 14:03 编辑

现在来求小明赢的概率,有了计算平局的经验,赢的概率类似处理,比较容易了,
小明在(n,n+1)位赢可能情况,同样用表格看规律,黄色表示正面,绿色表示必须为反面的位置,
白色表示要根据前面的方法计算可能数的位置,灰色表示不影响结果的位置,
小明赢的概率为:
\(p_1=\frac{F_2(2Q_1+Q_2)}{2^{4}}+\frac{F_3(2Q_2+Q_3)}{2^{7}}+\frac{F_4(2Q_3+Q_4)}{2^{10}}+...\)

\( =\sum_{k=1}^{\infty}\frac{F_{k+1}(2Q_{k}+Q_{k+1})}{2^{3k+1}}=\frac{1777}{5218}\)
小美赢的概率
\(p_3=1-p_1-p_2=\frac{2354}{5218}\)


图
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-10-7 06:56 , Processed in 0.033012 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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