组合数学第二讲 抽屉原理

《组合数学第二讲 抽屉原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、组合数学第二讲抽屉原理的其他应用形式一、单色三角形问题　　前面数例我们看到，抽屉原理应用的关键在于恰当地制造抽屉，分割图形，利用自然数分类的不同方法如按剩余类制造抽屉或按奇数乘以2的方幂制造抽屉，利用奇偶性等等，都是制造“抽屉”的方法。大家看到，抽屉原理的道理极其简单，但恰当地精心地应用它，不仅可以解决国内数学竞赛中的问题，而且可以解决国际中学生数学竞赛，例如IM0中的难题。　　例1．（第6届国际中学生数学奥林匹克试题）17名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个

2、题目，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个题目。证明：视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。考虑科学家A，他要与另外的16位科学家每人通信讨论一个问题，相应于从A出发引出16条线段，将它们染成3种颜色，而16=3×5+1，因而必有6=5+1条同色，不妨记为AB1，AB2，AB3，AB4，AB5，AB

3、6同红色，若Bi（i=1，2，…，6）之间有红线，则出现红色三角线，命题已成立；否则B1，B2，B3，B4，B5，B6之间的连线只染有黄蓝两色。　　考虑从B1引出的5条线，B1B2，B1B3，B1B4，B1B5，B1B6，用两种颜色染色，因为5=2×2+1，故必有3=2+1条线段同色，假设为黄色，并记它们为B1B2，B1B3，B1B4。这时若B2，B3，B4之间有黄线，则有黄色三角形，命题也成立，若B2，B3，B4，之间无黄线，则△B2，B3，B4，必为蓝色三角形，命题仍然成立。　　说明：（1）本题源于一个古典问题--世界上任意

4、6个人中必有3人互相认识，或互相不认识。（美国普特南数学竞赛题）。　　（2）将互相认识用红色表示，将互相不认识用蓝色表示，（1）将化为一个染色问题，成为一个图论问题：空间六个点，任何三点不共线，四点不共面，每两点之间连线都涂上红色或蓝色。求证：存在三点，它们所成的三角形三边同色。　　（3）问题（2）可以往两个方向推广：其一是颜色的种数，其二是点数。　　本例便是方向一的进展，其证明已知上述。如果继续沿此方向前进，可有下题：　　在66个科学家中，每个科学家都和其他科学家通信，在他们的通信中仅仅讨论四个题目，而任何两个科学家之间仅仅讨

5、论一个题目。证明至少有三个科学家，他们互相之间讨论同一个题目。　　（4）回顾上面证明过程，对于17点染3色问题可归结为6点染2色问题，又可归结为3点染一色问题。反过来，我们可以继续推广。从以上（3，1）→（6，2）→（17，3）的过程，易发现　　6=（3-1）×2+2，17=（6-1）×3+2，66=（17-1）×4+2，　　同理可得（66-1）×5+2=327，（327-1）×6+2=1958…记为r1=3，r2=6，r3=17，r4=66，r5=327，r6=1958，…　　我们可以得到递推关系式：rn=n(rn-1-1)+

6、2，n=2,3,4…这样就可以构造出327点染5色问题，1958点染6色问题，都必出现一个同色三角形。二、抽屉原理的其他形式　　在例7的证明过程中，我们实际上用到了抽屉原理的其他形式，我们把它作为定理2。　　定理2：把m个元素分成n个集合（m＞n）　　（1）当n能整除m时，至少有一个集合含有个元素；　　（2）当n不能整除m时，则至少有一个集合含有至少个元素。　　定理2有时候也可叙述成：把m×n+1个元素放进n个集合，则必有一个集合中至少放有m+1个元素。　　例2．在边长为1的正方形内任意放入九个点，求证：存在三个点，以这三个点为

7、顶点的三角形的面积不超过（北京市数学竞赛题）。分析与解答：如图，四等分正方形，得到A1，A2，A3，A4四个矩形。在正方形内任意放入九个点，则至少有一个矩形Ai内存在个或3个以上的点，设三点为A、B、C，具体考察Ai（如图所示），过A、B、C三点分别作矩形长边的平行线，过A点的平行线交BC于A'点，A点到矩形长边的距离为h=(0≤h≤)，则△ABC的面积　　说明：把正方形分成四个区域，可以得出“至少有一个区域内有3个点”的结论，这就为确定三角形面积的取值范围打下了基础。本题构造“抽屉”的办法不是唯一的，还可以将正方形等分成边长为

8、的四个小正方形等。但是如将正方形等分成四个全等的小三角形却是不可行的（想一想为什么？）。所以适当地构造“抽屉”，正是应用抽屉原则解决问题的关键所在。以下两个题目可以看作是本例的推广：　　（1）在边长为2的正方形内，随意放置9个点，证明：必有3个点，以它们为顶点的