PAGE
PAGE 1
第一讲 极端原理
纵观整个数学历史的发展过程，人们在生产生活和社会实践中，不断地提出自己的猜想，然后努力对提出的猜想加以印证，在一个一个的数学问题不断被解决的过程中，一种种新的思维方式不断的诞生了，从而在一方面推动了社会的进步，另一方面也促进了人们思维品质的提高。我们在解决数学竞赛问题的时候，往往也需要从多侧面，多角度进行思考。
1893年，数学家塞尔维斯特提出猜想：有限点集N中含n个元素,其中n≥3，所含点不都在同一直线上，则必有一条直线只过点集中的两个点。为了这一猜想的圆满证明，人们经历了一个漫长的过程，直到1933年，数学家伽莱才给出了对这一问题较为完整的一个证明。但还是显得很麻烦。又50年过去了，人们终于找到了一种简单明确的证明方法，使这一问题得到了圆满的解决，这就是极端原理。
例一：有限点集N中含n个元素,其中n≥3，所含点不都在同一直线上，试证有一条直线只过点集中的两个点。
P证明：任取一条直线过点集中不只一点，则点集中还有有限个不在该直线上的点，在这有限个点中，总有一点到该直线的距离小于或等于其他各点到该直线的距离，我们取这一点和这条直线作一个点线对的组合，可知这样的组合有有限个，找到其中点线距最小的一组，在这一组中的直线必定只过两点。
P
若上述直线过三点P1、P2、P3，点P为到该直
线距离最近的点，将点P与P1、P2、P3中距离
最远的点相连则剩下的两点中必有一点到所连
P3P2
P3
P2
P1
如图所示：
例二：有十六个城市参加的足球邀请赛，每一市都派出甲、乙两队参赛，规则规定，同一城市的两队之间不进行比赛，不同城市的两队之间最多比赛一场，比赛若干天后，经统计发现，除A市的甲队外，其他各队已比赛过的场次各不相同，问A市的乙队已赛过多少场？
分析：①共32只球队，某队最多可赛30场
②统计了31只球队，31只球队比赛的场次分别为0、1、2、3、……、30
③运用极端原理的思想对31只已统计的球队进行配对
解：将已赛过K场的球队记为：L（K），则L（30）已赛过自己该赛的每一场，即与它不同城市的30个队均赛过至少一场；则L（30）与L（0）来自同一城市，同理，L（29）与L（1）来自同一城市，……,L(16)与L(14)来自同一城市,因此L(15)必为A市乙队,于是可知, A市乙队已赛15场.
例三：试证：任意四面体中，一定可以找到一个顶点，使从这个顶点出发的三条棱可以组成一个三角形的三条边。
A分析：运用极端原理的思想，先找到六条棱中最长的一条记为AB
A
在已有三角形中：AB＜AD+BD
AB＜AC+BC
DB两式相加： 2AB＜（AD+AC）+（BD+BC）
D
B
C故：AB＜AD+AC或AB＜BC+BD
C
另外，因为AB为最长边，显然有两边之差小于第三边。
以上两式总有一个能够成立，即总可以构成三角形。
例四：在2×5的数表中，第一行各格内分别填入数字0、1、2、3、4，请在第二行的五个空格中各填入一数，使得你所填的数是上一行中对应格内的数在下一行中出现的次数。
0
1
2
3
4
分析：⑴在下一行中共五个空格，所有数字出现的次数之和应等于5，即第二行的数字之和为5。
⑵运用极端原理的思想，考虑第一行中影响最大的应为数字4，其出现的次数只能是0，然后类推。
于是可得本题的最终填法如下：
0
1
2
3
4
2
1
2
0
0
本例还可以扩充，有兴趣的同学可自己尝试。
例五： n× n的正方形棋盘内，放置棋子满足以下条件：
⑴棋子放在小格内，每小格最多放一枚棋子。
⑵若某小格内没放棋子，则这一小格所在的横行和竖列其他小格所放棋子数的和不少于n。
求证：整个棋盘内所放棋子数的和不少于个。
分析：运用极端原理的思想，n行n列中总能找到一行或一列所放棋子数不少于其它行或列所放棋子数，设满足条件的那一行共有K个棋子，那么该行一共有n-K个空格，与每个空格相对的纵列中最少含棋子n-K个，故共有（n-K）2个，和此行含有棋子的K个格子相对应的各列所含棋子数最少K个，故共有K2个，于是得到，整个棋盘所含棋子的总和不少于
（n-K）2+ K2个。
由不等式的平方关系重要不等式得：≥
所以：≥=
即: .
例六：对于x、y、z、u的方程：x2+y2=3（z2+u2），试证：此方程无非零整数解。
证明：设（a,b,c,d）是原方程的一组能使x2+y2最小的解，即：
a2+b2=3（c2+d2）
故：3∣（a2+b2） ＜＝＞ 3∣a2 且 3∣b2, 其理由如下：
若a2、 b2均能被3整除，则显然a2+b2能被3整除，
若a2、 b2有一数不能被3整除，则显然a2+b2不能被3整除，
若a2、 b2均不能被3整除，因为a、b为整数，则等价于a、b均不能被3整除。事实上，若任一整数不能被3整除，即除以3余1或余2，在此两种情况下，平方后均被3整除余1，则显然a2+b2能被3整除。
所以上诉结论成立。即a、b均能被3整除。于是可设a=3m、b=3n,则：
9（m2+n2）=3（c2+d2）
∴ c2+d2=3（m2+n2）
∴ (c,d,m,n)是原方程的另一组解，
又： a2+b2＞c2+d2
故与题设相矛盾，于是假定不成立，则原方程无非零实数解。
例七：在一次乒乓球邀请赛中n（ n≥3）名选手中没有全胜者，试证：一定存在选手A、B、C。使得A胜B、B胜C、C胜A。
证明：从寻找极端元素着手，设所有选手中A获胜的场数最多。因为没有全胜选手，所以必有一个选手胜A，不妨设为C，而于所有被A击败的选手中必有一人胜C，记为B，于是题目要求得以满足。
若上述假定不能成立，即所有被A击败的选手均也被C击败，那么选手C与选手A相比必定多胜一场（C胜A），这与假定A获胜的场数最多相矛盾。所以原命题成立。
例八：n（ n≥3）名乒乓球选手进行单打比赛，若干场后，任意两名选手一赛过的对手恰好都不完全相同。试证：总可以从中去掉一名选手而使余下的选手中任意两名选手已赛过的对手恰好都不完全相同。
分析:若上述结论不成立,即所有选手都不能去掉.比如若去掉A,则选手B与C对手完全相同,也就是说,选手B与C除A外,赛过的对手一样.于是可从极端情况加以分析.
证明:设选手A是所有参赛选手中比赛场数最多的选手.若不存在可去选手,则A不可去,即若去掉A,则余下必有两名选手对手相同,不妨设为B、C。也就是说，B与C除A外对手完全相同，不妨设B与A赛过而C与A没赛。又因为C也是不可去选手，同理，即若去掉选手C则会有两名选手对手完全相同，不妨设为D和E，其中D与C赛过而E与C没赛过。下面我们来分析选手A与E。
因为选手B与C除对手A外，赛过的对手完全相同，既然选手C与D赛过，那么B与D也赛过，选手D与E除C外对手完全相同，故选手E与B赛过。再看选手A与E，均为与B赛过而与C没赛过的选手。又因为选手B与C的唯一区别就是有且只有一个选手A与B赛过与C没赛过，所以A与E为同一个人，于是与假定中的一条相矛盾，在有有限个选手的比赛中,总可以找到一个选手,其比赛场数大于或等于其他选手.故只能是假定没有可去选手是错误的.即原命题成立.
例九：某次会议有A、B两个代表团参加，现知每位B团的成员都至少与A团的一位成员握过手，而A团中的任何人都没有与B团中的所有成员握过手。试证：一定可以从A团中找到两人a1、a2，从B团中找到两人b1、b2,使得a1与b1，a2与b2握过手，而a1与b2，a2与b1没握过手。（加拿大预选）
证明：于A团中总能找到一个成员与B团中的成员握手次数最多，记为a1，将B团中的人员分为两个部分，将与a1握过手的B团成员组成的集合记为B1，没与a1握过手的B团成员组成的集合记为B2，则B1 B、 B2 B。于是取， b2 B2。据题意可知，成员b2至少与A团中的一人握过手，取其中一人记为a2，如果B1中的所有成员都与a2握过手，那么与a1是A团中与B团中的成员握手次数最多的人相矛盾，所以，在集合B1中必定可以找到一人没与a2握过手，记为b1，即有b1 B1.于是原题意得以满足。