第二章鸽巢原理习题课

1、第二章鸽巢原理习题课第2章 小结（1）本章小结本章小结 本章讨论了鸽笼原理及其推广，本章讨论了鸽笼原理及其推广， Ramsey 数及其数及其性质，性质，Ramsey定理以及一些有趣的应用。鸽笼原理定理以及一些有趣的应用。鸽笼原理是重要的组合基本原理之一。是重要的组合基本原理之一。重点是：重点是：（1）鸽笼原理的正确使用。）鸽笼原理的正确使用。这是需要一定的技巧的，关键在于认清这是需要一定的技巧的，关键在于认清“鸽子鸽子”（放（放进盒子的物体）并制造进盒子的物体）并制造“鸽笼鸽笼”。而制造。而制造“鸽笼鸽笼”的的依据是：依据是：“待证命题成立，蕴涵有两只鸽子在同一鸽待证命题成立，蕴涵有两只鸽子在

2、同一鸽笼笼”。（2）鸽笼原理的加强形式）鸽笼原理的加强形式有多种说法，其中关于算术平均的说法应用尤广，它有多种说法，其中关于算术平均的说法应用尤广，它告诉我们，当告诉我们，当m/nrm个物体放入个物体放入n个盒子，那么至个盒子，那么至少有一个盒子有少有一个盒子有r+1个物体。运用它解题的关键仍然个物体。运用它解题的关键仍然是正确的设置是正确的设置“盒子盒子”。第2章 小结（3）本章小结本章小结（3） Ramsey定理，定理，Ramsey数数Ramsey定理的性质可以概述为定理的性质可以概述为“任何一个足够大的结构中任何一个足够大的结构中必定包含有一个给定大小的规则子结构必定包含有一个给定大小的

3、规则子结构”。在解有关在解有关Ramsey定理及其应用的问题时，最重要的是正确定理及其应用的问题时，最重要的是正确理解定理意义，特别是理解定理意义，特别是r=2时定理的几种形象的说法。时定理的几种形象的说法。在解题时，则要正确地设计一个集合，该集合分成哪几个在解题时，则要正确地设计一个集合，该集合分成哪几个部分，正确的确定部分，正确的确定a1,a2,am以及以及r分别体现在哪些已知量分别体现在哪些已知量或已知事实中。或已知事实中。如果从更高的角度看问题，有关鸽笼原理和如果从更高的角度看问题，有关鸽笼原理和Ramsey定理的定理的应用问题的解法都是模型化归方法。即把实际问题化归到应用问题的解法都

4、是模型化归方法。即把实际问题化归到“鸽子，鸽笼鸽子，鸽笼”的模式，化归到的模式，化归到“一个集合的一个集合的r子集分类子集分类”的模式的方法。的模式的方法。1. 鸽巢原理鸽巢原理1.1 鸽巢原理的简单形式鸽巢原理的简单形式 若有n+1只鸽子飞到n个鸽巢里面，则至少有一个鸽巢里至少有两只鸽子。1.2 鸽巢原理的加强形式鸽巢原理的加强形式注: n+1为结论成立的最小数。 将q1q2qnn1个物品放入n个抽屉中，则至少存在某个抽屉i（1in）,使得这个抽屉里至少有qi个物品。注: q1q2qnn1为结论成立的 最小 数,记为N(q1,q2,qn;1)。显然,当q1=q2=qn=2时,加强形式即为简单

5、形式。即即N(q1,q2,qn;1)=q1+q2+qn-n+1.鸽巢原理与Ramsey定理习题课 推论1 n(r-1)1只鸽子飞入n个巢里，则至少有一个鸽巢里至少有r只鸽子。当qi=r时，得： 推论3：设m1,m2,mn均为正整数,且满足 , 则m1,m2,mn中至少有一个数不小于r。 123.1nmmmmrn 推论2：m只鸽子飞入n个巢里，则至少有一个鸽巢里至少有 只鸽子,其中 是不小于 的最小整数。mnmnmn2 鸽巢的构造及其应用鸽巢的构造及其应用 虽然鸽巢原理十分简单明了，但不是所有的问题都一眼就可以看出什么是鸽子，什么是鸽巢。在应用它的时候却涉及很多技巧，这是利用鸽巢原理解题的魅力所

