鸽巢原理(p igeonhole principle 鸽巢原理( pigeonhole principle):若把n+1 只鸽子装进n只鸽巢,则至少有一只鸽巢 装2只以上的鸽子 又名抽屉原则 Dirichlet drawer principle) Peter Gustav Lejeune Dirichlet, 1805-1859) 推广形式:若把m件物品装进k只抽屉,则 至少有一只抽屉装只以上的物 「18=2,.1.8}=1,「-18-1,-18=2 《集合论与图论》第7讲 13《集合论与图论》第7讲 13 鸽巢原理(pigeonhole principle) 鸽巢原理(pigeonhole principle): 若把n+1 只鸽子装进n只鸽巢, 则至少有一只鸽巢 装2只以上的鸽子. 又名抽屉原则(Dirichlet drawer principle), (Peter Gustav Lejeune Dirichlet,1805~1859) 推广形式: 若把m件物品装进k只抽屉, 则 至少有一只抽屉装 只以上的物品. ⎡1.8⎤=2, ⎣1.8⎦=1, ⎡-1.8⎤=-1, ⎣-1.8⎦=-2. ⎥⎥⎤ ⎢⎢⎡ km