组合数学（3）

——极端原理与反证法 姓名____________ 极端原理：

第一题组

例1、在平面上给定点集M,若M中每个点都是M中某两点连线的中点，证明点集M必为无限集.

例2、对平面上不全共线的n个点，求证必存在一条恰好通过两点的直线.

n2例3、n个点它们之间至少有[]?1条连线，至少有一个三角形.

4

1

例4、一组砝码具有如下性质：

（1） 其中有5个砝码的质量各不相同；

（2） 对于任何2个砝码，都可以找到另外2个砝码，它们质量之和相等. 问这组砝码至少多少个？

例5、证明不定方程x2?y2?3(u2?v2)无正整数解.

a2?b3例6、已知正整数a和b，使得ab?1|a?b，求证是完全平方数.

ab?122

2

例7、n(n?3)名乒乓球选手单打比赛若干场后，任意两名选手已赛过的对手恰好都不完全相同，求证：总可以从中去掉一名选手，使在余下的选手中，任意两个选手已赛过的对手仍然都不完全相同.

例8、有三所学校，每所学校有n名学生，已知任意1名学生认识其他两所学校学生的总数都是n?1，证明：每所学校都存在一名学生，使得这3名学生互相都认识.

3

例9、现有2n?1条线段在同一直线上，且每条线段都至少与其余线段中n条线段有公共内点.证明：存在一条线段与其余所有2n条线段都有公共内点.

例10、在学校足球比赛中，要求每一个队都必须同其余各队进行一场比赛，每场比赛胜队得2分，平局各得1分，负队得0分.已知有一队对分最多（其余每队得分都比这队少），但它胜的场次比任何一队都少，问最少有多少队参赛？

4

第二题组

例11、在直角坐标平面内给定凸五边形ABCDE，它的顶点都是整点，证明：其对角线相交成的凸五边形A1B1C1D1E1的内部或周界上至少有一个整点.

例12、将一个?ABC的三个顶点分别涂上红、蓝、黑三色之一，在?ABC内任取若干点，并用线段将这些点及A、B、C三点连接起来，使?ABC全部分成以这些点及A、B、C为顶点的三角形.再将每个小三角形的顶点任意涂上红、蓝、黑三色之一.证明：不管怎样涂色，总存在一个三角形，它的三个顶点处涂的颜色互不相同.

…… 此处隐藏0字 ……

5

例13、2004位女孩围着一张圆桌，玩一副有2004张牌的游戏，开始时，女孩甲手中拿着所有的牌，如果至少有一位女孩手中拿的牌多于一张，那么这些女孩中必须有一人把她手中的牌分给左邻和右邻个一张，当且仅当每位女孩手中都恰好拿着一张牌时，游戏结束.

证明：这个游戏不可能结束.

例14、设A1,A2,…，A2004是圆周上依次排列的2004个点，最初A1上标的数为0，A2,…，A2004上标的数为1，允许进行如下操作：任取一点Aj，若Aj上所标的数为1，则同时将Aj-1，Aj，Aj+1上标的数a，b，c分别改为1-a，1-b，1-c.（这时A0=A2004,A2005=A1）问能否经过有限次这样的操作将所有的点上标的数都变为0？

6