第1章
鸽笼原理

我们如何知道一段计算机程序能产生正确的结果？我们又如何知道一段程序能完整运行？如果我们知道它必然会停下来，那么能预测停止时间是一秒之后、一小时之后还是一天之后吗？直觉地想道：测试。但即使“每一次测试都正常”也不能成为上述问题的严格证明。证明一个论断需要规范的推证过程：从已知为真的一些命题出发，并通过严谨的逻辑推理将这些为真的命题连接到一起。本书的目的就是阐述能够用来推证有关上述计算机程序行为的数学。

计算机科学数学并非什么特殊的领域，而是计算机科学家们所用到的各个数学分支中的相关内容的汇集，甚至有些内容是在计算机科学发展过程中首次发现了其应用价值。因此，这本书包括的内容涉及数理逻辑、图论、计数、数论和离散概率论等。从传统数学课程的角度来看，这些内容相互之间有些风马牛不相及，但它们拥有一个共同的特征：在计算机科学中都有重要的作用，并且都属于 离散数学 （discrete mathematics），也就是说，所涉及的量相互之间是有距离而不是连续的，量可以用符号或者结构（而非数字）来表示。当然，微积分学在计算机科学中也很重要，因为它有助于连续量的推证。但在本书中，我们很少使用积分和求导数。

数学思维最重要的技能之一就是 泛化 （generalization）。例如，下述命题：

不存在边长分别为 1、2 和 6 的三角形

为真，且这个命题非常具体（见图1.1）。长度为1和2的两条边必须分别与长度为6的边的两端相连，但这两条短边的总长度不足以使它们相连构成第三个角。

更为泛化的陈述可以是（见图1.2）：

不存在边长为 a 、 b 、 c 的三角形，其中 a 、 b 、 c 是任意的，且满足 a + b ≤ c 。

第二种形式更为泛化，因为可以通过代入 a =1、 b =2、 c =6来推导出第一种形式。它也涵盖了图中没有展示的情况，即当 a + b = c 时，三个角落在一条直线上的情况。总之，泛化规则具有优势，它不仅陈述了不可能的情况，而且给出了相应的解释，例如，不存在边长为1、2和6的三角形，因为1+2≤6。

因此，我们以泛化的形式表述命题有两个理由。首先，一个命题越泛化则越易于应用，并且应用范围更广泛。其次，对一个泛化的命题更易于捕捉其要点，因为它剔除了不相关且赘述的细节。

例1.1 再来看另一个简单的例子：

Annie、Batul、Charlie、Deja、Evelyn、Fawwaz、Gregoire 和 Hoon 在互相交谈时 ， 发现 Deja 和 Gregoire 都是星期二出生的 。

什么意思呢？当把两个人放在一起时，他们要么在一周内的同一天出生，要么不在。这里能进行泛化。只要至少有八个人，其中就一定有某两个人是在一周的同一天出生的，因为一周只有七天。像例1.1这样的命题一定是真的，只是可能涉及不同的一对名字和不同的一天。所以更泛化的命题如下：

任意八个人中，某两个人一定是在一周的同一天出生的 。

但是，上面的命题泛化得还不够。因为，生日重叠在同一天与什么人和星期几无关，只与有多少人和一周中有多少天相关。同样的情况：当我们把八个茶杯放在七个茶托上时，某个茶托上会放有两个茶杯。事实上，“八”和“七”并没有什么神奇之处，只是其中一个比另一个大。如果一家酒店有1000个房间和1001位客人，某个房间必然至少有两位客人。如何去陈述上述所有示例的基本原理，而又不提及其中任何不相关的细节呢？

首先，我们需要一个新的概念： 集合 （set）是一些事物或 元素 （element）的汇集。属于集合的元素称为集合的 成员 （member）。一个集合的成员是 可区分的 （distinct），换句话说，它们彼此是不相同的。于是，例1.1中提到的人构成一个集合，一周中的星期几构成另一个集合。有时我们显式地列出集合的所有成员，用花括号{}将它们括起来：

P ={Annie,Batul,Charlie,Deja,Evelyn,Fawwaz,Gregoire,Hoon}

