上周很火的100枚硬币问题~

majer

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

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

2. 两个人中先连续看到两个正面的人获胜（ 翻开一个正面后，下一次翻开的必须还是正面，才算数)。
再问：谁的赢面大：

mathe

我们可以先查看前几个硬币状态。
比如如果硬币1是正面，那么
如果硬币2、3至少有一枚是正面，很容易分析，三种情况打平
但是如果2、3都是反面，显然后面对小红有利；所以可以猜测，小红应该占优。

mathe

具体分析，如果奇数位前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$，所以小红赢的概率更大。

mathe

有了理论分析后可以再来一个模拟程序验证一下

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. #define N 100
   
5. char a[N];
   
6. 
   
7. void genrand()
   
8. {
   
9.     int i;
   
10.     for(i=0;i<N;i++){
    
11.         a[i]=rand()&1;
    
12.     }
    
13. }
    
14. 
    
15. #define SIMTIME 1000000
    
16. int main()
    
17. {
    
18.     int i,j;
    
19.     int cc0=0,cc1=0;
    
20.     srand(time(NULL));
    
21.     for(i=0;i<SIMTIME;i++){
    
22.         genrand();
    
23.         int c0=0,c1=0;
    
24.         for(j=0;j<N/2;j++){
    
25.             if(a[j]==1)c0++;
    
26.             if(a[2*j]==1)c1++;
    
27.             if(c0==2||c1==2){
    
28.                     break;
    
29.             }
    
30.         }
    
31.         if(c0==2&&c1==2){
    
32.                 cc1++;
    
33.         }else if(c0==2){
    
34.                 cc0++;
    
35.         }
    
36.     }
    
37.     printf("Win rate %f, equal rate %f\n",(double)cc0/SIMTIME,(double)cc1/SIMTIME);
    
38.     return 0;
    
39. }
    

复制代码

输出结果
Win rate 0.311646, equal rate 0.271073
和理论基本基本匹配，所以应该没有问题了

yigo

对于小明来说，标号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大时，小明输，另外两种情况，小美可能有其他标号更靠前。

yigo

前面的思路虽然错了，但是我根据以上思路构造出一个题目：
把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。
还有更好的策略吗，使得赢的概率比输的概率更大。

yigo

我来尝试下第二问：出现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没找到这个序列)
---------------------------------------------------------

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

图

yigo

查了下，满足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)

yigo

所以平局的概率为：
\(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开始。

yigo

现在来求小明赢的概率，有了计算平局的经验，赢的概率类似处理，比较容易了，
小明在(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}\)

图