定理. 如果 $N$ 个球被放入到 $M=N^2$ 个箱子中, 则"没有箱子装有多于1个球"的概率大于 $\frac{1}{2}$.
设有 $M=N^2$ 个箱子, $B_1, B_2,\ldots, B_M$. 将 $N$ 个球 $b_1,b_2,\ldots, b_N$ 放入这些箱子中.
$m_i$ 表示箱子 $B_i$ 所含球的个数. 此定理表明
\[
P(m_i\leqslant 1, \forall\ i=1,2,\ldots,N^2) > \frac{1}{2}.
\]
参考自 [1] P.171
[1] Mark Allen Weiss 著 《数据结构与算法分析》—— C++语言描述（第四版）
1
设函数 $f: \{1,2,\ldots,N\}\rightarrow\{1,2,\ldots,M\}$ 是记录球放在哪个箱子的函数. $f(i)=k$ 表示将第 $i$ 个球放入箱子 $B_k$ 中.
如果 $f(i)=f(j)$, 则表明球 $b_i$ 和 $b_j$ 放入了同一个箱子. 如果 $f$ 是散列函数, 则称此时发生了冲突. 当 $M=N^2$ 时, 可以绘制一个 $N$ 阶方阵 $A=(a_{ij})_{N\times N}$. 若 $f(i)=f(j)$, 则将 $a_{ij}$ 置为 1, 否则置为 0. 于是任意两个球放在同一箱子中(发生冲突)的概率为 $\frac{1}{M}$.
\[
\sum_{i < j}\frac{1}{M}=\frac{1}{M}\cdot\frac{N(N-1)}{2}=\frac{N(N-1)}{2N^2} < \frac{1}{2}.
\]
因此, 不发生冲突的概率大于等于 $\frac{1}{2}$.