D ={星期一，星期二，星期三，星期四，星期五，星期六，星期日}

当列出一个集合的所有元素时，元素的顺序无关紧要——任何顺序都表示同样的集合。我们用 x ∈ X 来表示 x 是集合 X 的成员。例如，Charlie∈ P ，星期四∈ D 。

为了讨论集合，需要有关数的一些基本术语。 整数 （integer）是指数字0、1、2、…，或-1、-2…。 实数 是数轴上的所有数，包括整数以及整数之间的所有数，如 、π等。大于0的数为 正数 ，小于0的数为 负数 ，大于或等于0的数为 非负整数 。

接下来，我们将讨论有穷集，也称有限集。 有穷集 是可以（至少原则上）列出其全部元素的集合，具有为非负整数的 大小 （size）或 基数 （cardinality）。集合 X 的基数表示为| X |。例如，在上述例子中，有| P |=8和| D |=7。因为列出了八个人，并且一周中有七天。一个集合若不是有穷的（例如，整数集合）就是 无穷的 （infinite）。无穷集也有大小——这是个有趣的主题，我们将在第7章再继续讨论。

从一个集合到另一个集合的 函数 （function）是一项规则，该规则将第一个集合的每个成员与第二个集合的唯一一个成员相关联。若 f 是从 X 到 Y 的函数且 x ∈ X ，则 f （ x ）是 Y 的成员并且由函数 f 将其与 x 相关联，我们称 x 是 f 的 自变量 （argument）， f （ x ）是自变量为 x 的函数 f 的 值 （value）。用 f : X → Y 表示 f 是一个从集合 X 到集合 Y 的函数。例如，我们可以用 b : P → D 来表示将八个朋友中的每一个与他或她出生的星期几相关联的函数，比如，若Charlie出生在星期四，则有 b （Charlie）=星期四。

函数 f : X → Y 有时也被称为“从 X 到 Y 的 映射 （mapping）”，或“ f 将元素 x ∈ X 映射到元素 f （ x ）∈ Y ”。（同样，现实中的地图就是将地球表面上的一个点与纸上的一个点相映射。）

最后，我们将例1.1背后的基本原理表述如下。

定理1.2 若有 f : X → Y 并且 X＞Y ，则存在元素 x ₁ ， x ₂ ∈ X ，使得 x ₁ ≠ x ₂ 且 f （ x ₁ ）= f （ x ₂ ）。

定理1.2就是著名的 鸽笼原理 （Pigeonhole principle），因为它以数学的形式表述了这个具有普遍意义的思想：当鸽子数大于鸽笼数且每只鸽子都进入了鸽笼时，某个鸽笼中必有不止一只鸽子。鸽子是集合 X 的成员，鸽笼是集合 Y 的成员（见图1.3）。

我们将在第3章给出鸽笼原理的规范证明，其中我们会详细研究证明的基础技术。现在，我们来深入探讨鸽笼原理的数学语言表述。下面是我们可能会问到的一些问题。

1. X 和 Y 是什么？

它们都是有穷集。为了清晰起见，我们可以用短语“对于任意有穷集 X 和 Y ”作为命题的开始，而只有当 X 和 Y 是集合时， f 是从 X 到 Y 的函数的断言才有意义。此外，根据上下文可知，所讨论的集合是有穷集，因此我们知道如何比较它们的大小。

2. 为什么选择 x ₁ 和 x ₂ 作为集合 X 中元素的名称？

原则上，我们可以选择任意变量名称，如 x 和 y ，但是使用与 X 相关的变量名来命名集合 X 的元素可以表明 x ₁ 和 x ₂ 是集合 X 的成员，而不是集合 Y 的成员。因此使用 x ₁ 和 x ₂ 会使命题更容易理解。

3. 短语“使得 x ₁ ≠ x ₂ ”真的有必要吗？没有它，语句会更简单，并且有无它似乎说法是同样的。

