下载文档原格式
第1章 鸽巢原理鸽巢原理（又叫抽屉原理）指的是一件简单明了的事实：为数众多的一群鸽子飞进不多的巢穴里，则至少有一个巢穴飞进了两只或更多的鸽子。
这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问题，得到一些很重要的结论，它在数学的历史上起了很重要的作用。
1.1 鸽巢原理的简单形式 鸽巢原理的简单形式可以描述为：定理1.1.1 如果把1n +个物品放入n 个盒子中，那么至少有一个盒子中有两个或更多的物品。
证明 如果每个盒子中至多有一个物品，那么n 个盒子中至多有n 个物品，而我们共有1n +个物品，矛盾。
故定理成立。
鸽巢原理只断言存在一个盒子，该盒中有两个或两个以上的物品，但它并没有指出是哪个盒子，要想知道是哪一个盒子，则只能逐个检查这些盒子。
所以，这个原理只能用来证明某种安排的存在性，而对于找出这种安排却毫无帮助。
例1 共有12个属相，今有13个人，则必有两人的属相相同。
例2 在边长为1的正方形内任取5。
证明 把边长为1的正方形分成4个边长为12的小正方形，如图1.1.1所示，在大正方形内任取5点，则这5点分别落在4个小正方形中。
由鸽巢原理知，至少有两点落在某一个小正方形中，从而这两点间的距离小于或等于小正方形对角线的长度2。
例3 给出m 个整数12,,,m a a a ，证明：必存在整数,(0)k l k l m ≤<≤，使得()12k k t m a a a +++++证明 构造部分和序列1121212,,m m s a s a a s a a a ==+=+++则有如下两种可能：（i ）存在整数(1)h h m ≤≤，使得h m s ，此时，取0,k l h ==即满足题意。
（ii ）对任一整数i ，均有(1)i m s i m ≤≤，令(m o d )i i r s m =，则有11(1)i r m i m ≤≤-≤≤，这样，m 个余数均在1到m-1之间。
鸽巢问题知识点总结一、概述鸽巢问题是一类经典的组合数学问题，它通常涉及到将若干个物体放入若干个容器中，保证容器内物体数量不超过规定值的情况下，求出最多可以放置多少个物体。
鸽巢问题有着广泛的应用，例如在密码学、计算机科学、图论等领域都有着重要的应用。
二、基本概念1. 鸽巢原理：若将n+1个或更多的物体放入n个盒子中，则至少有一个盒子内有两个或以上的物体。
2. 抽屉原理：如果有m个物品放进n个抽屉里，且m>n，则至少有一个抽屉里面至少有两个物品。
3. 完全背包问题：在给定的一组物品和一个容量为V的背包中，每种物品都有无限件可用。
装入背包中的物品总价值最大是多少？4. 01背包问题：在给定的一组物品和一个容量为V的背包中，每种物品只能选择一件。
装入背包中的物品总价值最大是多少？三、解题思路1. 鸽巢原理解题思路：（1）确定鸽子和鸽巢：将物体视为鸽子，容器视为鸽巢。
（2）确定限制条件：设每个鸽巢最多可以放置k个鸽子。
（3）确定问题：求出最多可以放置多少个物体。
（4）应用鸽巢原理：根据鸽巢原理，当物体数量大于nk时，至少有一个容器内放置了两个或以上的物体。
因此，最多可以放置的物体数量为nk。
2. 抽屉原理解题思路：（1）确定抽屉和物品：将容器视为抽屉，将物体视为物品。
（2）确定限制条件：设每个抽屉最多可以放置k个物品。
（3）确定问题：求出最多可以放置多少个物品。
（4）应用抽屉原理：根据抽屉原理，当物品数量大于nk时，至少有一个抽屉内放置了两个或以上的物品。
因此，最多可以放置的物品数量为nk。
3. 完全背包问题解题思路：（1）初始化状态：设f[i]表示前i件物品恰好装满容量为j的背包所能获得的最大价值，则f[0]=0。
（2）状态转移方程：f[i][j]=max{f[i-1][j-k*V[i]]+k*W[i]|0<=k*V[i]<=j}。
（3）求解最优解：最终的最大价值为f[n][V]。
4. 01背包问题解题思路：（1）初始化状态：设f[i][j]表示前i件物品恰好装满容量为j的背包所能获得的最大价值，则f[0][0]=0。
