生日悖论：为什么 23 个人就有一半概率撞生日

一句话结论

一个 23 人的房间，有两人生日相同的概率是 50.7%。不是直觉告诉你的 183 人。

差别出在：碰撞的机会不是「人数」，而是**「配对数」** $\binom{n}{2} = \frac{n(n-1)}{2}$ 。23 个人两两配对，能配出 253 对 —— 每一对都是一次独立的抽奖机会。

而这个数是按平方增长的。平方进，平方根出，这就是全部秘密。

直觉铺垫：你问错问题了

先看你脑子里那个 183 是怎么来的：一年 365 天，要有五成把握，大概得占掉一半的日子，所以一百八十多人。

这个推理本身没错 —— 但它回答的是另一个问题：

「有没有人和我同一天生日？」

而原题问的是：

「有没有任意两个人同一天生日？」

一字之差，答案差了八倍。

区别在于机会的数量。如果只盯着”我”，你只有 22 次机会（和其他 22 个人各比一次）。但如果允许任意两人相撞，机会就变成了所有配对的数量：

人数	两两配对数	相当于抽多少次奖
3	3	3
10	45	45
23	253	253
50	1225	1225
100	4950	4950

想象一群人进场后互相握手：3 个人握 3 次手，10 个人握 45 次，23 个人握 253 次。人数翻一倍，握手次数翻约四倍。

所以你需要的从来不是”人多到能站满半个日历”，而是”握手次数多到能撞上一次”。253 次机会里撞上一次，听起来就一点也不奇怪了。

推导过程：算反面

直接数”至少有一对撞了”很麻烦（撞 1 对、2 对、3 对……要分类）。标准做法是算反面：

$P(\text{至少一对相同}) = 1 - P(\text{全部都不同})$

第 1 步：全部都不同，是多少？

让 23 个人依次报生日。第 1 个人随便哪天都行（概率 $365/365$ ）；第 2 个人必须避开那 1 天（ $364/365$ ）；第 3 个人要避开前两人的 2 天（ $363/365$ ）……依此类推：

$P(\text{全不同}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365-n+1}{365}$

代入 $n = 23$ ，算出来是 $0.4927$ 。于是：

$P(\text{至少一对相同}) = 1 - 0.4927 = 0.5073$

23 个人，50.7%。

第 2 步：为什么会是平方？

用近似 $\ln(1-x) \approx -x$ （当 $x$ 很小时），对每一项取对数再相加：

$\ln P(\text{全不同}) = \sum_{i=0}^{n-1} \ln\left(1 - \frac{i}{365}\right) \approx -\sum_{i=0}^{n-1} \frac{i}{365} = -\frac{n(n-1)}{2 \cdot 365}$

那个 $n(n-1)/2$ 又出现了 —— 配对数。它坐在指数上，决定了全部。

于是：

$P(\text{至少一对相同}) \approx 1 - e^{-\frac{n(n-1)}{2 \cdot 365}}$

第 3 步：解出临界点

要它等于 $0.5$ ：

$e^{-\frac{n^2}{2 \cdot 365}} = 0.5 \quad\Rightarrow\quad \frac{n^2}{2 \cdot 365} = \ln 2 \quad\Rightarrow\quad n \approx \sqrt{2 \cdot 365 \cdot \ln 2} = 22.49$

取整数就是 23。

第 4 步：把它推广到任意空间

把 365 换成一个通用记号 $d$ （可能的结果总数），同样的推导给出：

$\boxed{n_{50} \approx 1.177\sqrt{d}}$

这条公式叫平方根律。它才是本文真正的主角。

交互演示

同一个公式，换一个 $d$ 就是完全不同的世界。切换下面四个场景，看看需要的次数怎么变：

演示 · 换一个空间大小，看碰撞何时变得几乎必然

抽取次数23

空间大小 d = 365（一年 365 天）· 半数点 = 23 人

碰撞概率

50.7%

两两配对数

253

需要多少次才过半

把空间从生日的 365 放大到 生日的 365（放大了 1 倍），需要抽取的次数只从 23 涨到 23—— 只放大了 1 倍，正好是平方根关系。

必做的一组对照：先停在「生日」看 23 人那个红点，再点「128 位哈希」—— 空间从 365 放大到 $3.4 \times 10^{38}$ （放大了 $10^{36}$ 倍），需要的次数却只从 23 涨到 $2.2 \times 10^{19}$ （只放大了 $10^{18}$ 倍）。正好是平方根关系。

