抽屉原则二
摘要:第五讲抽屉原则（二）一．用数组构造抽屉例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，
温馨提示：当前文档最多只能预览
5 页，若文档总页数超出了
5 页，请下载原文档以浏览全部内容。
本文档由 匿名用户 于 2020-11-07 05:51:51上传分享
46--抽屉原理