6、在。常用的构造鸽巢的方法有：利用整数分组、余数分类，划分集合，分割区间、分割图形，利用染色等。下面给出几类常用的构造鸽巢的方法。2.1 利用整数分组构造利用整数分组构造“鸽巢鸽巢” 例例1 试证明从试证明从11，2 2，kn 中选中选n+1+1个数，总存在个数，总存在2 2个数，它们之间最多个数，它们之间最多相差相差k-1-1。 证明：证明： 把把1，2，kn分为分为n部分部分1，2，3，,k, k+1,k+2,2k,(n-1)k+1,(n-1)k+2,kn,即做即做n个鸽巢，从中任个鸽巢，从中任选选n+1个数，由鸽巢原理，必有个数，由鸽巢原理，必有2个数选在同一个鸽巢中，所以它们的个数选在同

7、一个鸽巢中，所以它们的差最大为差最大为k-1。 路易路易波萨是匈牙利数学家波萨是匈牙利数学家, 在他在他11岁时匈牙利大数学家厄杜斯给他出岁时匈牙利大数学家厄杜斯给他出了个问题了个问题: “如果你手头上有如果你手头上有n+1个整数，这些整数是小于或等于个整数，这些整数是小于或等于2n的，那么你一的，那么你一定会有一对数是互素的。你知道这是什么原因吗？定会有一对数是互素的。你知道这是什么原因吗？”波萨仅思考了半分钟就巧妙地回答了这个问题。波萨仅思考了半分钟就巧妙地回答了这个问题。 例例2 在一条笔直的马路上种树，从起点起，每隔在一条笔直的马路上种树，从起点起，每隔1米种一棵数。如果把三米种一棵数

8、。如果把三块块“爱护爱护 树木树木”的小牌分别挂在三棵树上，那么不管怎么挂，至少有两棵挂的小牌分别挂在三棵树上，那么不管怎么挂，至少有两棵挂牌的树它们之间的牌的树它们之间的 距离是偶数（以米为单位）。距离是偶数（以米为单位）。 解解 从起点开始给每课树编号，树上的号码依次为从起点开始给每课树编号，树上的号码依次为1,2,3,1,2,3,n, 把这些号码把这些号码分为奇数和偶数两类，当作两个鸽巢，分为奇数和偶数两类，当作两个鸽巢， 把三块牌分别挂在三棵树上，那么不管把三块牌分别挂在三棵树上，那么不管怎么挂，这三棵挂牌的树至少有两棵树的号码同为奇数或偶数，而这两棵树的差怎么挂，这三棵挂牌的树至少有

9、两棵树的号码同为奇数或偶数，而这两棵树的差必为偶数，必为偶数， 所以至少有两棵挂牌的树它们之间的距离是偶数（以米为单位）。所以至少有两棵挂牌的树它们之间的距离是偶数（以米为单位）。 2.2 利用划分图形构造利用划分图形构造“鸽巢鸽巢” 例例1 1 边长为边长为1 1的正方形中，任意放入的正方形中，任意放入9 9个点，求证这个点，求证这9 9个点中任个点中任取取3 3个点组成的三角形中，至少有一个的面积不超过个点组成的三角形中，至少有一个的面积不超过 . .18 解：将边长为解：将边长为1 1的正方形等分成边长为的正方形等分成边长为1/21/2的四个小正方形，视这四的四个小正方形，视这四个正方形

10、为鸽巢，个正方形为鸽巢，9 9个点任意放入这四个正方形中，由鸽巢原理必有三个点任意放入这四个正方形中，由鸽巢原理必有三点落入同一个正方形内点落入同一个正方形内. .现特别取出这个正方形来加以讨论现特别取出这个正方形来加以讨论. . 图1 把落在这个正方形中的三点记为把落在这个正方形中的三点记为D D、E E、F.F.如图如图1 1，通过这三点中的任意一点（如通过这三点中的任意一点（如E E）作正方形边平行线）作正方形边平行线1111 1()2222 2hh11.4848hhSDEFSDEGSEFG 所以，结论成立。如果如果8个点无一个在圆心上，可将圆分成个点无一个在圆心上，可将圆分成7个相等的

