高二数学竞赛班讲义组合.doc

1高一数学竞赛班二试 第二讲 抽屉原理染色方法班级 姓名 一、知识要点：1．第 I 型抽屉原理 把 个物体放入 个抽屉，则至少有一个抽屉的物品不少于 个，其中mn l,|1,|ln2．第 II 型抽屉原理 把 个物体放入 个抽屉，则至少有一个抽屉的物品不多于 个，其中mlmln3．运用抽屉原理的关键是构造恰当的“抽屉”和“物品”二、经典例题例 1．（1953 年美国普特南数学竞赛题）空间六点，任三点不共线，任四点不共面，成对地连接它们得十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色）.求证：无论怎样染，总存在同色三角形例 2．(第 6 届国际数学奥林匹克试题 )有 17 位科学家，其中每一个人和其他所有人的都通信，他们的通信中只讨论三个题目中的一个求证：至少有三个科学家相互之间讨论同一个题目.2例 3．（首届全国中学生数学冬令营试题）能否把 1，1，2，2，3，3，…，1986，1986 这些数排成一行，使得两个 1 之间夹着一个数，两个 2 之间夹着两个数，…，两个 1986、之间夹着一千九百八十六个数？请证明你的结论.例 4．（2010 年联赛加试第四题）（本题满分 50 分）一种密码锁的密码设置是在正 边形n的每个顶点处赋值 和 两个数中的一个，同时在每个顶点处涂红、蓝两种颜色12nA 01之一，使得任意相邻的两个顶点的数字或颜色中至少有一个相同。

问：该种密码锁共有多少种不同的密码设置？3二、精选习题1．有九名数学家，每人至多会讲三种语言，每三名中至少有 2 名能通话，那么其中必有 3名能用同一种语言通话.2．如果把上题中的条件 9 名改为 8 名数学家，那么，这个结论还成立吗？为什么？3．（1966 年波兰数学竞赛题）大厅中会聚了 100 个客人，他们中每人至少认识 67 人，证明在这些客人中一定可以找到 4 人，他们之中任何两人都彼此相识.44． （首届全国数学冬令营试题）用任意方式给平面上的每一个点染上黑色或白色.求证：一定存在一个边长为 1 或 的正三角形，它三个顶点是同色的.5．对平面上一个点，任意染上红、蓝、黑三种颜色中的一种证明：平面内存在端点同色的单位线段6．设 为实数，满足 ，求证：对于每一个整数 ，存在12,nx2211nxx2k不全为零的整数 ，使得 ，并且 12,na (,)iaki1()1ninax5第二讲 抽屉原理例 1．证明 设 A、B、C、D、E、F 是所给六点.考虑以 A 为端点的线段AB、AC、AD、AE、AF ，由抽屉原则这五条线段中至少有三条颜色相同，不妨设就是AB、AC、AD，且它们都染成红色.再来看△BCD 的三边，如其中有一条边例如 BC 是红色的，则同色三角形已出现（红色△ABC）；如△BCD 三边都不是红色的，则它就是蓝色的三角形，同色三角形也现了.总之,不论在哪种情况下,都存在同色三角形.如果将例 4 中的六个人看成例 5 中六点,两人认识的连红线,不认识的连蓝线,则例 4 就变成了例 5.例 5 的证明实际上用染色方法给出了例 4 的证明.例 2． (第 6 届国际数学奥林匹克试题)有 17 位科学家,其中每一个人和其他所有人的人通信,他们的通信中只讨论三个题目.求证:至少有三个科学家相互之间讨论同一个题目.证明 用平面上无三点共线的 17 个点 A1,A2,…，A 17 分别表示 17 位科学家.设他们讨论的题目为 x,y,z,两位科学家讨论 x 连红线,讨论 y 连蓝线,讨论 z 连黄线.于是只须证明以这 17 个点为顶点的三角形中有一同色三角形.考虑以 A1 为端点的线段 A1A2,A1A3,…，A 1A17，由抽屉原则这 16 条线段中至少有6 条同色，不妨设 A1A2，A 1A3，…，A 1A7 为红色.现考查连结六点A2，A 3，…，A 7 的 15 条线段，如其中至少有一条红色线段，则同色（红色）三角形已出现；如没有红色线段，则这 15 条线段只有蓝色和黄色，由例 5 知一定存在以这 15 条线段中某三条为边的同色三角形（蓝色或黄色）.问题得证.上述三例同属图论中的接姆赛问题.在图论中,将 n 点中每两点都用线段相连所得的图形叫做 n 点完全图,记作 kn.这些点叫做“顶点” ，这些线段叫做“边”. 现在我们分别用图论的语言来叙述例 5、例 6.定理 1 若在 k6 中，任染红、蓝两色，则必有一只同色三角形.定理 2 在 k17 中,任染红、蓝、黄三角，则必有一只同色三角形.（2）点染色.先看离散的有限个点的情况.例 3．（首届全国中学生数学冬令营试题）能否把1，1，2，2，3，3，…，1986，1986 这些数排成一行，使得两个 1 之间夹着一个数，两个 2 之间夹着两个数，…，两个 1986、之间夹着一千九百八十六个数？请证明你的结论.证明 将 1986×2 个位置按奇数位着白色，偶数位着黑色染色，于是黑白点各有1986 个.6现令一个偶数占据一个黑点和一个白色，同一个奇数要么都占黑点，要么都占白点.于是 993 个偶数，占据白点 A1=993 个，黑色 B1=993 个 .993 个奇数，占据白点 A2=2a 个，黑点 B2=2b 个，其中 a+b=993.因此，共占白色 A=A1+A2=993+2a 个.黑点 B=B1+B2=993+2b 个，由于 a+b=993（非偶数！）∴a≠b，从而得 A≠B.这与黑、白点各有 1986 个矛盾.故这种排法不可能.“点”可以是有限个，也可以是无限个，这时染色问题总是与相应的几何问题联系在一起的.例 4．71．把９名数学家用点Ａ １ ，Ａ ２ ，…，Ａ ９ 表示．两人能通话，就用线连结，并涂某种颜色，以表示不同语种。

