第27章极端原理27.1.1** 两人轮流往一个圆桌面上放同样大小的硬币．规定每人每次只能放一枚，硬币平放在桌面上，并且两两不能重叠，谁放完最后一枚．使得对方无法按照规则再放，谁就获胜．问：是先放合算还是后放合算？解析本题的极端情况是：桌面小的只能放下一枚硬币．这时当然是先放的人合算．一般情况下，先放的人把硬币放在圆桌的中心处，每当对手放下一枚硬币后，就在对方硬币关于“圆心”对称位置再放下一枚硬币，这样只要对手还能放硬币，先放的人一定也能放，所以放最后一枚硬币的人一定是先放的人，从而他必能获胜．评注本题解法的独到之处在于考虑最极端的情况，“桌面最小”．这里的极端原理实际是一种“从特殊到一般”的思考方法，并且在极端情况下的结果提示我们解决一般问题的方法，在应用极端原理时，我们要利用如下的事实：1．有限个数中一定有最大数和最小数；2．无限个正整数中有最小数；3．无限个实数不一定有最大数或最小数．27.1.2** 在一次乒乓球循环赛中，n（n≥3）名选手中没有全胜的，证明：一定可以从中找出三名选手A、B、C，使得A胜B，B胜C，C胜A．解析没取胜场数最多的一名选手为A，由于没有一个选手是全胜的，所以在这n名选手中存在一名选手C，C胜A．考虑A击败的选手的全体，其中必有选手B胜C．事实上，若A的手下败将也都负于C，那么C胜的场数比A胜的场数至少要多1，这与A是获胜场数最多的选手矛盾．所以，存在三名选手A、B、C，使得A胜B，B胜C，C胜A．27.1.3** 平面上已给997个点，将连结每两点的线段中点染成红色，证明：至少有1991个红点，能否找到恰有1991个红点的点．解析997个点中每两点都有一个距离，因而共有9979962个距离（其中有可能有些距离是相等的），其中一定有一个最大距离．设AB是最大的距离．分别以A、B为圆心，12AB为半径作圆，如图所示．点A与除点B之外的995个点的连线的中点在圆A的内部或边界上；点B与除点外的995个点的连线的中点在圆B的内部或边界上，这样我们得到了995+995＝1990个红点．另外，AB 的中点是不同于上述1990个红点的，所以，至少有1991个红点．下面构造一个例子，说明恰好有1991个红点，设997个点在数轴上1，2，3，…，997的位置．这时中点为：32，42，52，…，19922，19932，故红点恰有1991个． 27.1.4** 证明：在任意的凸五边形中，都可以找到三条对角线，由这三条对角线可以组成一个三角形． 解析 如图所示，在凸五边形ABCDE 中，一共有5条对角线：AC 、AD 、BD 、BE 、CE ，所以其中一定有一条是最长的，不妨设AC 最长．ABEPD由于ACDE 是凸四边形，设AD 与CE 的交点为P ，则AC AP PC AD CE <+<+．因为AC 最长，所以，AC 、AD 、CE 这三条对角线可以作为一个三角形的三条边．27.1.5* 平面上给定3个点。

