抽屉原理

1834年狄利克雷提出的原理
image
抽屉原理（Pigeonhole principle[2]）也称鸽巢原理、重叠原理[1]或狄利克雷抽屉原理[2]，是一个初等且应用广泛的数学原理，同时也是组合数学中一个重要的原理。[1]抽屉原理的一般含义为：如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。[5]抽屉原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数。[1]
该原理是1834年狄利克雷提出的。[3]1846年，他使用抽屉原理阐明代数数域中单位数的阿坝尔群结构。[6]1930年，英国逻辑学家弗兰克·P·拉姆（F.P.Ramsey）将这个简单原理作了深刻推广，从而获得拉姆齐定理，该定理也被称为广义抽屉原理。[7]
抽屉原理通常用在整除问题、面积问题以及染色问题上。研究与整除有关的问题时， 常用剩余类作为抽屉；在面积问题上例如已知在边长为1的等边三角形内(包括边界)有任意10个点。证明至少有两个点之间的距离不大于1/3；染色问题如例如：将平面上每点都任意地染上黑白两色之一。求证： 一定存在一个边长为1或3的正三角形，它的三个顶点同色。[8]

定义

抽屉原理又称鸽巢原理或重叠原理，是组合数学中基本原理之一，[7]其定义为一般情况下，把n+1或多于n+1个苹果放到n个抽屉里，其中必定至少有一个抽屉里至少有两个苹果。人们称这种现象为抽屉原理。例如桌上有十个苹果，要把这十个苹果放到九个抽屉里，不限制每个抽屉中放置的苹果个数， 如有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终会发现至少可以找到一个抽屉里面至少放两个苹果。[5]该原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。[7]