高中数学奥赛辅导系列-抽屉原理

《高中数学奥赛辅导系列-抽屉原理》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、抽屉原理把八个苹果任意地放进七个抽屉里，不论怎样放，至少有一个抽屉放有两个或两个以上的苹果．抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则．它是组合数学中一个重要的原理．把它推广到一般情形有以下几种表现形式．形式一：证明：设把n＋1个元素分为n个集合A1，A2，…，An，用a1，a2，…，an表示这n个集合里相应的元素个数，需要证明至少存在某个ai大于或等于2（用反证法）假设结论不成立，即对每一个ai都有ai＜2，则因为ai是整数，应有ai≤1，于是有：a1

2、＋a2＋…＋an≤1＋1＋…＋1＝n＜n＋1这与题设矛盾．所以，至少有一个ai≥2，即必有一个集合中含有两个或两个以上的元素．形式二：设把n·m＋1个元素分为n个集合A1，A2，…，An，用a1，a2，…，an表示这n个集合里相应的元素个数，需要证明至少存在某个ai大于或等于m＋1．（用反证法）假设结论不成立，即对每一个ai都有ai＜m＋1，则因为ai是整数，应有ai≤m，于是有：a1＋a2＋…＋an≤m＋m＋…＋m＝n·mn个m＜n·m＋1这与题设相矛盾．所以，至少有存在一个ai≥m＋1高斯函数：对任意的实数x，[x]表示“不大

3、于x的最大整数”．例如：[3．5]＝3，[2．9]＝2，[－2．5]＝－3，[7]＝7，……一般地，我们有：[x]≤x＜[x]＋1形式三：证明：设把n个元素分为k个集合A1，A2，…，Ak，用a1，a2，…，ak表示这k个集合里相应的元素个数，需要证明至少存在某个ai大于或等于[n/k]．（用反证法）假设结论不成立，即对每一个ai都有ai＜[n/k]，于是有：a1＋a2＋…＋ak＜[n/k]+[n/k]+…+[n/k]k个[n/k]＝k·[n/k]≤k·(n/k)＝n∴a1＋a2＋…＋ak＜n这与题设相矛盾．所以，必有一个集合中元

4、素个数大于或等于[n/k]形式四：证明：设把q1＋q2＋…＋qn－n＋1个元素分为n个集合A1，A2，…，An，用a1，a2，…，an表示这n个集合里相应的元素个数，需要证明至少存在某个i，使得ai大于或等于qi．（用反证法）假设结论不成立，即对每一个ai都有ai＜qi，因为ai为整数，应有ai≤qi－1，于是有：a1＋a2＋…＋an≤q1＋q2＋…＋qn－n＜q1＋q2＋…＋qn－n＋1这与题设矛盾．所以，假设不成立，故必有一个i，在第i个集合中元素个数ai≥qi形式五：证明：（用反证法）将无穷多个元素分为有限个集合，假设这有限

5、个集合中的元素的个数都是有限个，则有限个有限数相加，所得的数必是有限数，这就与题设产生矛盾，所以，假设不成立，故必有一个集合含有无穷多个元素．例题１：400人中至少有两个人的生日相同．分析：生日从1月1日排到12月31日，共有366个不相同的生日，我们把366个不同的生日看作366个抽屉，400人视为400个苹果，由表现形式1可知，至少有两人在同一个抽屉里，所以这400人中有两人的生日相同．解：将一年中的366天视为366个抽屉，400个人看作400个苹果，由抽屉原理的表现形式1可以得知：至少有两人的生日相同．例题２：边长为1的正

6、方形中，任意放入9个点，求证这9个点中任取3个点组成的三角形中，至少有一个的面积不超过1/8．解：将边长为1的正方形等分成边长为的四个小正方形，视这四个正方形为抽屉，9个点任意放入这四个正方形中，据形式2，必有三点落入同一个正方形内．现特别取出这个正方形来加以讨论．EFGD把落在这个正方形中的三点记为D、E、F．通过这三点中的任意一点（如E）作平行线，如图可知：S△DEF＝S△DEG＋S△EFG≤×h＋＝＝例题3：任取5个整数，必然能够从中选出三个，使它们的和能够被3整除．证明：任意给一个整数，它被3除，余数可能为0，1，2，我们

7、把被3除余数为0，1，2的整数各归入类r０，r1，r2．至少有一类包含所给５个数中的至少两个．因此可能出现两种情况：　　1．某一类至少包含三个数；　　2．某两类各含两个数，第三类包含一个数．若是第一种情况，就在至少包含三个数的那一类中任取三数，其和一定能被3整除；若是第二种情况，在三类中各取一个数，其和也能被3整除．综上所述，原命题正确．例题4：九条直线中的每一条直线都将正方形分成面积比为2∶3的梯形，证明：这九条直线中至少有三条经过同一点．证明：如图，设PQ是一条这样的直线，作这两个梯形的中位线MN．∵这两个梯形的高相等，∴它们

8、的面积之比等于中位线长的比，即

9、MH

10、∶

11、NH

12、．∴点H有确定的位置．（它在正方形一对对边中点的连线上，并且

13、MH

14、∶

15、NH

16、＝2∶3）．由几何上的对称性，这种点共有四个，即，图中的H、J、I、K．已知的九条适合条件的分割直线中的每一条必须经过H、