在「生日」场景下点一下「真的随机试 4000 次」，你会看到实测频率死死贴着公式曲线 —— 这不是数学游戏，是真的会发生。

平方根律：这篇真正要讲的东西

$n_{50} \approx 1.177\sqrt{d}$

读法很重要：空间放大 100 倍，破解难度只放大 10 倍。

为什么是平方根？因为机会数是 $\frac{n^2}{2}$ ，要让机会总数达到空间大小 $d$ 的量级，就得有 $n^2 \sim d$ ，于是 $n \sim \sqrt{d}$ 。平方进，平方根出。

它决定了你的密码要设多长

这条公式在计算机安全里是硬的、每天都在用的常识：

空间	大小	五成碰撞所需次数	这意味着
32 位校验和	$4.3 \times 10^9$	77,164	七万多个文件就能撞一次，所以 CRC32 不能当指纹用
128 位哈希	$3.4 \times 10^{38}$	$2.2 \times 10^{19}$	每秒算十亿次，也要约 700 年
256 位哈希	$1.2 \times 10^{77}$	$4.0 \times 10^{38}$	宇宙年龄尺度上都算不完

这里有个几乎所有人都会忽略的细节，也是密码学里最容易被外行搞混的地方：

生日攻击（找到任意两个撞在一起）：成本约 $\sqrt{d}$
原像攻击（撞上某个指定的目标）：成本约 $d$

差整整一个平方根。 所以一个 128 位的哈希函数，它的抗碰撞强度只有 64 位，而不是 128 位。这就是为什么现在的安全标准要求 256 位 —— 你以为买了 256 位的保险，实际拿到的是 128 位的抗碰撞强度，而 128 位才刚好够用。

再往下推一步：多给一个比特，安全边际只涨 $\sqrt{2} \approx 1.41$ 倍。 哈希长度翻倍，攻击成本才涨 $2^{k/2}$ 而不是 $2^k$ 。安全这东西，比你直觉以为的更容易被蚕食 —— 所以位数一开始就得给足。

常见误解

误解一：「23 人里，有 50% 的概率有人和我同一天生日。」 不对。那是另一个问题，需要 253 人 才有五成把握（ $1 - (364/365)^{252} \approx 0.5$ ）。概率从来不站在”你”这一边 —— 它站在”任意两个人”那一边。

误解二：「概率就是 $23/365 \approx 6.3\%$ 。」 这是”某个特定的人和别人撞”的量级，混淆了”一个人有 22 次机会”和”253 对里任意一对撞”。数量级差了一个平方。

误解三：「生日不是均匀分布的（春秋出生多），所以 23 这个数不准。」 方向说反了。不均匀只会让碰撞更早发生，真实的 $n_{50}$ 比 23 还略小一点。均匀分布其实是”最不容易撞”的排布 —— 一旦有扎堆，撞得更快。所以 23 是个保守估计，不是乐观估计。

误解四：「100 个人，那肯定有两人同一天。」 几乎是必然，但不是逻辑必然： $99.99997\%$ 。要到 366 人才是 $100\%$ —— 那是鸽巢原理给的硬保证，不是概率给的。“几乎一定”和”一定”之间有条真实的鸿沟，概率从不跨越它。

误解五：「哈希会碰撞，所以哈希不安全。」 碰撞必然存在（输入无穷、输出有限，鸽巢原理），但关键是找不找得到。128 位哈希的碰撞在数学上多如牛毛，可你要在 $10^{19}$ 次尝试里才碰上一次 —— 存在性和可达性是两回事。安全性是个关于”成本”的概念，不是关于”存在”的。

延伸引用

计算 · 哈希（本站）—— 为什么改一个字母会得到完全不同的乱码：那里讲”不可逆”是怎么设计的，这里讲”碰撞”为什么不可避免。两篇合起来才是完整的哈希图像。
数学 · 鸽巢原理（待写）：确定性保证与概率保证的分界线 —— 366 人 vs 23 人，正是这条线两侧的两种真理。
横切原理 · 平方根律（待写）： $\sqrt{N}$ 是独立随机量叠加后的 universal 尺度。醉汉走 $N$ 步，离起点的期望距离是 $\sqrt{N}$ 而不是 $N$ ；做 $N$ 次独立测量，误差按 $\sqrt{N}$ 收敛而不是 $N$ ；布朗运动的位移、气体分子的涨落、这里生日攻击的成本 —— 同一条曲线，在完全不同的学科里反复出现。这是本站后面会专门拆的一条横切原理。