|
|
知识路径： > 应用数学 > 组合分析 > 组合分析 >
|
|
相关知识点：4个
|
|
|
|
|
鸽巢原理（抽屉原理，鸽笼原理）的简单形式定义如下：
|
|
|
|
若n+1个物体（鸽子）被放进n个盒子（巢）中，则至少有一个盒子（巢）将存有2个或2个以上的物体（鸽子）。
|
|
|
|
例如，13个人中必有至少两个人的生日是在同一个月中。
|
|
|
|
鸽巢原理的推广：设k和n都是任意的正整数。若至少有kn+1个物体被放进n个盒子中，则至少存在一个盒子中有至少k+1个物体。
|
|
|
推论1：m个物体，n个盒子，则至少有一个盒子里有不少于 个物体。
|
|
|
|
推论2：若取n(m-1)+1个球放进n个盒子，则至少有1个盒子有m个球。
|
|
|
|
鸽巢原理的强形式定义：设有p1+p2+…+pn个物体，有标号分别为1，2，…，n的盒子，则存在至少一个标号为j的盒子至少有pj个物体，j=1，2，…，n。
|
|
|
|
例子1：在一个水果篮中放入苹果、香蕉和橘子。那么需要在一个水果篮中最少放多少个水果，才能保证水果篮中至少有8个苹果或6个香蕉或9个橘子。
|
|
|
|
解：依据鸽巢原理的强形式定义，应该为8+6+9-3+1=21个水果。
|
|
|
|
例子2：在一个袋中有100个苹果，100个香蕉，100个橘子和100个生梨。如果现每分钟从袋中拿出一个水果，请问需要多久时间才能确保从袋中已取出12个同一种类的水果。
|
|
|
|
解：根据鸽巢原理，应该取n=4（有4种类型的水果），k+1=12，k=11，从而kn+1= 11×4+1=45。即需要45分钟时间就能确保从袋中取出12个同一种类水果。
|
|
|
