《组合数学》 第五章 抽屉原理和Ramsey理论
xi、xj和xk，其几何中心xi?xj?xk??3也是一个整点。 更一t维空间有n个整点，其中必存在k个整点，其几何般的中心也是整点。 问题 例1 t=1，问题同上。k=2，n=3，k=3，n=5 t=k=2，n=5 例2 证．设5个平面点为?xi,yi?（i=1,2,3,4,5） t=2，k=3，n=9 t任意，k=2，n=2+1 t例3 例4
例 5.2.2 从1,2,?,2n中任取n＋1个数，其中至少有一对数，一个是另一个的倍数。
（证）设所取的n＋1个数为a1,a2, ?,an+1，并 （1）表示 ai?2iri??i?0?，i＝1,2, ?,n＋1且ri为奇数。
（2）设置抽屉与物品：1~2n之间只有n个奇数（抽屉），故由抽屉原理知此n＋1个ri中至少有两个是相同的。设为 rj ＝ rk ＝r，即aj?2?j?rj?2?jr，ak?2?krk?2?kr，
显然有：要么ajak，要么akaj。
（3）说明：这里已是最好的“可能结果”，即针对各种条件，稍加放松，则结论不一定成立。
? 改为取n个数，只要取n＋1,n＋2, ?,2n这n个数，显然不满足结论。 ? 改为在1,2,?,2n+1中选n＋1个数，则结论也不一定成立。例如n=5，选6，7，8，9，10，11
6/37
《组合数学》 第五章 抽屉原理和Ramsey理论
例 5.2.3 设a1,a2, ?,am为任意m个正整数，则其中必存在若干个相继的数，其和是m的倍数。即至少存在正整数j和k(1≤j＜k≤m)，使得m能整除
k?ai=aj?aj?1???ak。
i?ji(证) 构造数列 si?s1 ?ajj?1=a1?a2???ai ，则 ri?si mod m ，则0≤ri＜m （i＝1,2,?,m） 若有某 rk＝0，则msk，问题得证。否则，所有ri≠0，由抽屉原理知，至少存在j km ，从而有msk?sj??ai。 i?j?1本题构造“抽屉”与“物品”的技巧在于并不直接针对正整数ai，而是构造出适合利用抽屉原理的n个数ri。为了构造ri，间接利用了si以达到目的。其中的抽屉是取关于模m的剩余类：0,1, ?,m－1，并且在应用抽屉原理时分为两步走。第一步先将ri分为两大类，即0与非0（或看作两个大抽屉）；第二步，针对非0情形，分为m－1种情况（或看作m－1个小抽屉）。 例 5.2.4 设正整数序列a1,a2,?,a25满足ai+1＋ ai+2＋?＋ ai+5≤6，i＝0,1,?20。 试证明至少存在正整数j、k（1≤j＜k≤25），使得aj＋aj+1＋?＋ak＝19。 i(证) 构造序列 si?s1 ?ajj?1=a1?a2???ai ，则 若有某个sk＝19，那么，问题得证（j＝1）。 7/37 《组合数学》 第五章 抽屉原理和Ramsey理论 否则，所有si≠19。 令集合 A＝{ s1，s2，?，s25，s1＋19，s2＋19，?，s25＋19} 且有 20≤s1＋19＜s2＋19＜?＜s25＋19≤49。 集合A中共有50个数，每个数的取值在1到49之间，由抽屉原理，其中必有两数相同。又知i≠j时，si≠sj，从而 si＋19≠sj＋19 。 所以，相等的两项必为 sk ＝ sj＋19（显然k>j）， 即 k19?sk?sj??ai=aj?1?aj?2???ak ，证毕。 i?j?1 问题一般化：设正整数序列a1,a2,?,amn满足ai+1＋ ai+2＋?＋ ai+n≤p，i＝0,1,?,n(m－1)。 若要求存在正整数j 分析：令 si ＝a1＋a2＋?＋ai， i＝0,1,?,nm 设 A＝{ s1，s2，?, smn，s1＋q，s2＋q , ?，smn＋q } 且有 1≤s1< s2< ?< smn， q< s1＋q< s2＋q 要用抽屉原理，A中元素个数必须大于A中最大数smn＋q，即mp＋q<2mn，或mp?q?2mn?1，由此得结论：q≤m(2n－p)－1 。 本例中，m＝n＝5，p＝6，q＝19 。 若选m＝n＝10，p＝16，则q≤39 。 变异：一学生用37天共60小时复习功课，第i天复习ai小时（ai为正整数），则无论如何安排，总存在相继若干天，这些天的复习时数之和恰为13 。 此问题实际上隐含着m＝1，n＝37，p＝60，q＝13 。 这时，问题可以描述为：m个正整数a1,a2,?,am满足 8/37 《组合数学》 第五章 抽屉原理和Ramsey理论 a1＋a2＋?＋am＝n，要存在1?j?k?m，使得aj＋ aj+1＋?＋ ak ＝q，必须有q≤2m－n－1（这只要在一般问题中取m＝1，n＝m，p＝n即可）。 例 5.2.5 将65个正整数1,2, ?,65随意分为4组，那么，至少有一组，该组中最少存在一个数，是同组中某两数之和或另一数的两倍。 (证) 用反证法。设任何一组数中的每一个数，它既不等于同组中另外两数之和，也不等于同组中另一数的两倍。即任何一组数中的的任意两个数之差总不在这个组中。 由抽屉原理，四组中至少有一组（称为A组），其中至少有17个数。从中取17个：记为a1,a2,?,a17，不妨设a17最大。令 ai?1??a17?ai， i＝1,2, ?,16 显然1?ai?1??65 。 由假设知ai?1??A（否则，就有某个ak和ak满足a17=ak+aj），所以，该16个数必在另外三组B、C、D中。 再由抽屉原理知，B、C、D三组中至少有一组（设为B组），至少含有6个ai1。只取其中6个，记为b1,b2,?,b6， ?1?同理可设b6最大，并令bi?b6?bi（i＝1,2,?,5）。同样有 ??1?bi?1??65 且bi?1??1??B。而且由假设知 bi?b6?bi?a17?aj??a17?ak??ak?aj?A ??（aj?ak） 故该5个数一定在C或D中。 又由抽屉原理，设C组中至少有3个bi?1?，取其中3个记为c1?c2?c3 。 同理可证d1?c3?c2,d2?c3?c1（d1?d2，1?di?65）也不在A、B、C三组中，故必在D组中。进一步，可证得e?d2?d1?c2?c1不在A、B、C、D中，且满足1?e?65 。 这说明从1到65的这65 9/37 《组合数学》 第五章 抽屉原理和Ramsey理论 个整数中有一个不在A、B、C、D这4组的任何一组中，与题设矛盾。 例 5.2.6 由mn＋1个不同实数构成的序列?aii?1,2,?mn?1?中必存在一个(m＋1)项的递增子序列或(n＋1)项的递减子序列。 (证) 某个序列?bnn?1,2,?n?是递增的，是指该序列满足：b1?b2???bn；反之，若b1?b2???bn，则称其是递减的。 针对每一个ai，以ai为首项，向后寻找递增子序列，最长子序列的项数（即长度）记为t（i＝1,2, ?,mn＋1），则1≤ti≤mn＋1 (若ai之后每一项都比ai小，则t ＝1；若ai之后有一项aj比ai大，则t＝2；若aj之后还有一项ak比aj大，则t＝3 ?)。 iii例如，对m=2，n=4序列 4 5 2 9 3 1 8 6 7 t1=4，t2=3，t3=4，t4=1，t5=3，t6=3，t7=1，t8=2，t9=1 若有某个 ti≥m＋1，则问题得证。 否则，所有 1≤ti≤m，由推论1，至少有n＋1个ti相等，设 tk?tk???tk12n?1， 且1?k1?k2???kn?1?mn?1 那么，必有ak1?ak2???akn?1，从而构成n＋1个实数的递减子序列。事实上，若ki?kj时，有aki?akj，则以aki为首项的最长子序列比以akj为首项的最长子序列多一项，即tki?tkj，矛盾。 本例已达到最好的可能结果。 特例：m＝n 。 实际的问题为：不同高度的n2?1个人 10/37