2021年阿里巴巴全球数学竞赛中的一个概率问题, 难出了新高度

阿里巴巴全球数学竞赛的奖金总额约为30万美元。它对任何人开放，并且允许编程。下面是2021年决赛的概率与组合学赛道的第一道题。

问题

一场舞会以20个女孩和22个男孩开始，有无限多的女孩和男孩在外面等待。每轮比赛，从派对中随机挑选一个人。

如果一个女孩被选中，她邀请派对上的一个男孩跳舞，然后他们两个都离开派对。

如果一个男孩被选中，他邀请外面等待的一个女孩和一个男孩跳舞，然后他们三个都留在派对上。

当派对上只剩下（两个）男孩时，派对就结束了。

问：派对永远不会结束的概率是多少？

理解问题

选一个女孩，派对上就会少一对男女；而选择一个男孩时，派对上就会多出一对男女。

这是一个“随机游动”的例子。每轮后，从派对中选中男孩和女孩的概率都会改变。

如果还有2n人，选出一个女孩的概率是：Pr(G) = (n − 1) / (2n)

选出一个男孩的概率是：Pr(B) = (n + 1) / (2n)

我们想要求出派对“永不结束”的概率，可以计算为：

因此，我们的挑战是找出，在有限轮之后派对结束的概率。

一开始，有20个女孩和22个男孩，选出一个女孩的概率是：Pr(G) = 20 / 42

连续选出2个女孩的概率是：Pr(GG) = (20 / 42) × (19 / 40)

连续选出20个女孩的概率是：Pr(GG…G 20 times) = (20 / 42) × (19 / 40) × … (2 / 6)× (1 / 4)

消去连续的分子和分母，我们得到

连续选出20个女孩的概率太小（几乎不可能）。派对也可以在第21回合、30回合或100回合后结束。

我想简化这个问题，希望找到一些规律。

简化问题

首先，研究最简单的情况。假设这个派对只有1个女孩和3个男孩。2轮后，有三个可能的结果：

增加了2对男女

去掉了2对男女

总体上没有变化

让我们看看“没有变化”的概率，从最初的2个女孩和4个男孩开始：

我们发现，这个1/2与剩余人数无关。如果有2n人：

然后，我们可以计算其他两种情况的概率：

好了，现在让我们用这些规则来解决一个简单的问题：2个女孩，4个男孩的聚会结束了。

解决一个简单的情况

假设派对开始时只有2个女孩和4个男孩。所以我们只需要从派对中移除2对男女组合就可以了。

它是一个无穷级数，我假设它是收敛的（否则概率会超过1）。我们试着计算前几项开始，看看会发生什么。

（提醒一下，2n是聚会上剩下的人数。在本例中，我们从n = 3开始）。

下面，我把两个“两轮”分为一组，用“0”表示“没有变化”；“-2”表示“两对男女被移除”；“+2”表示“派对中增加2对男女”

Pr(2，−2)=(1/2)^4这一事实会非常有帮助。你可以用上面的公式进行验证并简化：

到目前为止，我们已经知道：

它看起来就像一个几何级数。我们继续往下看：

其中，3 × Pr(0，2，−2，−2)中的3给无穷级数增加了一些复杂性。之所以会出现这种情况是因为有3个位置可以放置0。

寻找结构

当数字增加时，计算−2和2的排列就变得更加复杂了。看看计算4个“−2”和3个“2”的情况就知道了：

但别忘记，竞赛是允许编程的，这让求解容易了很多。

运行这个程序，我发现只包含−2和2的可能的步数如下：

1，2，5，14，42，132，…

很多人可能不熟悉这个数列，这些被称为加泰罗尼亚数字。我还发现加泰罗尼亚数字有一个简单的生成函数：

其中，C_n是第n个加泰罗尼亚数字。

研究无穷级数

这里有无穷概率级数和加泰罗尼亚数字的关系：

首先，我用上面提到的Pr(0) = 1/2和Pr(2， -2) =(1/2)^4计算单个概率。

现在我们提取出公因式1/12，把它分成几个无穷级数：

黑色级数是无穷几何级数：1 + 1/2 + 1/4 +…，它收敛于2。

粉色，蓝色和橙色的级数都有相同的结构，与加泰罗尼亚数字的生成函数相似，它们都收敛于2。

现在对每一个单独的彩色级数求值，可以应用泰罗尼亚数字的生成函数：

2个女孩，4个男孩的派对在有限轮数后结束的概率正好是1/3。

解决这个“更简单的问题”已经是一个漫长的过程。幸运的是，扩展这个结果以解决最初的问题并不需要太多的工作。

答案

我要解决的下一个问题是，从20个女孩和22个男孩开始，在有限的轮数之后，2对男女被移除的概率。

计算方法与上面相同，只是上面的(1/12)将被(19/84)所代替，(19/84)是n = 21时选择2个女孩的概率。

我们可以用同样的方法计算n=19的情况：

…

然后把这些概率相乘，一直到上面的1/3。因为派对结束的唯一方式就是这些事件连续发生。

消去分子和分母就得到

现在，问题“派对永远不会结束的概率”的答案终于出来了：

答案是：1/21。