11、扇形，由鸽巢原理，个相等的扇形，由鸽巢原理， 这这8个点至少有两个在同一个扇形内，则这两点之间的距离小于半径。个点至少有两个在同一个扇形内，则这两点之间的距离小于半径。 例例2 2 在圆内（包刮圆周）有在圆内（包刮圆周）有8 8个点，则其中必有两个点，它们之间的距离小个点，则其中必有两个点，它们之间的距离小于圆的半径。于圆的半径。证明证明 分两种情况考虑。分两种情况考虑。A1A2A3A4A6A5o2 sin2bR2. 2. 如果如果8 8个点有一个点在圆心，可将圆个点有一个点在圆心，可将圆分成分成6个相等的扇形，如图，个相等的扇形，如图，取扇形取扇形OA1A2不包含不包含OA2,扇形扇形OA2

12、A3不包含不包含OA3,扇形扇形OA6A1不包含不包含OA1, 由鸽巢原理，余下的由鸽巢原理，余下的7个点个点至少有两个在同一个扇形内，则这两点之间的距离至少有两个在同一个扇形内，则这两点之间的距离小于半径。小于半径。由于圆上相邻两点由于圆上相邻两点A Ai,A,Aj间的弦长恰好为圆的半径，所以间的弦长恰好为圆的半径，所以弦长：在边长为1的正方形内任取5个点,则其中至少有两点,它们之间的 距离不超过2.22.证明: (1) 在一边长为1的三角形中任取10个点,则其中至少有两点,它们之间 的距离不超过1/3. (2) 确定mn，使得在一边长为1的三角形中任取mn个点,则其中至少有 两点,它们之间

13、的距离不超过1/n.类似这样的问题还有不少。2.3 2.3 利用余数分类构造利用余数分类构造“鸽巢鸽巢” 例例 试证明任意给定试证明任意给定5252个整数，它们之中必有个整数，它们之中必有2 2个数，其和或差个数，其和或差是是100100的倍数的倍数( (即被即被100100整除）整除）。 证明：任意一个整数证明：任意一个整数a除以除以100产生的余数为产生的余数为0，1，2，99共共100种。用种。用a1, a2, ,a52表示这表示这52个整数，个整数，ai除以除以100产生的余数记为产生的余数记为ri（ i=1，2，52）。）。 由鸽巢原理，这由鸽巢原理，这52个整数分别除以个整数分别除

14、以100产生的产生的52个余数个余数r1,r2,r52中必中必有两个余数落在同一组中有两个余数落在同一组中， 我们现在用我们现在用0 0，1 1，2 2，,99,99这这100100个余数来构造鸽巢，将它们分为个余数来构造鸽巢，将它们分为5151组，组，构造出构造出5151个鸽巢：个鸽巢： 00，11，9999，22， 9898，49,51,50,49,51,50,即存在两个数，它们的和或差能被即存在两个数，它们的和或差能被100整除。整除。若这两个余数落在若这两个余数落在0或或50中，则它们的和及中，则它们的和及差都能被差都能被100整除。整除。 若这两个余数落在剩下的若这两个余数落在剩下的

15、49组中的一组，当余数相同组中的一组，当余数相同时，它们的差时，它们的差被被100100整除，整除，当余数不同时，它们的和被当余数不同时，它们的和被100整除，整除，类似这样的例子也有不少。 这个问题的一般提法 任意给定n+2个整数，它们之中必有2个数，其和或差是2n的倍数。1.任取n+1个正整数，求证在这n+1 个数中必有两个数它们之差被n整除.2.任意给出2011个正整数 证明必存在正整数122011,a aa122011/().kklaaa0, (2011),k lkl 使得2.任意给出2011个正整数 证明必存在正整数122011,a aa122011/().kklaaa使得,2011

16、),k lkl （0证明证明 构造部分和序列构造部分和序列112122011122011,sasaasaaa则有如下两种可能：则有如下两种可能：（i）存在整数存在整数h(1h 2011), 使得使得 . 此时此时, 取取k=0,l=h即满足即满足 题题意意.2011/hs（iiii）对任一整数）对任一整数i，均有，均有 . .令令 ，2011| (12011)isi (mod2011)iisr12010 (12011),iri 则有则有这样这样, 2011个余数均在个余数均在1到到2010之间之间,由鸽巢原理知由鸽巢原理知, , 存在整数存在整数 , , 使得使得 . . (1,2011)kl

17、k lklrr不妨设不妨设l k，则，则12()(mod2011)0(mod2011).kkllklkaaassrr综合（综合（i）和（）和（ii），即知题设结论成立），即知题设结论成立.2.4 利用分割区间来构造利用分割区间来构造“鸽巢鸽巢“ 例例 一个孩子每天至少看一个小时电视，共看一个孩子每天至少看一个小时电视，共看7 7周，每周看电视从不超周，每周看电视从不超过过1111小时，证明：在此期间存在连续若干天这个孩子恰好看电视小时，证明：在此期间存在连续若干天这个孩子恰好看电视 2020个小个小时。（设这个孩子每看电视时间为整数个小时）时。（设这个孩子每看电视时间为整数个小时） 证明证明

18、设这个孩子设这个孩子7周内每天看电视的时间分别为周内每天看电视的时间分别为a1,a2,a49小时小时，现在构造出数列现在构造出数列an的前的前n项和的数列项和的数列 s1=a1， s2=a1+a2， s49=a1+a2+a49 ，则有：1 s1s2s3s49117=77,而序列s1+20，s2+20，, s49+20也是一个严格的递增序列，且有 21 s1+20 s2+20j)，即，即si-sj= 20，从而这个孩子从，从而这个孩子从 j+1天起到第天起到第i天的时间里恰好看电视天的时间里恰好看电视20个小时。个小时。类似这样的例子还有不少。类似这样的例子还有不少。1.1.一个乒乓球手有一个乒