是的，短语是必要的，如果没有它，说法是不一样的。如果我们不指出 x ₁ ≠ x ₂ ，那么 x ₁ 和 x ₂ 可以取同一元素。如果不规定 x ₁ 和 x ₂ 必须是不相同的，这个命题虽然不为假，但是没有任何意义。显然，当 x ₁ = x ₂ 时，有 f ( x ₁ )= f ( x ₂ )。这就如同地球的质量等于距离太阳第三远的行星的质量一样。另一种鸽笼原理的表述是：存在不同的元素 x ₁ ， x ₂ ∈ X ，使得 f ( x ₁ )= f ( x ₂ )。

这里还有一点需要强调。像“存在不同的元素 x ₁ ， x ₂ ∈ X ，具有……性质”的命题并不意味着恰好只有两个元素具有该性质，而是说至少有两个这样的元素使命题为真，元素可能会更多，但肯定不会更少。

数学家们对任何原理总是希望寻找其最泛化的形式，因为这样可以解释更多的事情。例如，同样明显的命题是，我们不能将15只鸽子放在7个鸽笼里，除非某个鸽笼中至少放有3只鸽子——这种情况是无法从鸽笼原理推得的。下面是鸽笼原理更泛化的版本。

定理1.3 扩展鸽笼原理。对于任意有穷集 X 和 Y 以及任意正整数 k ，且 X ＞ kY ，若有 f ： X → Y ，则至少有 k +1个不同的成员 x ₁ ，…， x _{k +1} ∈ X ，使得 f （ x ₁ ）=…= f （ x _{k +1} ）。

鸽笼原理是扩展鸽笼原理中 k =1时的情况。

这里首次使用了 序列 （sequence）表示法：同一变量名带有一定范围的数字下标。在此情况下， x _i （1≤ i ≤ k +1）就构成了一个长度为 k +1的序列。这种表示法非常方便，因为它可以在下标中使用像 k +1这样的代数表达式。类似地，我们可以推断出序列 y ₁ , y ₂ ,…的第2 i 个成员是 y _{2 i} 。

当应用于特定集合 X 和 Y 时，已知 X 和 Y 的大小，便可推出扩展鸽笼原理中参数 k 的最小值。这有助于使计算更精确。

如果 的商是一个整数（即 q 除以 p 没有余数），则称整数 p 整除 （divide）整数 q ，记为 p | q 。用 表示 p 不能整除 q ，例如， 。对于任意实数 x ，我们用 表示小于或等于 x 的最大整数，称为 x 的 下取整 （floor）。例如， 。同样还需要 上取整 （ceiling）的表示方法： 表示大于或等于 x 的最小整数，例如 。

借助于这些符号，我们从“在已知鸽子和鸽笼数的情况下，确定占用同一个鸽笼的最多鸽子数的最小值”的角度重申扩展鸽笼原理。

定理1.4 扩展鸽笼原理（另一个版本）。设 X 和 Y 是任意有穷集，且有 f : X → Y 。则存在 y ∈ Y ，使得 f （ x ）= y ，其中 x 的取值至少为 。

证明 ：设 m =| X |和 n =| Y |。如果 n | m ，那么这是扩展鸽笼原理中 的情况。如果 ，那么这是扩展鸽笼原理中 的情况，因为 是小于 的最大整数。■

泛化的鸽笼原理似乎均以奇妙的方式表述了一些显然的事情。此外，一旦分析出哪些是鸽子哪些是鸽笼，我们就能使用它们去解释大量不同的现象。让我们以 数论 （number theory）（对整数性质的研究）中的应用来结束本章。首先是一些基础知识。

如果 p | q ，那么称 p 为 q 的 因子 （factor）或 除数 （divisor）。

质数 （prime，也称 素数 ）是一个大于1的整数，它只能被自身和1整除。例如，7是质数，因为它只能被7和1整除，但6不是质数，因为6=2×3。注意1本身不是质数。

定理1.5 算术基本定理。一个大于1的整数有且仅有一种形式表示为不同质数（按递增顺序且具有正整数次幂）的乘积。

例1.6 我们将在第4章证明这个定理，此处仅给出它的应用。将一个数 n 质分解（prime decomposition）就是将其表示为唯一的质数乘积形式：