已知其中任意两点的距离不超过1，证明：这3个点被一个半径为等的圆覆盖．解析 设三点为A 、B 、C ，不妨设BC AB ≥，AC ，当A ∠≥90︒时．易知以删为直径的圆可覆盖ABC △（此圆半径≤2BC ≤12），当90A ∠<︒时，ABC △为锐角三角形，设外心为O 在ABC △内部．由于120BOC ∠︒≥，故外接圆半径，故结论成立． 27.1.6*** 平面上给定2005个点，任意两点距离小于2005，任意三点是某个钝角三角形的顶点．求证：存在直径不超过2005的圆覆盖这2005个点．解析 在这2005个点中，设两两之间距离最大的两点是A 、B 且2005AB <．则以AB 为直径的圆覆盖了这2005个点．这是因为，如图分别过A 、B 作AB 垂线1l 、2l ，则给定的点不能在直线1l 、2l 围成的带形之外．否则这点P 到点B （或A ）距离大于AB ，这与AB 的最大性矛盾．同时，给定的点也不能在带形内部的圆外．否则，这点P '与A 、B 不构成钝角三角形，与已知条件矛盾． 故结论成立．评注 此例是组合几何问题中的一类覆盖问题．这些问题的解决往往需借助于极端原理的思想． 27.1.7** 平面上给定()212n n ->个点，其中任意三点都至少有两点距离小于l ，证明：可以找出其中n 个点位于半径为1的圆内．解析 考虑距离最远的两个点A 、B ．以A 、B 为圆心、半径为l 作两个圆，若有点C 在这两个圆外或边上，则AC 、BC ≥1，于是由条件知只能有AB <l ，与AB 的定义矛盾，因此没有点在这两个圆外或边上．于是由抽屉原理，至少有n 个点在其中一个圆的内部．27.1.8*** 在平面上任给2n 个点，其中任意三点不共线，并把其中”个点染成红色，n 个点染成蓝色．求证：可以一红一蓝地把它们连成n 条线段，使这些线段互不相交．解析 因为总共只有2n 个点，将红点与蓝点一一配对的方法只有有限种（实际上为()!121n n n ⋯=⋅-⋅⋅⋅种，即第一个红点可与n 个蓝点中的某一个配对，有1n -种可能，第二个红点与剩下的1n -个蓝点中的某一个配对，有1n -种可能……第n 个红点与剩下的一个蓝点配对，有1种可能）．对于每一种配对方法，都会得到这n 条线段的长度和，这种和数只有有限个（其实不超过!n 个），所以其中必有一个是最小的，下证这时候n 条线段是互不相交的．用反证法．假定此时有两条线段11R B 和22R B 相交，其中1R 、2R 是红点，1B 、2B 是蓝点，设它们的交点为P （如图）．由于()()112112211122R B R B R P PB R P PB R B R B +<+++=+，PR 1R 2B 2B 1所以，当我们将1R 与2B 配对，2R 与1B 配对，其他的保持不变，这时候n 条线段的长度和减少了，矛盾．因此这时n 条线段是互不相交的．评注 本题所要证明的是“存在性”命题，利用极端原理处理存在性命题的基本手法是：取极端制造所存在的东西，然后用反证法证明．27.1.9* 能否在平面上安排有限条线段，使每一条线段都至少有一端点严格地位于其他某条线段的内部？解析 不可能，因为有限条线段中不妨设最长的是AB ，且B 位于另一条线段CD 中，由于180CBA DBA ∠+∠=︒，不妨设90CBA ∠︒≥，于是AC AB >，与AB 的定义矛盾．这个命题即使在空间也是成立的．CBD A27.1.10** 平面上有n 个点，其中任意三点不共线，且任意三点构成的三角形的面积都小于1．证明：存在一个面积小于4的三角形包含这n 个点．解析 我们先通过取极端制造一个面积小于4的三角形，然后用反证法证明这个三角形包含这n 个点．n 个点中任意三点作一个三角形，三角形的个数是有限的（其实为()()1126n n n --个），每一个三角形都有一个面积，取其中面积最大的一个记为123A A A △．由于每个三角形的面积都小于1，所以1231A A A S <△．过顶点1A ，2A ，3A 分别作对边的平行线，得到一个ABC △，如图所示．显然 12344ABC A A A S S =<△△．下面证ABC △包含了这n 个点．用反证法．设ABC △外还有这n 个点中的一点，设为4A （不妨设在AC “外侧”）．如图，则123231A A A A A A S S >△△，ACA 1A 2A 3A 4这与123A A A △的面积最大矛盾．于是ABC △即为所求．27.1.11* 设n 是大于2的自然数，12k a a a ⋯<<<是小于n 且与n 互质的全部正整数．证明：这k 个数中必定有一个是质数．解析 显然11a =，又2n >，所以2k >．我们证明2a 是质数．它是异于1、小于n 且和n 互质的最小正整数．如果2a 不是质数，则因为22a >，所以2a xy =，这里x 、y 都是大于1的正整数．既然2a 与n 互质，x 、y 也与n 互质，但21x a <<，这就和上述2a 的最小性矛盾．27.1.12** 考虑一个无限大的棋盘，棋盘的每个方格内有一个正整数．若方格中的每个数是其上下左右四个数的平均值．证明所有的数都相等．解析 若这些正整数不相等，设a 为其中的最小值，则必有某一块与含a 相邻且严格大于a ．又含a 方格中的a 等于与之相邻的4块的平均值，每块都不小于a ，有一块大于a ．这就得到一个矛盾． 27.1.13** 草场上有15个男孩在玩球，每人手上有一个球．任何两人的距离皆不相等．每个男孩把自己手里的球抛向距离自己最近的那个男孩． （1）证明：结果有一个男孩没有球； （2）证明：没有一个男孩得到的球超过5个．解析 （1）考虑其中距离最近的两个男孩A 、B ．他们互相交换了球．若还有其他人传球给他们，则由抽屉原理即证；否则可以忽略A 、B ，这时问题变为13人玩球．我们按照上面的方法同样讨论．因为共有奇数个人，最后一定剩下一人没有人传球给他．（2）若有6个或以上的男孩传球给同一个人O ，不妨设为A 、B 、C 、D 、E 、F ．则必有某一个角（不妨记为AOB ∠）小于60︒．这时AB 不会是OAB △的最长边，则OA 、OB 中某条是最长边，即A 、B 中一人不传球给O ．27.1.14*** 若干个人聚会，其中某些人彼此认识，已知如果某两人在聚会者中有相同数目的熟人，那么他俩便没有共同的熟人．证明：若聚会者中有人至少有2008个熟人，则必然也有人恰好有2008个熟人．解析 我们考虑（聚会者中）熟人最多的某个人（如果这样的人不止一个，那么任取其中一个），记为A ，设A 共认识n 个人，这些熟人依次记为1B ，2B ，…，n B ．由于1B ，2B ，…，n B 中任意两个人i B 与j B 都认识A ，即是他俩的共同熟人，因此（由题设推出）i B 与j B 的熟人数目不等．此外，1B ，2B ，…，n B 的熟人数目均不会超过n （这里用到了n 的“最大性”），于是他们的熟人数目恰好是1，2，…，n ．现在已知有人至少认识2008人，这意味着n ≥2008，所以数2008在上述数列中出现，于是1B ，2B ，…，n B 中恰好有人有2008个熟人．27.1.15**** 在圆周上任取21个点．证明：以这些点为端点的所有弧中，不超过120︒的弧不少于100条．解析 本题的出发点在于：圆上任意3点分圆而得的3段弧中至少有一段不超过120︒．为了便于识别，我们将不超过120︒的弧的端点连结成弦．只要证明这样的弦不少于100条．在所有的点中，不妨设以1A 为端点的弦数最小，且记以1A 为端点的弦为12A A ，13A A ，…，1n A A ，共1n -条，而以2A ，3A ，…，n A 为端点的弦都不少于1n -条．故这n 个点至少有()12n n -条．在其余的21n -个点中任取2个点i A 、j A （i j ≠，i ，1j n =+，2n +，…，21）．在三点组（1A ，i A ，j A ）中一定有一条弦．根据我们对1A 的取法，这条线不会是1i A A 、1j A A 而只能是弦i j A A ．所以在这21n-个点任意两点之间连有弦，共()()212112n n ---条．综上，总共有弦至少为 ()()()12121122n n n n y ----=+221210n n =-+ 22139924n ⎛⎫=-+ ⎪⎝⎭．所以当10n =或11时，y 取到最小值100．这就证明了不超过120︒的弧不少于100条．27.1.16*** 某个岛国的每条道路都是单行道，任两个城市之间恰有一条路．证明存在一个这样的城市，从另外每个城市或者可以直接到达该城市，或者可经过至多一个城市到达该城．解析 对每个城市，计算通到这个城市的单行线的条数，其中最大的记为m ，设M 是到达这个数的城市．记D 为有直路通到M 的城市的全体，设R 是除了M 和D 中城市外的其他城市的全体． 如果R 中没有任何城市，则结论当然成立；否则，不妨设X 为R 中的城市，则D 中的有某个城市E 使得道路X E M →→是通的．事实上，如若不然，则D 中所有城市都有直路通到X ，而且M 也直接通到X ．这样通到X 的直路至少有1m +条，这与我们对M 的假设矛盾．这样，所有进入的道路数达到最大的城市都满足题中的条件．评注 对于存在性有关的问题，极端原理解题时，有时实际是构造性的，并且常常与反证法结合着使用．27.1.17**** 有23个人，每人的体重都是偶数．他们想进行一场足球比赛，每队11人，剩下的人为裁判．为了公平起见，两个队队员体重之和要求相等．事实上，他们发现不论选谁做裁判，他们都能做到这一点．证明：这23个人的体重都相同．解析 对满足题意的23个数{1x ，2x ，…，23x }，当我们把每个数减去一个相同的数或者除以一个相同的数，所得的新数组仍然满足题意．若23人的体重满足条件，则称构成的数组{1x ，2x ，…，23x }为“平衡的”．设S 为23个数的和，若选取1x 为裁判，则1S x -一定是偶数，因为剩余的22名队员体重和能均分成两份．同理，2S x -，3S x -，…，23S x -也都是偶数．所以对于一个平衡的数组，其中的元素具有相同的奇偶性．下面我们证明，平衡数组的每个数都相等．设a 为其中的最小元素，定义i i b x a =-，则新集合{1b ，2b ，…，23b }也是平衡的且每个元素非负，其中某些元素是0．因为0是偶数，所以所有的数都是偶数．取2ii b c =，则{1c ，2c ，…，23c }同样含有一些0，是平衡的．因此，我们仍然可以把每个元素除以2得到新的平衡数组，而且我们可以一直这样做下去．只有0这个整数能够不断除以2且保持是一个整数．所以我们可以推断{1b ，2b ，…，23b }都是0．评注 本题证明中结合使用了奇偶分析和无穷递降法．使用无穷递降法会回到类似的情形． 27.1.18** 证明不定方程33324x y z +=没有正整数解（x ，y ，z ）．解析 假设方程有正整数解，设（1x ，1y ，1z ）是所有正整数解中使x 最小的一组解．由于 33311124x y z +=，所以31x 是偶数，故1x 是偶数．设122x x =，则333211824x y z +=，即33321142x y z +=， 故1y 是偶数．设122y y =，则333211482x y z +=，即33321124x y z +=， 故1z 是偶数．设122z z =，则333212248x y z +=．所以（2x ，2y ，2z ）也是方程的一组正整数解，且21x x <，矛盾． 所以原方程没有正整数解．27.1.19*** 设有n （n ≥7）个圆，其中任意3个圆都不两两相交（包括相切），求证：一定可以找到一个圆，它至多能与5个圆相交．解析 取半径最小的圆（如有多个，取其中一个即可）设为O ．若1O 与6个（或多于6个）的圆2O 、3O 、4O 、5O 、6O 、7O 相交，连结12O O ，13O O ，…，17O O ，则1∠，2∠，…，6∠中至少有一个不大于60︒．设213160O O O ∠=∠︒≤，连结23O O ，如图所示．O 7设1O 、2O 、3O 的半径为1R 、2R 、3R ，12R R ≤，13R R ≤．因为1O 、2O 相交，故连心距不超过两圆半径之和，即121223O O R R R R ++≤≤．同理 131323O O R R R R ++≤≤．又在123O O O △中，160∠︒≤，故在2O ∠、3O ∠中必有一个不小于60︒．设2601O ∠︒∠≥≥，则1323O O O O ≥，即2323R R O O +≥，所以2O 、3O 相交，从而1O 、2O 、3O 两两相交．与题设矛盾！27.1.20*** 空间中给出了8个点，其中任意4个点都不在同一平面上，在它们之间连以17条线段．证明：这些线段至少形成了一个三角形．解析 不妨设连出线段数目最多的点为A ，且设它共连出n 条线段．如果所有17条线段都没有形成三角形，那么与A 相连的n 个点之间彼此都没有线段相连，而其余的7n -个点中，每一点所连出的线段条数不多于n 条，因此，线段的总数目不超过()()2878162n n n n n n n +-⎛⎫+-=-= ⎪⎝⎭≤．这与已知的有17条线段矛盾．从而命题成立．评注 其实本题的结论可加强为“三角形的数目不少于4个”，这个问题较难，留给有兴趣的读者思考． 27.1.21**** 在2×n 方格表的每个方格中都写有一个正数，使得每一列中的两个数的和都等于1．证明：可以自每一列中删去一个数，使得每一行中剩下的数的和都不超过14n +． 解析 假设第一行中所放的数为1a ，2a ，…，n a ．必要时通过交换列的位置，可以使得1a ≤2a ≤…≤n a ，此时第二行中所写的数就依次分别为111b a =-，221b a =-，…，1n n b a =-．显然1b ≥2b ≥…≥n b ．如果1214n n a a a +⋯+++≤，那么就删去第二行中的所有各数即可达到目的．否则，我们可以找到使得1214k n a a a +⋯+++>成立的最小的k ．此时我们在第一行中删去k a ，1k a +，…，n a ，在第二行中删去1b ，2b ，…，1k b -由k 的取法，立知12114k n a a a -+⋯+++≤，下面只需证明 114k k n n b b b ++⋯+++≤． 由于1214k k a a a n a k k ⋯++++>≥， 所以1k k n b b b +⋯+++()()()111k k n k b n k a +-=+--≤()()()()221114125144n n k k n k n k+⎛⎫+-- ⎪⎝⎭-+=+-≤()()()212511444n k n n k +++-=≤． 27.1.22*** 平面上有n （>2）个点，它们两两连线都有一个中点，如果重合的中点算一个点，求证：至少有23n -个不同的中点．解析 不妨设n 个点为1A ，2A ，…，n A ．且1n A -、n A 为最远两点，记1i n A A -中点为i B （i =1，2，…，2n -），i n A A 中点为i B '（i =1，2，…，2n -）． 不存在一个i 与j ，使i j B B '=，否则当i B 不在线段1n n A A -上时，作平行四边形1n n i j A A A A -，不妨设190i n n A A A -∠︒≥，于是11n i n n A A A A -->，这与1n n A A -定义矛盾．A iA jA nA n -1B i当i B 在1n n A A -亦然．于是全部i B 与j B '一共有24n -个中点，加上1n n A A -中点，至少有23n -个不同中点，读者不难构 造出达到此界的例子．27.1.23**** 设正整数a 、b 、k 满足221a b k ab +=-，求证：5k =．解析 对每一个k ，如果有这样的a 、b 存在，可设a b +最小，且a b ≥．a b =时，2221k a =+-，无解，故a b >．关于a 的方程220a bka b k -++=有另一根a '，由两根和知a '为整数，由两根积知a '为正数，故a '为正整数，于是a a '≥，或 22a aa b k '=+≤，即()2222121k a b a a a ---=-≥≥．当1b =时，212111a k a a a +==++--，2a =或3，5k =．当2b ≥时，()()222222121441a a b k ab a a a >+=--=-+≥，故22410a a -+<或()2211a -<，不可能．综上所述，5k =．27.1.24**** 已知正整数a 与b 使得1ab +整除22a b +，求证：221a b ab ++是某个正整数的平方． 解析 用反证法．假设221a b ab ++并不是某个正整数的平方．令 221a b k ab +=+， 220a b kab k +--=．所以，（a ，b ）是方程220x y kxy k +--= ①的一组正整数解．设（1a ，1b ）是方程①的所有正整数解中，使x y +为最小的一组解，由对称性不妨设11a b ≥． 把①改写成关于x 的二次方程，得()22110x kb x b k -+-=． ②于是1a 就是②的一个正整数解．由韦达定理知②的另一个解211a kb a =-也是整数，由2211a a b k =-知20a ≠（因为k 不是平方数），若20a <，则 222121120a kb a b k kb a k k k -+->---=≥，矛盾．故2a >0．于是（2a ，1b ）也是方程①的一组正整数解．但是由2222111121111111b k b a a a a a a a a ---=<<=≤， 得2111a b a b +<+．这与11a b +为最小相矛盾．因此愚为某个正整数的平方．。