19、乓球手有3737天时间准备一场比赛天时间准备一场比赛, ,他决定每天至少打他决定每天至少打1 1场球场球,37,37 天至多打天至多打6060场球场球, ,证明证明: :在此期间存在连续若干天他恰好打了在此期间存在连续若干天他恰好打了2121场球。场球。2.一一个学生解数学题个学生解数学题100天天,每天至少解一道题每天至少解一道题,每每10天至多解天至多解17道道题题,证明证明:在此期间存在连续若干天他恰好解了在此期间存在连续若干天他恰好解了29道题道题.那么是否存那么是否存在连续若干天他恰好解了在连续若干天他恰好解了30道题。道题。3. 在在(0,1区间上任取区间上任取5个点，则必有两个点

20、它们的距离小于个点，则必有两个点它们的距离小于1/4。4. n+1个实数个实数xi满足满足0 xi1（i=1,2,n+1），求证这），求证这n+1个实数中必存在两个实数中必存在两个数个数xi,xj，使得，使得 1|.ijxxn 由于1ai200，所以ri(1i101)只能取1，3，5，199这100个奇数，而r1，r2， ，r101共有101项，由鸽巢原理知，存在 1ij101，使得ri=rj ，不妨设sisj，则即aj能被ai整除.2.5 利用化分集合来构造利用化分集合来构造“鸽巢鸽巢” 例 试证明在1到200个自然数中任取101个数，一定存在两个数，其中的一个数是另一个数的整数倍。 证明:

21、 设a1，a2，a101是被选出的101个整数,对任一ai，都可以唯一地写成 如下的形式：2 (1,2,101),isiiari其中，si为整数，ri为奇数.222jjiisssjjsiiarar整数推论推论3 3的应用的应用. .例例1 把把1至至10这十数字随机的排成一个圆圈，证明这十数字随机的排成一个圆圈，证明必有一个三相邻数字之和大于等于必有一个三相邻数字之和大于等于17证明证明把把1至至10这十个数字随机排成一个圆圈这十个数字随机排成一个圆圈,从中任取从中任取三个相邻数字的方法有三个相邻数字的方法有10种种,设这设这10种三个相邻数字之和分别种三个相邻数字之和分别为为m1,m2,m1

22、0,则有则有m1+m2+m10=3(1+2+10)=3 (10 11).21210.3 1116.5 16,102mmm 例 2 设有大小两个圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形漆成黑色，其余的100个小扇形漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色. 现将大小两只圆盘的中心重合，转动小盘使小盘上的每个扇形含在大盘上的小扇形之内. 证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色. 证明：由条件，固定大盘转动小盘共有200个不同的位置，设mi表示在第i个位 置时，大、小扇形同色的个数（i=1，2，200），只要证明.122001

23、()99200mmm 对小盘上的每一个扇形，由着色的条件，旋转一周（200个位置），与大扇形同色的个数为100个，所以200个小扇形在旋转一周同色的个数共有 100200=20000个. 1220012200 200001 ()99 200mmmmmm结论成立.即可.3. 3. 鸽巢原理在国内外数学竞赛中的应用鸽巢原理在国内外数学竞赛中的应用 中学数学竞赛中，鸽巢原理常常作为一种处理问题的工具，多中学数学竞赛中，鸽巢原理常常作为一种处理问题的工具，多用于组合问题，在一些代数与几何问题中亦有应用。鸽巢原理及用于组合问题，在一些代数与几何问题中亦有应用。鸽巢原理及其简单形式多用于解答存在性问题，应

24、用鸽巢原理解题时，关键其简单形式多用于解答存在性问题，应用鸽巢原理解题时，关键是构造适合的鸽巢。下面给出一些利用鸽巢原理解决的数学是构造适合的鸽巢。下面给出一些利用鸽巢原理解决的数学竞赛题。竞赛题。例1 (北京市数学竞赛复赛试题北京市数学竞赛复赛试题) 将将910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种： 1至少三行完全相同； 2至少有两组（四行），每组的两行完全相同。 证明：910瓶红、蓝墨水，排成130行，每行7瓶。每行中的7个位置中的每个位置都有红、蓝两种可能，因而总计共有27=128种不同的行式（当且仅当两行墨水瓶颜色及

25、次序完全相同时称为“行式”相同）。依鸽巢原理可知，在130行中必有两行（记为A，B）“行式”相同。 在除A、B外的其余128行中若有一行P与A（B）“行式”相同，则P，A，B满足“至少有三行完全相同”，结论成立；在除A，B外的其余128行中若没有与A（B）行式相同者，则128行至多有127种不同的行式，依鸽巢原则，必有两行（不妨记为C、D）行式相同，这样便找到了（A，B）、（C，D）两组（四行），每组两行完全相同，结论成立。 例2 (1995年全国高中数学联赛试题年全国高中数学联赛试题 ) 将平面上每个点以红、蓝两色之一着色，证明：存在这样的两个相似三角形，它们的相似比为1995，并且每一个三

26、角形的三个顶点同色。证明：如图，作两个半径分别为1和1995的同心圆，在 内 圆 上 任 取 9 个 点 ， 必 有 5 点 同 色 ， 记 为A1,A2,A3,A4,A5。如图所示，连半径0Ai交大圆于Bi（i=1,2,3,4,5），对B1，B2，B3，B4，B5，必有3点同色，记为Bi,Bj,Bk，则BiBjBk与AiAjAk为三顶点同色的相似三角形，相似比等于1995，所以结论成立.2sin2rb弦长例例3 (美国普特南数学竞赛题美国普特南数学竞赛题 ) 在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明其中一定存在两个整点，它们的连线中点仍是整点。 证明 欲使坐标平面两点（x1,

27、y1）、（x2,y2）的中点坐标是整数，必须而且只须x1与x2，y1与y2的奇偶性相同。 坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数，偶数），（奇数，偶数），（偶数，奇数）以此构造四个“鸽巢”，则在坐标平面上任取五个整点，那么至少有两个整点，属于同一个“鸽巢”，因此它们连线的中点就必是整点。 我们可以把整点的概念推广：如果（x1，x2,xn）是n维（元）有序数组，且x1，x2,xn中的每一个数都是整数，则称（x1，x2,xn）是一个n维整点（整点又称格点）。如果对所有的n维整点按每一个xi的奇偶性来分类，由于每一个位置上有奇、偶两种可能性，因此共可

28、分为222=2n个类(鸽巢)。这是对n维整点的一种分类方法。 当n=3时，23=8，此时可以构造命题：“任意给定空间中九个整点，求证它们之中必有两点存在，使连接这两点的直线段的内部含有整点”。这就是1971年的美国普特南数学竞赛题。 例例4 (美国普特南数学竞赛题美国普特南数学竞赛题 ) 任意6个人中必有3个人互相认识，或互相不认识。这就是著名的Ramsey问题。 这个问题可转化为：对6阶完成图K6的边任着红、蓝两色，必存在同色三角形。 证明 设A0,A1,A5为 K6的6个顶点，从A0 引出 的5条边中，必有3条同色，不妨设A0A1,A0A2,A0A3为红色。若A1A2A3有一条红边，则这条

29、边的两个端点连同A0构成红色三角形。若A1A2A3没有红边，则这个三角形为蓝红色三角形。结论成立。 我们用6个点表示6个人,当两个人互相认识时,两个点之间连一条红边,当两个人互相不认识时,两个点之间连一条蓝边,于是注注:6为结论成立的最小数为结论成立的最小数.例例5 (第第6届国际中学生数学奥林匹克试题届国际中学生数学奥林匹克试题 ) 17名科学家中每名科学家都和其他科学家通信，在他们通信时，只讨论三个问题，而且任意两名科学家通信时只讨论同一个问题，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个问题。 证明：视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问

30、题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。即转化为证明：对17阶完成图K17的边任着红、蓝、黄三色，必存在同色三角形。 考虑科学家A，他要与另外的16位科学家每人通信讨论一个问题，相应于从A出发引出16条线段，将它们染成3种颜色，由鸽巢原理必有6条同色，不妨记为AB1，AB2，AB3，AB4，AB5，AB6同红色，若Bi（i=1，2，6）之间有红线，则出现红色三角线，命题已成立；否则B1，B2，B3，B4，B5，B6之间的连线只染有黄、蓝两色，由例4存在同色三角

31、形，证毕。 前面数例我们看到，鸽巢原理的应用多么奇妙，其关键在于恰当地制造鸽巢，就像我们前面所介绍的，利用余数分类，划分集合，分割区间，分割图形，利用染色等，都是制造“鸽巢”的方法。运用鸽巢原理解题往往能起到事半功倍的效果，鸽巢原理的道理极其简单，但需要巧妙地精心地应用它，不仅可以解决国内数学竞赛中的问题，而且可以解决国际中学生数学竞赛的问题.4.鸽巢原理的推广鸽巢原理的推广Ramsey定理定理(介绍）介绍） 鸽巢原理是组合学中的一个最基本的原理，应用它可以解决许鸽巢原理是组合学中的一个最基本的原理，应用它可以解决许多涉及存在性的组合问题。但对于一些更加复杂的有关存在性的组多涉及存在性的组合问

32、题。但对于一些更加复杂的有关存在性的组合问题，鸽巢原理显得无能为力。合问题，鸽巢原理显得无能为力。 19281928年，年，2424岁的英国数学家、哲学家兼经济学家在伦敦的数学会宣岁的英国数学家、哲学家兼经济学家在伦敦的数学会宣读了一篇题为读了一篇题为“论形式逻辑中的一个问题论形式逻辑中的一个问题”的论文，文中证明的一个的论文，文中证明的一个组合数学定理后来被称为组合数学定理后来被称为RamseyRamsey定理。定理。 RamseyRamsey定理可视为鸽巢原理定理可视为鸽巢原理的推广，它的简单形式就是我们前面提到的著名的的推广，它的简单形式就是我们前面提到的著名的Ramsey问题。问题。人人们普遍认为们普遍认为RamseyRamsey定理是组合学中最重要、最精美的定理之一。定理是组合学中最重要、最精美的定理之一。2.3 Ramsey定理3练习练习6个人中一定有个人中一定有3个人相互认识或相互不认识。个人相互认识或相互不认识。证明：先考虑证明：先考虑6个人中的任意一个人，不妨把这个人称作个人中的任意一个人，不妨把这个人称作p。则其。则其他的他的5个人可以分为下面的两个集合个人可以分为下面的两个集合F和和S。其中。其中F=与与p相识的人的集合，相识的人的集合，S=与与