0811市政西南设计研究院管理诊断报告摘要版

第十二讲抽屉原理（二）模块一、最不利原则：例1．现有一个袋子，里面装有18种不同颜色的玻璃球，每种颜色的玻璃球各有40个，则在这个袋子中至少要取出个玻璃球，才能保证取出的球至少有三种颜色，且每种颜色的球都至少有10个。解：这18种颜色的球中有二种颜色的球都取出来，为40×2=80个，其余各种颜色的球都取出9个，为16×9=144个，这时再从中任意取出1个球就能保证满足条件。所以至少要取出80+144+1=225个球。例2．一个袋子中共有45个球，其中标注1的有1个2的有2个，3的有3个，…，标注9的有9个，那么最少取出个球才能保证取出来的球中必有两个球的编号相差2.解：把编号为9和8的球都取出来有9+8=17个，再取编号为5和4的球，有5+4=9个，再取编号为1的1个球，现在已经有17+9+1=27个球，再任意取一个球，能保证必有2个球的编号相差2，所以最少取出27+1=28个球。例3．某商店举行抽奖活动，在箱子里放有红色、蓝色、黄色小球各100个，若50个同色小球可以换一共布偶，80个同色小球可以换一个零食包，且每个小球只能换一次奖，小明去抽奖，每次只能从箱子中不放回地随机抽取一个小球，他最少需要抽取次才能保证他可以换到两种奖品各一个。解：小明取出三种颜色的球都是79个，再任取1个球，即共抽取79×3+1=238次能保证可以换到两种奖品各一个。模块二、构造抽屉进阶：例4．（1）证明：在边长为3的等边三角形中任意放入10个点，其中至少有2个点的距离不大于1.（2）如图，将每一个小方格涂上红色、黄色或蓝色（每一列三个小方格涂的颜色均不相同），证明：不论如何涂色，其中至少有两列，它们的涂色方法相同。解：（1）如图，将边长为3的等边三角形分成9个小三角形，每个小三角形的边长为1，将10个点放入9个三角形中，根据抽屉原理，一定有一个三角形中有2个点，这两个点之间的距离不大于1.（2）用红、黄、蓝三种颜色来染色，在一列中有336A种不同的的排列顺序，现在一共有7列，用6种方法来染色，根据抽屉原理，一定有两列是用同一种排列顺序来染色的。例5．有22个装乒乓球的盒子，装球最多的盒子中装有x个乒乓球，如果不论怎么装都至少有4个盒子的乒乓球数相同（不装算0个），那么x的最大值为。解：如果分别有3个盒子装0个，1个，2个，3个，4个，5个，6个，现在已经装了3×7=21个盒子，取x=6，第22个盒子装的球的个数不大于6，那么就至少有4个盒子的乒乓球数相同。例6．（1）请说明：在任意的68个自然数中必有两个数的差是67的倍数。（2）请说明：在1、11、111、1111、…，这一列数中必有一个是67的倍数。（3）从1、2、3、4、…、1988、1989这些自然数中，最多可以取个数，其中每两个数的差不等于4.解：（1）67是一个质数，按一个自然数除以67的余数来分类，即余数分别为0、1、2、3、…、66，共有67种分法，把68个数分到这67个类别中，有一个类别中至少有2个数，这两个数的差是67的倍数；（2）由（1）知道任意68个数中必有两个数的差是67的倍数，现在取1、11、111、1111、…、6811111个，在这68个数中必有两个数的差是67的倍数，不妨设这两个数是11111m个，11111n个(mn)，即11111m个−11111n个=111110000mnn个个0是67的倍数，而111110000mnn个个0=11111mn个×10000n个0，其中10000n个0与67互质，所以11111mn个是67的倍数。（3）1989÷4=497……1，把1、2、3、4、5、6、7、8、9、10、…、1987、1988、1989，每4个分成一组，即(1、2、3、4)；(5、6、7、8)；(9、10、11、12)；…、(1985、1986、1987、1988)，1989一共有497组，和最后一个数1989，从(1、2、3、4)开始，隔一组取一组，一共取出249组，最后一个1989不取：即(1、2、3、4)；(9、10、11、12)；…；(1985、1986、1987、1988)，，一共有249×4=996个数，这些数中每两个数的差都不等于4，再任取一个数，都会出现某两个数的差为4。随堂练习1．口袋里有70只球，其中20只是红球，20只是绿球，20只是黄球，其余的是白球和黑球。任意从中取出多少只球，可确保取出的球中至少有10只同色的球？解：把10只白球和黑球都取出来，其余再取红、绿、黄球各9只，最后再任取一只即可，所以至少取出10+3×9+1=38（只）球。2．一个口袋中有50个编上号码的相同的小球，其中编号为1、2、3、4、5的小球分别有2、6、10、12、20个，任意从口袋中取球，至少要取出多少个小球，才能保证取值至少有2个编号的小球各有7个？解：先取出编号为1、2的8个球，再取编号为5的20个球，和编号分别为3、4的球各6个，最后任取1个，就满足条件。所以至少取出8+20+2×6+1=41（个）球。3．17名同学参加一次考试，考试题是3道判断题（答案只有对于错），每名同学都在答题纸上依次写上了3道题目的答案。请问：至少有几名同学的答案是完全一样的？解：3道题，每题有2种答案，答案种类有2×2×2=8种，看做是8个抽屉，将17个苹果放入8个抽屉，根据抽屉原理，至少有3个苹果在某一抽屉中，即至少有3名同学的答案完全一样。4．如图：将2行5列的方格纸每一格染成黑色或白色，请说明：不管怎么染，总有两列的染色方式是一样的。解：对一列两个方格染色，有4种不同的方法，现在一共有5列，根据抽屉原理，不管怎样染色，总有两列染色的方式是一样的。5．从1、4、7、10、…、37、40这14个数中任取8个数，试证：其中至少有2个数的和是41.解：把这14个数分成7组(1、40)、(4、37)、(7、34)、(10、31)、(13、28)、(16、25)、(19、22)，组内每两个数的和都是41，从7组中取任8个数，至少有2个数在同一组内，这两个数的和是41.