项目概述#

• 起因
• 问题背景
• 数学方法计算
• 程序模拟计算
• 补充
• 总结
• 拓展

起因#

事情是这样的。

高一的时候，英语还没有积累太多，经常在阅读限时训练中做不到最后一篇七选五。

其中有一次，我破罐子破摔，直接蒙了五个上去。

结果如图所示：

我悲从中来，不禁思考，我，竟然如此倒霉吗？一个都没有蒙对。

于是，我展开了对此的计算。

问题背景#

为了得到一个通性的计算方式，我们将问题一般化为：对于一道 $m$ 选 $n$ 的英语阅读题，随机选择互不相同的选项填上去，答案对 $k$ 个的概率是多少？ $(0 \le k \le n, 1 < n \le m)$

例如，对于一道七选五，你的答案可以填： $EDCBA$ 、 $CFDEA$ 、 $BGDFC$ ……

为了方便说明，我们不妨假设正确答案为 $ABCDE$ 。

数学方法计算#

首先，对于对 $k$ 个的情况，不难想到分步乘法，先在 $n$ 个空里选出 $k$ 个是填对的，也就是 $C_n^k$ ，然后剩余 $(n-k)$ 个都是错的。

对于剩余填错的那些空，正面计算显然不太容易，于是正难则反。

假设对于这 $(n-k)$ 个空和剩下的 $(m-k)$ 个选项，猜对 $X$ 个空对应的方案数为 $cnt(X)$ ；选择 $X$ 个空填对、剩下乱填对应的方案数为 $pre(X)$ ，则：

我们需要得到 $cnt(0)$ 。

根据容斥原理，乱填 $(n-k)$ 个的情况数，需要扣掉选一个空填对、剩下 $(n-k-1)$ 个乱填的情况数，但是在 $C_{n-k}^{1} \times A_{m-k-1}^{n-k-1}$ 的计算过程中，对于每一次“选一个填对”的操作，不同的这些操作之间包含的情况数可能重叠，因为后面的是随便填的。

而重叠的部分，正是那些选两个空填对、剩下 $(n-k-2)$ 个乱填的情况。

但是，这样又会造成一些情况被多扣掉，也就是那些选三个空填对、剩下 $(n-k-3)$ 个乱填的情况，需要加回来。

以此类推，也就是： $cnt(0)=pre(0)-pre(1)+pre(2)-$ ……

最后，我们可以得到：

对于一道 $m$ 选 $n$ ，答案对 $k$ 个的情况数是： $(0 \le k \le n, 1 < n \le m)$

$C_n^k \times \sum_{i=0}^{n-k}[(-1)^i A_{m-k-i}^{n-k-i} C_{n-k}^i]$

用公式计算了七选五的情况及其概率，草稿如下：

这个计算结果可以方便我们对下面的频率估计概率提供参照。

程序模拟计算#

我们知道，当样本足够大的时候，用频率估计概率，可以大致估计出这个问题的答案。

我们又知道，计算机的很多随机数其实是不太均匀的，比如一些以时间刻度为标准的随机数，在密集调取时就会出很大问题。

虽然计算机可能没有完全的随机数，但是我们可以找一个更精确一点的。

我们引入 C++ 的 random 库，使用 uniform_int_distribution 随机整数生成函数。

模拟从 $m$ 个选项选 $n$ 个填入空，然后判断对了几个，同时计数。

程序代码如下：

1
#include<bits/stdc++.h>
2
#include<windows.h>
3
#include<conio.h>
4
#include<random>
5
using namespace std;
6
int n,m,a[102],t;
7
long long T,per,sum,cnt[102];
8
bool v[102];
9
inline int read(){
10
    int x=0,f=0;
11
    char ch=getchar();
12
    while(ch<'0'||ch>'9'){
13
        if(ch=='-') f=1;
14
        ch=getchar();
15
    }
16
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
17
    return f?-x:x;
18
}
19
int main(){
20
    //input
21
    SetConsoleTitle("\"from m choose n\" simulate");
22
    system("color F0");
23
    printf("from m choose n:");m=read(),n=read();
24
    printf("sample size:");T=read();
25
    printf("per step:");per=read();
26
    //random seed
27
    default_random_engine e;
28
    uniform_int_distribution<int> u(1,m);
29
    e.seed(time(0));
30
    //process
31
    while(T-->0){
32
        //init
33
        for(int i=1;i<=m;++i) v[i]=0;
34
        //make data
35
        for(int i=1;i<=n;++i){
36
            t=u(e);
37
            if(v[t]) --i;
38
            else v[t]=1,a[i]=t;
39
        }
40
        //count
41
        t=0;
42
        for(int i=1;i<=n;++i) if(a[i]==i) ++t;
43
        ++cnt[t],++sum;
44
        //print
45
        if(sum%per==0){
46
            system("cls");
47
            printf("from %d choose %d\n",m,n);
48
            printf("total %lld\n",sum);
49
            for(int i=0;i<=n;++i) printf("%d correct %lld %.4lf%%\n",i,cnt[i],(double)cnt[i]*100/sum);
50
//            printf("(press any key to continue)");
51
//            getch();
52
        }
53
    }
54
    //result
55
    system("cls");
56
    printf("#result\n\n");
57
    printf("from %d choose %d\n",m,n);
58
    printf("total %lld\n",sum);
59
    for(int i=0;i<=n;++i) printf("%d correct %lld %.4lf%%\n",i,cnt[i],(double)cnt[i]*100/sum);
60
    printf("\npress any key to end");
61
    getch();
62
    return 0;
63
}

需要输入的数据：

• $m$ -几个选项
• $n$ -几个空
• $T$ -样本大小
• $per$ -每一跳大小

我们取 $m=7,n=5,T=10^8,per=10^5$ ，得到如下模拟结果：

对于生成的概率，我们保留百分数两位小数，可以发现数值一样。

由此我们得出，对于 $10^8$ 的样本大小，这个随机种子产生的结果与真实概率的误差 $\delta < 0.01\%$ ，可接受。

同时我们也双重验证了上述数学计算过程应该没问题。

补充#

在七选五问题中，我们只考虑了填五个不一样的选项。

那如果填五个一样的选项呢？不难发现，全错的概率是 $\frac{2}{7}$ ，对一个的概率是 $\frac{5}{7}$ 。

我们计算一下两种填法的期望，发现期望得分是相同的。

具体原因在此不详细阐释，可自行证明。

总结#

如果你和我有类似的经历，不要灰心，是全部蒙错的概率本来就高达 $48.17\%$ ，甚至全错和对一个的概率加起来，就已经达到 $84.09\%$ ，这并不能证明你运气不好，只能说蒙对还是太难了。

如果你追求稳妥，可以填五个一样的选项，这样至少得分的概率是 $\frac{5}{7}$ ，不至于较大概率没分。

当然，你想搏一搏，也未尝不可，毕竟还有 $0.0397\%$ 的全对概率等着你~

拓展#

有兴趣的话，可以探索一下，填几个相同的选项，得分会比较舒服。

包括但可能不限于：（用同一个数字表示同一个选项）

• 12345（已探究）
• 11111（已探究）
• 12222
• 11222
• 11223
• 11234

如果有其他成果，欢迎发邮件到 juzi75@qq.com 。