其中 p _i 是递增的质数， e _i 是正整数。例如，180=2 ² ×3 ² ×5 ¹ ，并且不存在其他的质数乘积 等于180，其中 p 1＜ p 2＜…＜ pk ，所有的 pi 都是质数， e _i 都是整数幂。

两个整数 m 和 n 的乘积的质分解是由 m 的质分解与 n 的质分解结合起来的，即 m · n 的每个质因子一定是 m 或者 n 的质因子。

定理1.7 如果 m 、 n 和 p 都是大于1的整数， p 是质数，且 p m · n ，则有 p m 或者 pn 。

证明 ：根据算术基本定理（定理1.5），有且仅有唯一的质分解如下：

其中 p _i 是质数。那么 p 必为 p _i 之一，并且每个 p _i 必然出现在 m 或者 n 的唯一质分解式中。■

在 m · n 的质分解中，质数 p 的幂是其在 m 和 n 的质分解中的幂之和（如果质分解中没有出现 p ，则其幂计算为0）。例如，从乘积18×10=180，可以得到

可以看出，乘积180中2、3和5的幂是它们在两个因子18和10的分解中的幂之和。

有关质数的另一个重要事实是有无穷多个质数。

定理1.8 不存在最大质数（即有任意大的质数）。

“任意大”意味着对于每一个 n >0，都存在一个大于 n 的质数。

证明 ：设 k 取某个值，则我们可以得到至少 k 个质数，设 p ₁ ，…， p _k 为递增的前 k 个质数。（我们可以取 k =3，则有 p ₁ =1、 p ₂ =2、 p ₃ =5。）我们将展示如何找到一个大于 p _k 的质数。由于这个过程可能会无限地重复下去，因此必定会得到无穷多个质数。

例1.9 来看一下比前 k 个质数乘积大1的数 N ：

N =( p ₁ · p ₂ ·…· p _k )+1

N 除以 p ₁ ，…， p _k 中的任何一个数，余数都为1。所以 N 不存在小于或等于 p _k 的质因子。因此，要么 N 不是质数且有一个大于 p _k 的质因子，要么 N 本身就是质数。■

例如，在 k =3的情况下， N =2×3×5+1=31。 N 本身是质数，习题1.11中要求找到一个 N 不是质数的例子。

两个数的 公约数 （common divisor）是能够整除这两个数的数。例如，21和36具有公约数1和3，而16和21没有大于1的公约数。

在上述定理的基础上，我们来举一个鸽笼原理在数论中应用的例子。

例1.10 在2和40之间（包括2和40）选出 m 个不同的数，其中 m ≥13。那么至少存在两个数有大于1的公约数。

“在 a 和 b 之间（包括 a 和 b ）”代表所有≥ a 且≤ b 的数，因此该例中包括2和40。

解 ：首先观察到，有12个质数小于或等于40:2、3、5、7、11、13、17、19、23、29、31、37。其中任意两个数不存在大于1的相同因子（公约数）。定义 P 为这12个质数的集合。（我们需要指定 m ≥13，因为 m =12时该论断为假，集合 P 将是一个反例。）现在考虑具有 m 个数（取值范围为2~40，包括2和40）的集合 X 。将 X 的成员看作鸽子， P 的成员看作鸽笼。将鸽子放到鸽笼中，定义函数 f ： X → P ，其中 f （ x ）是整除 x 的最小质数。例如， f （16）=2、 f （17）=17、 f （21）=3。根据鸽笼原理，由于 m >12，则对于 X 的两个不同成员，必有其 f 的值相等，因此 X 中至少有两个成员有公约数。■

本章小结

• 数学思维侧重于从具体示例的细节中抽象出一般性原理。

• 集合 是 不同 事物或 元素 的无序汇集。集合的元素称为 成员 。

• 一个集合是 有穷集 ， 当且仅当 其所有成员可以逐一列出来。有穷集 X 的成员数称为 基数 或 大小 ，记为“| X |”。一个集合的大小一定是 非负整数 。

• 两个集合之间的 函数 或 映射 是将第一个集合的每个成员与第二个集合中唯一成员相关联的规则。

