2024年3月25日发(作者：姒馥芬)
第一节 鸽巢原理
关于鸽巢原理的阐释，粗略地说就是如果有许多鸽子飞进不够多
的鸽巢内，那么至少要有一个鸽巢被两个或多个鸽子占据。
一、鸽巢原理的简单形式
1、定理1：如果要把n+1个物体放进n个盒子，那么至少有一个盒
子包含两个或更多的物体。
证明：用反证法进行证明。如果这n个盒子中的每一个都至多含有一
个物体，那么物体的总数最多是n，这与有n+1个物体矛盾。所以某
个盒子至少有两个物体。
2、定理1的说明：无论是鸽巢原理还是它的证明，都不能具体找出
含有两个或更多物体的盒子。它只是证明这样的盒子存在，即如果人
们检査每一个盒子.那么他们会发现有的盒子里面放有多个物体。另
外，当只有n个（或更少）物体时，是无法保证鸽巢原理的结论的。
这是因为可以在n个盒子的每一个里面放进一个物体。所以鸽巢原理
成立的条件是至少为n+1个物体。
3、鸽巢原理的两个简单应用
应用1：在13个人中存在两个人，他们的生日在同一个月份里。
应用2：设有n对己婚大妇。至少要从这2n个人中选出多少人才能保
证能够选出一对夫妇？
为了在这种情形下应用鸽巢原理，考虑n个房间，其中一个房间
对应一对夫妇。如果选择n十1个人并把他们中的每一个人放到他们
夫妻所对应的那个房间中去，那么就有一个房间含有两个人；也就是
说，已经选择了一对已婚夫妇。选择n个人使他们当中一对夫妻也没
有的两种方法是选择所有的丈夫和选择所有的妻子，因此，n+1是保
证能有一对夫妇被选中的最小的人数。
4、从应用2得出的两个推论
推论1：如果将n个物体放入n个盒子并且没有一个盒子是空的，那
么每个盒子恰好有一个物体。
说明：以应用2为例，选择n个人，如果其中有一对夫妻，那么必然
有一个房间是空的，为了保证没有空房间，则必须从每对夫妻中选一
个人，即恰好从每对夫妻中选一个人。
推论2:如果将n个物体放入n个盒子并且没有盒子被放入多于一个的
物体，那么每个盒子里恰好有一个物体。
说明：以应用2为例，选择n个人，每个房间只能是夫妻中的一个人，
2n个人，恰好每个从每对夫妻当中选择一个人。
5、例题
例1：给定m个整数
a
1
，a
2
，……，a
m
，存在满足0≤k≤l≤m的整
数k和l，使得
a
k+1
+ a
k+2
+ ……+ a
l
能够被m整除。
分析：题目通俗化，即给定m个整数的序列，其中连续几个的和能被
m整除。所以考虑序列中连续和的情况。如果其中任何一个能被m整
除，那么结论就成立了。对此，只能先假设连续和不能被整除，即有
余数。
解：找出鸽子：m个正整数连续和，即
a
1
，a
1
+a
2
， a
1
+a
2
+a
3
，……，
a
l
+a
2
+a
3
+……+ a
m
共m个和
构造鸽巢：连续和不能被整除，那么余数必然为1,2，……，m-1共
m-1个。如果余数为0或m，则已经整除结论成立，所以只能是m-1
个。
鸽巢原理：m个和，m-1个余数，那么必然有两个余数是相同的。因
此存在整数k和l，0≤k≤l≤m，使得
a
l
+a
2
+a
3
+……+ a
k
及
a
l
+a
2
+a
3
+……+ a
l
除以m有相同的余数
，
不妨设
2024年3月25日发(作者：姒馥芬)
第一节 鸽巢原理
关于鸽巢原理的阐释，粗略地说就是如果有许多鸽子飞进不够多
的鸽巢内，那么至少要有一个鸽巢被两个或多个鸽子占据。
一、鸽巢原理的简单形式
1、定理1：如果要把n+1个物体放进n个盒子，那么至少有一个盒
子包含两个或更多的物体。
证明：用反证法进行证明。如果这n个盒子中的每一个都至多含有一
个物体，那么物体的总数最多是n，这与有n+1个物体矛盾。所以某
个盒子至少有两个物体。
2、定理1的说明：无论是鸽巢原理还是它的证明，都不能具体找出
含有两个或更多物体的盒子。它只是证明这样的盒子存在，即如果人
们检査每一个盒子.那么他们会发现有的盒子里面放有多个物体。另
外，当只有n个（或更少）物体时，是无法保证鸽巢原理的结论的。
这是因为可以在n个盒子的每一个里面放进一个物体。所以鸽巢原理
成立的条件是至少为n+1个物体。
3、鸽巢原理的两个简单应用
应用1：在13个人中存在两个人，他们的生日在同一个月份里。
应用2：设有n对己婚大妇。至少要从这2n个人中选出多少人才能保
证能够选出一对夫妇？
为了在这种情形下应用鸽巢原理，考虑n个房间，其中一个房间
对应一对夫妇。如果选择n十1个人并把他们中的每一个人放到他们
夫妻所对应的那个房间中去，那么就有一个房间含有两个人；也就是
说，已经选择了一对已婚夫妇。选择n个人使他们当中一对夫妻也没
有的两种方法是选择所有的丈夫和选择所有的妻子，因此，n+1是保
证能有一对夫妇被选中的最小的人数。
4、从应用2得出的两个推论
推论1：如果将n个物体放入n个盒子并且没有一个盒子是空的，那
么每个盒子恰好有一个物体。
说明：以应用2为例，选择n个人，如果其中有一对夫妻，那么必然
有一个房间是空的，为了保证没有空房间，则必须从每对夫妻中选一
个人，即恰好从每对夫妻中选一个人。
推论2:如果将n个物体放入n个盒子并且没有盒子被放入多于一个的
物体，那么每个盒子里恰好有一个物体。
说明：以应用2为例，选择n个人，每个房间只能是夫妻中的一个人，
2n个人，恰好每个从每对夫妻当中选择一个人。
5、例题
例1：给定m个整数
a
1
，a
2
，……，a
m
，存在满足0≤k≤l≤m的整
数k和l，使得
a
k+1
+ a
k+2
+ ……+ a
l
能够被m整除。
分析：题目通俗化，即给定m个整数的序列，其中连续几个的和能被
m整除。所以考虑序列中连续和的情况。如果其中任何一个能被m整
除，那么结论就成立了。对此，只能先假设连续和不能被整除，即有
余数。
解：找出鸽子：m个正整数连续和，即
a
1
，a
1
+a
2
， a
1
+a
2
+a
3
，……，
a
l
+a
2
+a
3
+……+ a
m
共m个和
构造鸽巢：连续和不能被整除，那么余数必然为1,2，……，m-1共
m-1个。如果余数为0或m，则已经整除结论成立，所以只能是m-1
个。
鸽巢原理：m个和，m-1个余数，那么必然有两个余数是相同的。因
此存在整数k和l，0≤k≤l≤m，使得
a
l
+a
2
+a
3
+……+ a
k
及
a
l
+a
2
+a
3
+……+ a
l
除以m有相同的余数
，
不妨设