鸽巢原理
维基百科,自由的 encyclopedia
鸽巢原理,又名狄利克雷抽屉原理、鸽笼原理。
其中一种简单的表述法为:
- 若有n个笼子和n+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少2只鸽子。
另一种为:
- 若有n个笼子和kn+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少k+1只鸽子。
集合论的表述如下:
- 若A是n+1元集,B是n元集,则不存在从A到B的单射。
拉姆齐定理是此原理的推广。
鸽巢原理,又名狄利克雷抽屉原理、鸽笼原理。
其中一种简单的表述法为:
另一种为:
集合论的表述如下:
拉姆齐定理是此原理的推广。