课件40张PPT。第五讲 抽屉原则（二）一．用数组构造抽屉 例1．在1、4、7、10、……、100中任取20个不同的数组成一组，证明这样的任意一组数中必有不同的两对数，其和都是104.证明：把所给的数分成如下18个不相交的数组： {4、100}、{7、97}、{10、94}、……、{49、55}、{1}、{52}。 把每一组数看作是一个“抽屉”，当任意取出20 个整数时，若取到1和52，则剩下的18个数，一定取自前16个“抽屉”。 这样至少有4个数取自某两个“抽屉”中，若1和52没有全被取出，则有多于18个数取自前16个“抽屉”中，同样至少有4个数取自某两个“抽屉”中。 而前16个“抽屉”中的任一“抽屉”的两个数之和为104。说明：题目中没有现成的东西可看作“抽屉”。我们把和为104的两个数组成的数组看作“抽屉”。 这种根据问题的要求构造“抽屉”的方法少经常要用到的。 还应注意，本题中“抽屉”的容量是有限的，解题时要根据所给的条件进行具体的分析。例2．夏令营组织2017名营员去游览故宫、景山公园和北海公园，规定每人必须去一处，最多去两处游览，那么至少有多少人游览的地方完全相同？解：首先要弄清楚一共有多少种不同的游览情况，并把它们表示出来。 为此，设某人游览某处记作“1”，没有去某处记作“0”。并用有序数组{a，b，c}表示某人游览的情况。 a=1表示去了故宫，a=0表示没有去故宫；b=1表示去了景山，b=0表示没有去景山；c=1表示去了北海，c=0表示没有去北海。 例如{1，1，0}表示某人去了故宫个景山，而没有去北海。 由于每人必须去一处，且最多去两处，所以又来的不同的情况共有6种可能： {1，1，0}，{1，0，1}，{0，1，1}，{1，0，0}，{0，1，0}，{0，0，1}。 这样我们就可以把这六种情况看作是六个“抽屉”，由于2017>2016=6×336+1， 根据抽屉原则二，至少有337人游览的地方相同。例3．把1、2、3、……、10这10个自然数按任意顺序排成一圈，求证：在这一圈数中一定有相邻的三个数之和大于17.证明：无论依怎样的顺序，把1、2、3、……、10这10个自然数摆成一圈， 总能先找到1的位置，然后按逆时针方向，把其他的数依次表示为a2，a3，a4, ……, a10。 对任意一种摆法，都把以上九个数分成三组(a2，a3，a4)；(a5，a6，a7)；(a8，a9，a10)。 把这三组数看作是三个“抽屉”，又根据加法的交换律、结合律，可以得到下面的等式： (a2+a3+a4)+(a5+a6+a7)+(a8+a9+a10) =2+3+4+……+10=54. 而54>51=17×3。根据抽屉原则二， 一定有一个抽屉中的三个数之和大于17，它们恰好是位置相邻的三个数。二．用剖分图形构造“抽屉” 例4．已知在边长为1的等边三角形内（包括边界），任意点了五个点，求证：至少有两个点之间的距离不大于二分之一。证明：如图，等边三角形ABC的三边中点为E、F、G， 这样EF、FG、GE把边长为1的等边三角形ABC分成了4个边长为二分之一的等边三角形。 如果规定EF、FG、GE上的点属于△EFG， 那么△ABC内的点被划分为四个不相交的区域。把每个区域看作是一个“抽屉”， 在△ABC内任意画五个点，根据抽屉原则，必有两个点放入同一抽屉中。 也就是一定有一个边长为二分之一的三角形，其中包含两个点。 显然这两个点的距离不超过二分之一。例5．如果在一个边长为1的正方形中，任意放入九个点，则至少存在三个点，其所构成的三角形的面积不超过八分之一。解：如图一，将边长为1的正方形分成四个面积都是四分之一的长方形G1、G2、G3、G4，图一 在正方形内任意放入九个点，由于9>2×4， 根据抽屉原则，至少有一个长方形内包含三个或三个以上的点。 只要证明以这三个点为顶点的三角形的面积不大于小长方形面积的一半就行了。 设一个小长方形DEFG内有三个点A、B、C（如图二）， 如果这三个点在一条直线上，结论显然是对的。图二 设过 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