两人不通话，就不连线．（１）果任两点都有连线并涂有颜色，那么必有一点如Ａ １ ，以其为一端点的８条线段中至少有两条同色，比如Ａ １ Ａ ２ 、Ａ １ Ａ ３ ．可见Ａ １ ，Ａ ２ ，Ａ ３ 之间可用同一语言通话．②如情况①不发生，则至少有两点不连线，比如Ａ １ 、Ａ ２ ．由题设任三点必有一条连8线知，其余七点必与Ａ １ 或Ａ ２ 有连线．这时七条线中，必有四条是从某一点如Ａ １ 引出的．而这四条线中又必有二条同色，则问题得证．2．结论不成立，如图所示（图中每条线旁都有一个数字，以表示不同语种）．3．用点Ａ １ 、Ａ ２ 、…、Ａ １００ 表示客人，红、蓝的连线分别表示两人相识或不相识，因为由一个顶点引出的蓝色的线段最多有３２条，所以其中至少有三点之间连红线．这三个点（设为Ａ １ 、Ａ ２ 、Ａ ３ ）引出的蓝色线段最多为９６条．去掉所有这些蓝色的线段（连同每条线段上的一个端点Ａ Ｉ ，Ｉ≠１，２，３），这样，在图中至少还剩下四个点，除Ａ １ 、Ａ ２ 、Ａ ３ 外，设第四点为Ａ ４ ，这四个点中Ａ １ ，Ａ ２ ，Ａ ３ 每一个点与其它的点都以红色的线段相连，于是客人Ａ １ 、Ａ ２ 、Ａ ３ 、Ａ ４ 彼此两两相识．4．先利用右图证明＂若平面上有两个异色的点距离为２，地么必定可以找到符合题意的三角形＂．再找长为２端点异色的线段．以Ｏ（白色）为圆心，４为半径作圆．如圆内皆白点，问题已证．否则圆内有一黑点Ｐ，以ＯＰ为底作腰长为２的三角形ＯＰＲ，则Ｒ至少与Ｏ、Ｐ中一点异色，这样的线段找到．5．证明 作出一个如图 29-7 的几何图形是可能的,其中△ABD、△CBD、△AEF、△GEF 都是边长为 1 的等边三角形，CG=1.不妨设 A 点是红色，如果 B、E、D、F 中有红色，问题显然得证.当 B、 E、D、F 都为蓝点或黄点时，又如果 B 和 D 或 E 和 F 同色，问题也得证.现设 B和 D 异色 E 和 F 异色,在这种情况下,如果 C 或 G 为黄色或蓝点,则 CB、CD、GE 、GF 中有两条是端点同色的单位线段，问题也得证.不然的话,C、G 均为红点，这时 CG是端点同色的单位线段.证毕.6．由柯西不等式易得 ，因此当 时，有12nxx01iak12()naxak将区间 等分成 个小区间，每个小区间的长度为 。

0,()kn ()nk由于每个 能取 个整数，因此 共有 个正数由抽屉原i 12nxax理知必存在两个数落在同一个小区间内，设它们分别是 和 ，则有1ia1ix1()()1niiini kax9又 ， ，取 ，于是1iiak,2in (0)iiiiiax1()ninx。