如果 $N$ 个球被放入到 $M=N^2$ 个箱子中, 则"没有箱子装有多于1个球"的概率大于 $\frac{1}{2}$.
定理. 如果 $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++语言描述（第四版）