简单的抽屉原理.doc

练习52张扑克牌有红桃、黑桃、方块、梅花4种花色各13张，问：至少从中取出多少张牌，才能保证有花色相同的牌至少2张。至少从中取出几张牌，才能保证有花色相同的牌至少5张。至少从中取出几张牌，才能保证有4种花色的牌。至少从中取出几张牌，才能保证至少有2张梅花牌和3张红桃。至少从中取出几张牌，才能保证至少有2张牌的数码（或字母）相同。答案: 5张, 17张,40张,43张,14张. 例1 有5个小朋友，每人都从装有许多黑白围棋子的布袋中任意摸出3枚棋子.请你证明，这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。分析与解答 首先要确定3枚棋子的颜色可以有多少种不同的情况，可以有：3黑，2黑1白，1黑2白，3白共4种配组情况，看作4个抽屉.把每人的3枚棋作为一组当作一个苹果，因此共有5个苹果.把每人所拿3枚棋子按其颜色配组情况放入相应的抽屉.由于有5个苹果，比抽屉个数多，所以根据抽屉原理，至少有两个苹果在同一个抽屉里，也就是他们所拿棋子的颜色配组是一样的。例2 一副扑克牌(去掉两张王牌)，每人随意摸两张牌，至少有多少人才能保证他们当中一定有两人所摸两张牌的花色情况是相同的?分析与解答 扑克牌中有方块、梅花、黑桃、红桃4种花色，2张牌的花色可以有：2张方块，2张梅花，2张红桃，2张黑桃，1张方块1张梅花，1张方块1张黑桃，1张方块1张红桃，1张梅花1张黑桃，1张梅花1张红桃，1张黑桃1张红桃共计10种情况.把这10种花色配组看作10个抽屉，只要苹果的个数比抽屉的个数多1个就可以有题目所要的结果.所以至少有11个人。例3 证明：任取8个自然数，必有两个数的差是7的倍数。分析与解答 在与整除有关的问题中有这样的性质，如果两个整数a、b，它们除以自然数m的余数相同，那么它们的差a-b是m的倍数.根据这个性质，本题只需证明这8个自然数中有2个自然数，它们除以7的余数相同.我们可以把所有自然数按被7除所得的7种不同的余数0、1、2、3、4、5、6分成七类.也就是7个抽屉.任取8个自然数，根据抽屉原理，必有两个数在同一个抽屉中，也就是它们除以7的余数相同，因此这两个数的差一定是7的倍数。把所有整数按照除以某个自然数m的余数分为m类，叫做m的剩余类或同余类，用0，1，2，m-1表示.每一个类含有无穷多个数，例如1中含有1，m+1，2m+1，3m+1，.在研究与整除有关的问题时，常用剩余类作为抽屉.根据抽屉原理，可以证明：任意n+1个自然数中，总有两个自然数的差是n的倍数。在有些问题中，“抽屉”和“苹果”不是很明显的，需要精心制造“抽屉”和“苹果”.如何制造“抽屉”和“苹果”可能是很困难的，一方面需要认真地分析题目中的条件和问题，另一方面需要多做一些题积累经验。例4 从2、4、6、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34。分析与解答 我们用题目中的15个偶数制造8个抽屉：凡是抽屉中有两个数的，都具有一个共同的特点：这两个数的和是34。现从题目中的15个偶数中任取9个数，由抽屉原理(因为抽屉只有8个)，必有两个数在同一个抽屉中.由制造的抽屉的特点，这两个数的和是34。例5 从1、2、3、4、19、20这20个自然数中，至少任选几个数，就可以保证其中一定包括两个数，它们的差是12。分析与解答在这20个自然数中，差是12的有以下8对：20，8，19，7，18，6，17，5，16，4，15，3，14，2，13，1。另外还有4个不能配对的数9，10，11，12，共制成12个抽屉(每个括号看成一个抽屉).只要有两个数取自同一个抽屉，那么它们的差就等于12，根据抽屉原理至少任选13个数，即可办到(取12个数：从12个抽屉中各取一个数(例如取1，2，3，12)，那么这12个数中任意两个数的差必不等于12)。例6 从1到20这20个数中，任取11个数，必有两个数，其中一个数是另一个数的倍数。分析与解答 根据题目所要求证的问题，应考虑按照同一抽屉中，任意两数都具有倍数关系的原则制造抽屉.把这20个数按奇数及其倍数分成以下十组，看成10个抽屉(显然，它们具有上述性质)：1，2，4，8，16，3，6，12，5，10，20，7，14，9，18，11，13，15，17，19。从这10个数组的20个数中任取11个数，根据抽屉原理，至少有两个数取自同一个抽屉.由于凡在同一抽屉中的两个数都具有倍数关系，所以这两个数中，其中一个数一定是另一个数的倍数。例7 证明：在任取的5个自然数中，必有3个数，它们的和是3的倍数。分析与解答 按照被3除所得的余数，把全体自然数分成3个剩余类，即构成3个抽屉.如果任选的5个自然数中，至少有3个数在同一个抽屉，那么这3个数除以3得到相同的余数r，所以它们的和一定是3的倍数(3r被3整除)。如果每个抽屉至多有2个选