【水】鸽巢原理

鸽巢原理是这样叙述的：如果有k个鸽巢，多于k只鸽子，每只鸽子在一个鸽巢内，那么必有一个鸽巢内至少有两只鸽子。或者跟普遍地说，对于k个巢，n只鸽，那么必有鸽巢至少有\(\left\lfloor \frac{\text{n}}{k} \right\rfloor \)另一些鸽巢必定至多有\(\left\lfloor \frac{\text{n}}{k} \right\rfloor \)只鸽子。其实它有大家更为耳熟能详的一个名字：抽屉原理。它虽然简单，但是可以创造性地用来证明一些意想不到的复杂结果。用它处理问题的时候需要明确哪些对象代表鸽子，哪些对象代表巢。

例题一：假设有n个人参加一次会议，有些人与另一些人握手，证明至少有两个人与同样多个人握手。

解：

每个人的握手次数及他和对方握手的人数必在0、1、.....n-1的范围之内，人就是鸽子，握手次数就是巢。是否可能将每个巢都占有呢？或者说有一个人握0次手，却有一个人和参加会议的除他以外的每一个人都握手，这就产生了矛盾，所以必定至少有一个巢没有被占有。现在有n只鸽子，n-1个巢，所以必有两只鸽子在一个巢里，也就是说至少有两个人的握手次数相同，得证。

例题二：证明存在每个由4个数字组成的数列，有无穷多次出现在2的幂的前4位数字中。（除掉零开头的）

证：假设对每一个由4个数字组成的数列构造一个集合，把2的幂的前4位分类放入集合内，前9个幂不放入集合内，因为2的幂有无穷多个，所以有一些集合必容纳无穷多个2的幂。对于这个集合的由4个数字组成的数列，有无穷多次出现在2的幂的前4位数字中。

例题三：给出一个由1985个不同的正整数组成的集合M，其中任何一个都没有大于23的质约数。证明M含有一个由4个元素组成的子集，这4个元素的积是一个整数的4次幂。

证明：因为集合大写的m中没有元素大于23的制约数，所以每一个元素都可以写成以下形式。对于一些整数\({{\alpha }_{\text{i}}}\)>=0，有

\[{{2}^{{{\alpha }_{1}}}}{{3}^{{{\alpha }_{2}}}}{{5}^{{{\alpha }_{3}}}}{{7}^{{{\alpha }_{4}}}}{{11}^{{{\alpha }_{5}}}}{{13}^{{{\alpha }_{6}}}}{{17}^{{{\alpha }_{7}}}}{{19}^{{{\alpha }_{8}}}}{{23}^{{{\alpha }_{9}}}}\]

需要注意，如果两个数的质因数分解式中的每一个质因数的质数的奇偶性都相同，那么他们的积是完全平方数。因为对9个指数中的每一个数都有积或偶这两种可能，所以奇偶性共有2的9次方等于512种不同的分布。

根据鸽巢原理，因为有1985个不同的整数以及有512种既有型的分布情况，所以必定至少有两个数的奇偶性的分布相同。除这两个数以外，还有1983个不同的整数，再利用鸽巢原理找出另一些对奇偶性的分布相同的数。不必与第一对数的奇偶性的分布相同，这一过程我们可以重复513次，此时我们已经排除了这1985个数中的1026个数，还多出959个数，因为还比512多，所以在这种情况下还可以利用鸽巢原理。

现在有513对乘积是完全平方数的数。考虑这513个完全平方数，我们考察这些数的质因数分解式中各指数除以4的余数，因为这些数都是完全平方数，所以余数只可能是0和2，注意与前面的基偶性情况一样，如果两个完全平方数有同样的余数分布，那么这两个完全平方数的积是一个整数的4次方，因为我们有513个完全平方数以及有512种余数的分布情况，根据鸽巢原理必定有两个完全平方数有同样的余数分布。

从原来的集合M中取出这两个数乘以我们乘到完全平方数的两个数，就得到完全4次幂，于是我们就有一个含有4个元素的子集，他们的积是一个整数的4次幂。

注：例题有其他解法。

最重要的还是把握好对象特点，对应好鸽和巢，比较抽象，但很有意思。