竞赛专题培训课件：抽屉原理

《竞赛专题培训课件：抽屉原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、≤1，于是有：a1＋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,[

3、x]表示“不大于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可以得

6、知：至少有两人的生日相同.鹅娅尽損鹌惨歷茏鴛賴。例题２：边长为1的正方形中，任意放入9个点，求证这9个点中任取3个点组成的三角形中，至少有一个的面积不超过1/8.籟丛妈羥为贍偾蛏练淨。解：将边长为1的正方形等分成边长为的四个小正方形，视这四个正方形为抽屉，9个点任意放入这四个正方形中，据形式2，必有三点落入同一个正方形内.现特别取出这个正方形来加以讨论.預頌圣鉉儐歲龈讶骅籴。把落在这个正方形中的三点记为D、E、F.通过这三点中的任意一点（如E）作平行线，如图可知：S△DEF＝S△DEG＋S△EFG≤×h＋＝＝GFCDE例题３：任取5个整数，必然能够从中选出

7、三个，使它们的和能够被3整除.证明：任意给一个整数，它被3除，余数可能为0，1，2，我们把被3除余数为0，1，2的整数各归入类r０，r1，r2.至少有一类包含所给５个数中的至少两个.因此可能出现两种情况：渗釤呛俨匀谔鱉调硯錦。　　１°.某一类至少包含三个数；　　２°.某两类各含两个数，第三类包含一个数.若是第一种情况，就在至少包含三个数的那一类中任取三数，其和一定能被3整除；若是第二种情况，在三类中各取一个数，其和也能被3整除.综上所述，原命题正确.例题４：九条直线中的每一条直线都将正方形分成面积比为2∶3的梯形，证明：这九条直线中至少有三条经过同一点.铙

8、誅卧泻噦圣骋贶頂廡。证明：如图，设PQ是一条这样的直线，作这两个梯