• 鸽笼原理 指出：若 X 是鸽子的集合， Y 是鸽笼的集合，并且有| X |>| Y |，则任意由鸽子集合到鸽笼集合的函数都会给某个鸽笼分配多于1只鸽子。

• 扩展鸽笼原理 指出：若 X 是鸽子的集合， Y 是鸽笼的集合，并且有| X |> k | Y |，则任意由鸽子集合到鸽笼集合的函数都会给某个鸽笼分配多于 k 只鸽子。

• 一个项的序列可以用具有不同数字下标的同一变量表示，如 x ₁ ，…， x _n ，下标也可以是一个代数表达式。

• 算术基本定理 指出：任意正整数都存在唯一一个质分解。

习题

1.1 求解下列问题。

（a）|{0，1，2，3，4，5，6}|。

（b） 。

（c） 。

（d）100的因子集合。

（e）100的质因子集合。

1.2 设 f （ n ）是 n 的最大质因子。当 x < y 时，会有 f （ x ）> f （ y ）吗？举例或说明为什么不可能。

1.3 什么情况下有| x |=| x |-1？

1.4 想象一下：有一个9×9的鸽笼方阵，每个鸽笼里有一只鸽子。（因此，81只鸽子在81个鸽笼中，见图1.4。）假设所有鸽子同时向上、向下、向左或向右移动一个鸽笼。（边缘的鸽子不允许移出方阵。）证明某个鸽笼里会飞进两只鸽子。提示：数字9有点复杂。尝试小一点的数儿，看看会发生什么。

1.5 证明在任意一群人中，有两个人在群中拥有同样多的朋友。（这里有个重要的假设：没有人是他或她自己的朋友，并且朋友关系是 对称的 （symmetrical），即如果 A 是 B 的朋友，那么 B 也是 A 的朋友。）

1.6 已知球体上的任意5个点，证明其中4个点必位于一个闭合的半球体中，其中“闭合”表示半球中包括一个“圈”，该圈将其与球体的另一半分开。 提示 ：已知球体上的任意两点，总可以在它们之间画一个“大圈”，该圈与球体的赤道有相等的周长。

1.7 证明在任意25个人的人群中，必有3个人的生日在同一个月。

1.8 一堆硬币中包含6种不同的面值：1分、5分、10分、15分、50分和1元。至少要收集多少枚硬币才能保证至少有100枚硬币的面值相同？

1.9 有25个人每天在同一家健身房上瑜伽课，该健身房每天提供8节课。每位参加者可以穿蓝色、红色或绿色衬衫去上课。证明在某一天，至少有一节课上有两个人穿着同一颜色的衬衫。

1.10 在1和60之间（包括1和60）选择4个不同的整数，证明其中两个数的差最多是19。

1.11 找到一个 k ，使得前 k 个质数的乘积加1不是质数，并且具有比前 k 个质数都大的质因子。（解决这个问题没有诀窍，必须尝试各种可能。）

1.12 证明任意9个正整数构成的集合中，存在两个数具有相同的小于或等于5的质因子。

1.13 从字符串集到数字集的 哈希函数 （hash function）作用是为文本字符串 s 计算出一个哈希数值 h （ s ）。例如，将 s 中所有字符的数字编码相加，再除以质数 p ，保留余数。哈希函数的关键点是能产生可再现的结果（即对同一字符串 s 计算两次 h （ s ）会产生相同的数值），并且使不同字符串的哈希值在0到 p -1之间均匀分布。当哈希函数对不同的两个字符串产生相同的哈希值时，称这两个字符串是哈希值 冲突 （collide）的。哈希值的 冲突数 是指具有相同的哈希值的字符串的数量减1，因此，如果有2个字符串具有相同的哈希值，则该哈希值的冲突数是1。如果有 m 个字符串和 p 个可能的哈希值，那么对于发生最多冲突的哈希值，发生的最小冲突数是多少？某哈希值发生的最大冲突数是多少？ vW9KNV+FPu+dhjzwSnUR9xyOaEuN4ECICsBKRYK6q41UlcxXMHpW6uS/g3vulBeL