摘要
抽屉原理可叙述如下:将n+1个球放入n个盒子中,则至少有一个盒子中装的球数不少于两个。 证明 若每个盒子中最多装一个球,则n个盒子中总共最多只能装n个球,但这n个盒子中共有n+1个球,这是一个矛盾。 抽屉原理还可推广为更一般的形式:设m_1,m_2,…,m_3都是正整数,若将sum from i=1 to n(m_i-(n-1))个球放入n个盒子中,则:第一个盒子中至少放入m_1个球,或第二个盒子中至少放入m_2个球,… ,或第n个盒子中至少放入m_n个球,这n种情形中至少有一种情形必然发生。 证明 若第一个盒子中装的球数少于m_1个,第二个盒子中装的球数少于m_2个,…。
