阿里巴巴全球数学竞赛的奖金总额约为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。
评论列表