高中数学竞赛专题精讲23抽屉原理(含答案)

抽屉原理抽屉原理又叫重叠原则或鸽原则，抽屉原则有如下几种情形。

抽屉原则I 把1+n 件东西任意放入n 只抽屉里，那么至少有一个抽屉里有两件东西。

抽屉原则II 把m 件东西放入n 个抽屉里，那么至少有一个抽屉里至少有⎥⎦⎤⎢⎣⎡n m 件东西。

抽屉原则III 如果有无穷件东西，把它们放在有限多个抽屉里，那么至少有一个抽屉里含无穷件东西。

利用抽屉原则解题时，其关键是如何利用题中已知条件构造出与题设密切相关的“抽屉”，下面通过例子说明抽屉原则的应用。

例1．在边长为1的正方形内任意放置5个点，试证：其中必有两个点，它们之间的距离不大于22。

证明：将边长为1的正方形划分成如图所示的四个边长为21的小正方形，则每个小正方形中任意两点间的距离不大于22，据抽屉原理：5个点放入四个正方形中，其中至少有一个正方形中至少有2个点，则这两个点间的距离不大于22。

例2．证明：边长为1的的正三角形内任意放置5个点，其中必有两点，其距离不超过21。

证明：将边长为1的正三角形的各边中点连结起来，得到四个小正三角形，则每个小正三角形中任意两点间的距离不大于21，据抽屉原理：5个点放入4个小正三角形中，其中至少有一个小正三角形中至少有2个点，则这两个点间的距离不超过21。

例3．在边长为1的正方形中有任意九个点。

试证：在以这些为顶点的各个三角形中，至少有一个三角形，其面积不大于81。

证明：将边长为1的正方形划分为如图所示的4个441⨯的小长方形，9个点放入4个小长方形中，则必有一个长方形中放入了至少3个点，设为C B A ,,,则三角形ABC 的面积不大于过81，证明如下：A 作边的平行线交BC 于A '，则：C A A B A A ABC S S S '∆'∆∆+=8141121=⨯⨯≤。

例4．求证：任给五个整数，必能从中选出三个，使得它们的和能被3整除。

证明：因为任意一个整数被3除的余数只能是0，1，2，若任给的5个整数被3除的余数中0，1，2都出现，则余数为0，1，2的三个整数之和能被3整除；若5个数被3除的余数只出现0，1，2中的两个，则据抽屉原理知：必有3个整数的余数相同，而余数相同的3个数之和能被3整除。

抽屉原理一．抽屉原理的各种形式：抽屉原理1：n +1 个元素分成n 类，至少有1类中的元素不止1个．抽屉原理2：n ·m +1个元素分成n 类，至少有1类中的元素不止m +1个．即：k 个元素分成n 类，至少有1类中的元素不止⎣⎡⎦⎤k －1n +1个．(k ，n ∈N*)抽屉原理3：n 个数之和为m ，则其中必有一数≥m n ，也必有一数≤m n ．抽屉原理4 把一个无限集A 分成有限个集合的并集，即A i ⊂A ，且i ＝1∪nA i =A ，A i ∩A j =∅（i ，j =1，2，……，n ；i ≠j ）．则至少有一个A 的子集A k (1≤k ≤n )，它有无限多个元素．例1．把大小两个圆盘各划分成2n 个相等的扇形格，在每格都用黑、白两色之一涂色，使两盘总计，黑格与白格都各有2n 格．然后把两个圆盘的圆心固定于同一点，并让小盘在上成为一个转盘．试证：可将小盘转到某一适当位置，使两个圆盘上的格子对齐，并使二盘对应格子颜色不同的不少于n 对．证明：让小盘逐格转动，每次都记下颜色不同的格子对齐的数目，当转动了2n －1次后，小盘转动了一周，共记了2n 次．于是，小盘上每个格子都与大盘上的每个格子对齐一次．设小盘上有k 个黑格，2n －k 个白格，则大盘上有2n －k 个黑格，k 个白格．颜色不同的格子对齐的数目为k 2+(2n －k )2=4n 2+2k 2－4nk =2(k －n )2+2n 2≥2n 2．∴至少有一次转动对齐后，使二盘对应格子颜色不同的数目≥⎣⎡⎦⎤2n 2－12n +1＝n ．例2．从1，2，3，…，3n (n ≥2)这3n 个正整数中任意取出n +2个数，求证：其中必有两个数，其差大于n 而小于2n ．解：设取出的最大的数为k ，则把取出的数都加上 3n －k ，这样做不会影响它们之间的差．此时最大数为3n ，如果在取出的数中有一个在n 与2n 间(满足n+1≤x ≤2n －1的数)，则这数与3n 即为所求．若无任何数在此二数之间，则作抽屉(1，2n )，(2，2n +1)，(3，2n +2)，…，(n ，3n －1)，共n 个抽屉，除去3n 这个数外，还有n +1 个数，于是必有两个数落入同一抽屉，此二数即满足要求．例3．任取一个正实数a ，求证：在a ，2a ，3a ，…，(n －1)a 这n －1个数中，至少有一个数，它与最接近的整数之差不超过1n． 解：取这n －1个数的小数部分{a }，{2a }，{3a }，…，{(n －1)a }，则此n －1个数都在区间[0，1)内，把区间[0，1)分成n 个小区间，每个区间的长都为1n ：[0，1n )，[1n ，2n )，…，[n －1n，1)． 若此n －1个数中有某一个落入头尾两个区间之一，则原数即与最近的整数相差不超过1n．此n －1个数不可能没有任何一个落入头尾两个区间中，因若此n －1个数中没有任何一个落入头尾两个区间，则此n －1个数必落入了其余n －2 个区间内，于是必有两个数落入同一区间，设为{ta }，{sa }，(1≤t <s ≤n －1)，此时|(s －t )a |<1n，而0<s －t <n －1，令k =s －t ，于是必有{ka }落入头尾两个区间之一.故证．例4．M 是1985个不同的正整数的集合，M 中每个数的质因数都小于26，求证：从M 中一定可以选出四个不同的数，使它们的积等于一个完全四次方数．解：M 中的任一个数的质因子只能是2、3、5、7、11、13、17、19、23这9个数中的某些数．设a ∈M ，则按这9个质因子的指数为奇或为偶可把所有1985个数分成29=512类，由抽屉原理，任取513个M 中的数必有两个数属于同一类，于是可得(1985－511)÷2=737对数，每对数都属于同一类，于是，这737对数中，每对两数的乘积都是完全平方数，即每个质因子的指数都是偶数．即每个质因子的指数除以4后的余数都只能是0或2，再按这9个质因子的指数是0或2把这737个数分类，又可得512类，现在737个数放入这512类，必有两数同一类，此二数的乘积就是完全四次方数，而乘得此二数的原来4个数即为所求．例5．6个代表队共有1978名运动员，编上号码1，2，3，…，1978号，证明至少有一个运动员，他的号码等于其两个队友号码的和或者等于某一个队友号码的两倍．解：不妨设第1个代表队人数最多，则其人数≥[1978－16]+1=330人，设其中最大的号码为a 1，用a 1减其它329个号码，得到的差如果在此329个数中，则命题已成立．如果这329个差都不是第一个代表队的号码，那么不妨设其中有[329－15]+1=66个号码在第二个队中，同样设这66个号码最大的为b 1，用它减其余65个号码，差b 1－b i =(a 1－a t )－(a 1－a s )=a s －a t 如果在第一或第二个队的号码中，则命题已证，若不在，则此65个数必有[65－14]+1=17人同一队，设为第三队，又设其中最大者为c 1，用c 1减其余16个数，其差c 1－c i =(b 1－b i )－(b 1－b j )=b j －b i ，而b j －b i =(a 1－a t )－(a 1－a s )=a s －a t ，若在第一，二，三队的号码中，则命题可证，依此类推，若无，则[16－13]+1=6，[5－12]+1=3个，其差或是前面某队的号码，或是第6队的号码，问题总能成立．例6．S 是{1，2，3，…，1989}的一个子集，而且S 中任两个数的差不能是4或7，那么S 中最多可有多少个元素？(1989年第七届美国数学邀请赛)解：取前11个自然数1、2、3、4、5、6、7、8、9、10、11，排成一个圈：1、5、9、2、6、10、3、7、11、4、8．这样排好后，任意相邻两数都不能同时被取出，否则其差为4或7．而在这11个数中任取6数，就会在上面这个圈中取出了相邻的两个数，于是这11个数中，最多只能取出5个满足要求的数．例如，取1，3，4，6，9这五个数满足要求．1989=11×180+9，于是把这1989个数从1开始每连续11个数为一组，每组都取出5个数：11k +1，11k +3，11k +4，11k +6，11k +9(k =0，1，2，…，180)共取出181×5=905个数．即S 中最多可有905个元素．当取出的数超过905个时，总有某组数中取出的数超过6个，于是就会出现差为4或7的两个数．从而905为所求．例7．一位棋手参加11周（77天）的集训，每天至少下1盘棋，每周至多下12盘棋，证明这个棋手必在连续的几天内恰好下了21盘棋．解：这名棋手在77天内最多下了11×12=132盘棋．不妨记他从开始起第n 天共下了a n 盘棋，则有a 1<a 2<…<a 77．再取77个数：a 1+21，a 2+21，…，a 77+21，这样共得77×2=154个数．但这些数最大 不超过132+21=153． 于是必有两个数相等，这就是说，必有a i +21=a j (i <j )，即从第i +1天起，到第j 天这连续j －i 天中，这名棋手共下了21盘棋．例8．设有小数A =0.a 1a 2a 3…，如果a i +2是a i +1+a i 的个位数字(i =1，2，3，…)，求证：A 是有理数． 解：把a i ，a i +1组成一组：(a i ，a i +1)，(i =1，2，3，…)，则所有这些组只有以下100种可能的取法：(0，0)，(0，1)，(0，2)，…，(0，9)；(1，0)，(1，1)，(1，2)，…，(1，9)；…(9，0)，(9，1)，(9，2)，…，(9，9)．而取(a 1，a 2)，(a 2，a 3)，…，(a 100，a 101)，(a 101，a 102)这101组，于是必有两组相同，设为(a i ，a i+1)，(a i ，a j+1)，(i <j )．于是可得a i +2=a j +2，a i +3=a j +3，…，即A 为循环小数，故A 为有理数．例9．已知菲波拉契数列0，1，1，2，3，5，8，13，21，……(从第三项起，每项都等于它的前面两项的和)．试问，它的前100000001项中，是否有某一项的末四位数字全为0？(不算第1项)分析：添一项可以看作0000，考虑每一项的末四位数字，末四位数字共有104种，(从0000到9999)，而每项的末四位数字都是由其前面两项的末四位数字求和而得出．解：记每一项a i 的末四位数字为x i ，由于该数列的每一项都是其前两项的和，由于x i 有104种，x i+1也有104种，所以有序数对(x i ，x i+1)共有108种，但对于每一项都有一个有序数对(x i ，x i +1)与之对应：(x 0，x 1)，(x 1，x 2)，…，(x 100000000，x 100000001)，共有100000001个数对，从而必有两个数对完全一样，设(x i ，x i +1)与(x j ，x j +1)相同(i <j )．则有x i = x j ，x i +1= x j +1，由于x i -1= x i +1－ x i ， x j -1= x j +1－ x j ，故又有x i -1=x j －1，这样又有(x i -1，x i )=(x j -1，x j )，(x i -2，x i -1)=(x j -2，x j -1)，…，直至(x 0，x 1)与(x j -i ，x j -i +1)，即x j -i 与x 0相同，即a j -i 的末四位数字全是0．事实上该数列的7501项的末四位全是0．当两项相邻时的情况．例10．设m 、n 都是自然数，任给一个有nm +1项的数列(该数列各项互不相等)a 1，a 2，……，a nm +1证明可以从中选出m +1项，按原来的顺序组成递增数列或选出n +1项按原来的顺序组成递减数列． 说明：先举一个例说明：m =n =2，在一个5项的数列1，8，3，2，5中，可以选出一个3项的递增数列：1，3，5；但未能选出3项的递减数列来．解：对于mn +1项的数列a 1，a 2，…，a nm +1中每一项a i ，都可以从这项开始向后找出以该项为首项的项数最多的递增数列来，设这样的数列有x i 项，同时也能找出以该项为首项的项数最多的递减数列来，设这样的数列有y i 项，这样，对于每一项a i ，都有一对数（x i ，y i ）与之对应，这就得到了mn +1个数对（可以看成是mn +1个坐标）．如果所有x i 都不大于m ，所有y i 都不大于n ，即x i =1，2，…，m ；且y i =1，2，…，n ．于是这样的数对只能有nm 种，将每一种都看成是一个抽屉，但共有nm +1个数对，于是根据抽屉原理，必有2个数对落入同一抽屉．设为a i 与a j ，（i <j )，它们都对应着坐标(h ，k )，这表示从这两个数中的任一个开始，可以向后找出h 项组成递增数列，也可向后找出k 项组成递减数列．若a i <a j ，则从a j 起共有h 项组成递增数列，但加上a i 后应有h +1项，即与a i 对应的数不应为h ，同样若a i >a j ，也将引出矛盾．这说明必有某个x i 满足x i >m ，或者某个y i 满足y i >n 命题得证．例11．设实数x 1，x 2，x 3，…，x n 满足x 12+x 22+x 32+…+x n 2=1证明对每一个整数k ≥2，存在不全为0的整数a 1，a 2，…，a n ，满足|a i |≤k －1，(i =1，2，…，n )使|a 1x 1+a 2x 2+…+a n x n |≤(k －1)n k n －1． 证明：对于|a i |≤k －1，有(a 1x 1+a 2x 2+…+a n x n )2≤(a 12+a 22+…+a n 2)(x 12+x 22+…+x n 2)≤a 12+a 22+…+a n 2≤(k －1)2+（k －1)2+…+（k －1)2=n （k －1)2．所以， |a 1x 1+a 2x 2+…+a n x n |≤(k －1)n ． ⑴现在取{a 1，a 2，…，a n } {0，1，2，…，k －1}，则共可有k n 种取法，其每一种取法都满足⑴式．把区间[0，(k －1)n ]分成k n －1等份，每份长为(k －1)n k n －1．则k n 个数落入此区间内，必有二数落入同一份内．设为a '1x 1+a '2x 2+…+a 'n x n 与a "1x 1+a "2x 2+…+a "n x n ，则它们的差：(a '1－a "1)x 1+(a '2－a "2)x 2+…+(a 'n －a "n )x n = a 1x 1+a 2x 2+…+a n x n ．必满足|a i |≤k －1 (i =1，2，…，n )，且|a 1x 1+a 2x 2+…+a n x n |≤(k －1)n k n －1． 例12．一个棱柱以五边形A 1A 2A 3A 4A 5及B 1B 2B 3B 4B 5分别为上下底，这两个多边形的每一条边及线段A i B j (i ，j =1，2，3，4，5)均涂上红色与绿色，每个以棱柱的顶点为顶点，以涂色线段为边的三角形都有两边颜色不同．求证：上底与下底10条边的颜色相同．证明：首先证明此棱柱的上底面的棱颜色相同．否则必有两条相邻边颜色不同．不妨设A 1A 5为红，A 1A 2为绿．5条线段A 1B i (i =1，2，3，4，5)中必有3条同色．设有3条同为红色．这3条红色的线段中，总有两条是向相邻的两个顶点引出的，例如A 1B 1、A 1B 2都为红色．于是在△A 1B 1B 2中B 1B 2必为绿色．又在△A 1A 5B 1及△A 1A 5B 2中，A 5B 1及A 5B 2均必为绿色．这样就得△A 5B 1B 2全为绿色．矛盾．这说明上底面的5条棱同色．同理，下底面的5棱也同色． 下面再证明，上下底面10条棱颜色全同．反设上底面5条棱钱红，下底面5条棱全绿．由上证，A 1B 1、A 1B 2不能全红，但也不能全绿，故必一红一绿，设A 1B 1红，则A 1B 2绿，同理得，A 1B 3红，A 1B 4绿，A 1B 5红，此时，△A 1B 1B 5又出现上证情况．故得证．练习题 1． 在3×4(cm )的长方形中，放置6个点，试证：可以找到两点，其距离不超过 5 cm ．解 先把长方形分成5个区域(如图)，根据抽屉原理，必有两个点在同一个区域内，因而它们的距离不超过 5 cm ．2．⑴ 是否存在由10个正整数组成的集合A ，使A 的任一6元子集的元素和都不能被6整除？⑵ 对于任一由11个正整数组成的集合A ，证明：一定可以找到它的一个6元子集，其和能被6整除．⑴解：取A ={1，7，13，19，25，6，12，18，24，30}，则A 的任一六元子集的元素和都不能被6整除．⑵证明：对于任一元素都是正整数的11元集A ，总可以把这11个元配成5组，每组二个数的奇偶性相同，于是同组两数的和为偶数，这样就得到5个偶数和．这5个偶数mod 3后，如果有3个数mod 3互不同余，则此三数的和被3整除；如果这样的3个数不存在，即mod 3后只有至多两个剩余类，则其中必有1类中至少有3个数，则此三个数的和被3整除．于是取加得这三个数的原来的六个数，其和被6整除．3．把大小圆盘各划分成n 个相等的扇形格，各依次填上实数a 1、a 2、…、a n 及b 1、b 2、…、b n ，然后把把两圆盘圆心重叠做成转盘，试证：若a 1+a 2+…+a n <0，b 1+b 2+…+b n <0，则必可以使转盘转到某个适当位置，使大小圆盘对应扇形上两个数的乘积的和为一个正数．证明：让小盘逐格转动，每次都记下大小圆盘对应扇形上两个数的乘积的和，这样转过n 次后，共得B 1B 2B 3B 4B 5A 5A 4A 3A 2A 1B 1B 2B 3B 4B 5A 5A 4A 3A 2A1到了n 个和．由于大盘上的每个数字都要与小盘上的每个数字对应一次，故乘积a i b j (i ，j =1，2，3，…，n )在这n 个和中都出现一次且只出现一次，故这n 个和的总和=(a 1+a 2+…+a n )( b 1+b 2+…+b n )>0．∴这n 个和不可能都小于≤0，即其中至少有一个和为正数．4．已知自然数n (n >1)，用小于n 的自然数组成两个数组，每组内的数都各自两两不同，但两组间的数不一定全不同．证明：若两组数的总个数不小于n ，那么，一定可以从每一组中各选一个数，其和为n ．证明：设所组成的两个数组分别为A ={a 1、a 2、…、a k }及B ={b 1、b 2、…、b h }．其中各个a i 互不相同，各个b j 也互不相同．且k +h ≥n ．现取一数组C ={c 1，c 2，…，c h }，使c j =n －b j ，于是各c j 均为小于n 的正数，也互不相同．由于数组{ a 1、a 2、…、a k ，c 1，c 2，…，c h }的元素都为小于n 的正整数，但k +h ≥n ．从而必有某个c j =a i ，于是a i +b j =n ．5．给定13个不同的实数a 1，a 2，…，a 13，求证：存在两个实数a i ，a j ，(i ≠j )，满足0< a i －a j 1+a i a j <2－ 3 2+ 3． 证明：令tan θi =a i (－π2 <θi <π2，i =1，2，…，13)， 则有tan(θi －θj )= a i －a j 1+a i a j <2－ 3 2+ 3 =1－ 3 2 1+ 3 2 = 1－cos π6 1+cos π6 =tan π12 ． 故只要把这13个角按从大到小排列，并把区间(－π2 ，π2)分成12等分，则总有一个区间内落入了二个所给的角θi ，θj ，(θi >θj )，这两个角对应的实数即为所求．6．在[1，1000]内任取n 个互不相等的数a 1，a 2，…，a n ，为了总可以找到两个数a i ，a j (1≤i <j ≤n )，使得0<a i －a j <1+3∛____a i a j成立，试确定n 的最小值并证明之．解：设a i >a j ，且 0<∛__a i －∛__a j <1，于是，立方之，得0<a i －a j －3∛____a i a j (∛__a i －∛__a j )<1．∴ 0< a i －a j <1+3∛____a i a j (∛__a i －∛__a j )<1+∛____a i a j ．如果取n =10，可令a i =i 3，此时当i >j 时，a i －a j =i 3－j 3=(i －j )3+3ij (i －j )≥1+3ij =1+∛____a i a j 当取n =11，及区间[i 3，(i +1)3]，(i =1，2，…，9)．于是这11个数中必有两个数落入同一区间．由于这些区间共有10个端点，故这11个数不可能只取这9个区间的端点值i 3，于是必存在两个数落入同一区间且其中至少有一个数不是区间的端点．则此二数满足要求．7．证明：存在着绝对值都小于一百万，不全为0的三个整数a ，b ，c ，使|a + 2 b + 3 c |<10－11．证明：令A ={x ∈N |0≤x <106}．M ={ r +s 2 +t 3 | r ，s ，t ∈A }．d =(1 + 2 + 3 )·106．若x ∈M ，则x ∈[0，d ]．把区间[0，d ]分成1018－1个长度为l =d 1018－1 的子区间． 由抽屉原理，M 中1018个数中必有两个数同在某个子区间内，此二数之差<l <1071018－1 <10－11． 即此二数之差满足要求．8．我们称A 1，A 2，…，A n 为集合A 的一个n 划分，如果⑴ A 1∪A 2∪…∪A n =A ；⑵ A i ∩A j =Ø，1≤i <j ≤n ．求最小的正整数m ，使得对A ={1，2，…，m }的任意一个14划分A 1，A 2，…，A 14，一定存在某个集合A i (1≤i ≤14)，在A i 中有两个元素a ，b 满足b <a ≤43b ．(中国西部2001数学奥林匹克) 分析：14个集合相当于14个抽屉，取15个数，则必有一个抽屉中有两个数．若15个数中任意两个的数都满足b <a ≤43b ，则可求出最小的m 值． 解：取b ，b +1，b +2，…，b +14，共15个数．若b +14b ≤43，即得b ≤42．即至少取42+14=56个数，就可保证对A 的任一划分满足要求．当m ≥56时，取出其中42，43，…，56，共15个数，则根据抽屉原理，必有两数b ，a (42≤b <a ≤56)在同一划分中，由于1<a b ≤5642 = 43 ，即b <a ≤43b 成立． 若m <56．取A i ={a |a ≡i (mod 14)，0<a <56}，则对于A i 中任意两个数c ，d (c <d )，显然，c ≤42．故d c≥c +14c =1+14c >1+1442 =43，即此时不存在满足要求的划分．。

竞赛数学中的抽屉原理
简介：抽屉原理是一种统计原理，由四位数学家兼统计学家：约
翰·施特劳斯、古斯塔夫·海尔·西多夫、艾伦·艾尔法和安德烈·拉普
洛斯在20世纪30年代发现的。

它用于描述随机事件的分布情况。

抽屉原
理的主要思想是，如果一个事件存在多种可能性，则通常会出现几种情况，而这几种情况又可以等分地再被分割，其中每个情况的发生概率都是给定的。

具体而言，抽屉原理可以用来说明随机事件的几率是一致的，也就是说，在每一次随机事件中，每一种可能性的发生概率都是固定的。

抽屉原理也被称为拉普洛斯原理，它简单的说明是，如果一个给定的
随机事件有m种可能性，那么它的概率就是1/m，这意味着每一种可能性
的概率都是相等的。

该原理可以用来推断许多概率题的正确答案。

抽屉原理也可以用来解决概率问题。

比如，一个骰子有6种可能的数字，它们的概率就是1/6.根据抽屉原理，如果确定一个给定的随机事件，就可以确定它的概率。

抽屉原理也可以应用于其他领域，例如，当我们想要预测一支股票的
未来行情时，也可以用抽屉原理。

抽屉原则在解决存在性问题时，抽屉原则是一个强有力的工具.抽屉原则I将一个元素个数不少于"的集合划分为加个子集岀，短，…，九，则至少有一个子集A*伙w {1,2,…，加})其元素个数其中，［x］表示的最大整数.推论把一个"元集划分为加个子集(">%),则至少有一个集合含有至少两个元素.我们称这里的子集4,爲，…，4”,为加个“抽屉” •应用抽屉原则解题的关键是构造合适的抽屉，在不同的实际问题中抽屉的表现形式是不一样的；即使是对同一问题也可以从不同角度制造不同的抽屉.抽屉原则丫从加个互不相交的有限集中4，爲，…，4”,取出hw + 1个元素构成一个集合S ,则S中至少有k+1个元素属于某个A p(pe {1, 2,…，m}).抽屉原则II将一个元素不多于"的集合S划分为加个子集£,■■■, A m,则至少存在一个集合A伙w {1,2,…，，"})其元素数目抽屉原则III把一个无限集S划分为有限个子集A2, ■■■, A m,则至少存在一个集合A p(pe{l, 2, •••,加})仍为无限集.例1已知集合S={1, 2, 3,…，3町，"是正整数，T是S的子集，满足：对任意x, y , z^T (其中x, y , z可以相同)都有x+y + z^T ,求所有这种集合T 的元素个数的最大值.解析考虑S中那些较大的数.取T0={n + l, n + 2, ■■■, 3n］,显然，其中任三数之和大于3”.故max|T|> |7^| = 2n .另一方面，作三元子集列A^={n , 2n, 3n]={k, 2n — k, 2n + k] , k = 1,2, •••, n — 1 ,Ak则S=U4,对于s的任一个2〃 + 1元子集尸，必包含有某个A・若观u尸，则其中有元素3n = n + n + n；若某个4 c T', ke{l,2, ■■■, n-1},则其中有元素In + k -k + k + (2n-k).于是max|T| < 2n + l.所以，max卩| = 2".抽屉原则应用过程中的抽屉制造实质就是对问题涉及的某些对象进行分类. 因此，首先应弄清楚对哪些对象分类，分多少类，按什么规则分.例2从1, 2,…，3839中任意选1996个数，证明：一定存在两个数的差恰好等于96.解析按模96的余数0,1, 2,…，95,把整数分类为96类.现有1996个数，且1996 = 96x20 + 76,故由抽屉原则可知，在这1996个数中必有21个数属于同一类，即这21个数中任意两数的差都是96的倍数.如果这21个数中，每两个数之差都不是96,那么这样的最小的21个数是：- 0x96 + r , a2 = 2x96 + r , a3 - 4x96 + r ,…，axo21 =2x20x96 + r>3840>3839 (0 < r < 95),这与已知条件不符.所以，选出的1996个数中一定存在两数之差恰好等于96.例3 —位棋手参加11周(77天)的集训，每天至少下一盘棋，每周至多下12盘棋•证明：这位棋手必定在连续的几天内恰好下21盘棋.解析用S,表示这位棋手在第1天至第7天(包括第7天在内)所下的棋的总盘数(1</<77).由于棋手每天至少下一盘棋，所以S] < S°< ••- < S77.又由于棋手每周至多下12盘棋，所以S77 <12x11 = 132.要证明存在7, j,1<;</<77,使S i-S J =21,这只需证明在» S2)…，S77, 5+21, …，S77+2I中有两项相同即可.事实上，上面的77x2 = 154个数中最小的,1,最大的=S77+21<132+21=153. 由抽屉原则I：必有两数相同.例4试卷上共有4道选择题，每题有3个可供选择的答案.一群学生参加考试，结果是对于其中任何3人，都有一个题目的答案互不相同，问参加考试的学生最多有多少人？解析设每题的3个选择支为a,b,c.如果参加考试学生有10人，则由抽屉原则II知，第一题答案分别为a,b,c的三组学生中，必有一组不超过3人，10-1 + 1 = 2,去掉这组学生，余下的学生中选出7人，则他们对第一题的答案只有两种.对于 这7人关于第二题应用抽屉原则II 知其中必可选出5人，他们关于前两题的答案 都只有两种可能，对于这5人关于第三题应用抽屉原则II,又知可选出4人，关 于第四题应用抽屉原则II,知必可选出3人，他们关于4个题目的答案都只有两 种，这不满足题中的要求.可见，所求的最多人数不超过9.另一方面，如果9 个人的答案如下表所示，则每3人都至少有一个问题的答案互不相同.例5设⑷，a 2,…，a”，…是任意一个具有性质a k < a k+l (k > 1)的正整数的无 穷序列.求证：这个数列中有无穷多个％可以表示为a ,n = xa P + W?，其中，p , q, x, y 是适当的正整数，且p 丰q .解析 在给定的数列中任意取一项仙，因为陶是正整数，把全体正整数按 mod 仙的剩余类分类.由于正整数a ；, a 2, ■■■, a n , ■■-有无穷多个，所以由抽屉原 则III,上述陶个分类中至少有一类含有数列中的无穷多项.再由最小数原理， 这无穷多个项中一定有一个最小的项伟，于是对这个剩余类中的其他任意一项 %都有4” 三 a/moda/,且 a m > a p .所以a m =a p +a q y(y 为某个正整数).取x = l,即有a m = xa p + ya q .例6在不超过91的非零自然数中任意取10个数，证明：这10个数中一定 有两个数的比值在区间§冷内.解析 不超过91正整数共91个，要把这些数分成兀组，使X 可取的最大值是9.现将1, 2, ■■■, 90, 91这91个数分为9组:{1}, {2,3}, {4,5,6}, {7,8,9,10},{11, 12,…，16}, {17, 18,…，25}, {26, 27,…，39},{40, 41,…，60}, {61, 62, ■■■, 91}.这9个组的每个组中任意两数之比P适合-<k<-.由抽屉原则F,从这9个组 3 2中任意取10个数必有两数取自同一组，其比值在-内.L3 2」在这里显然抽屉的个数不能多于9个，分类的规则是使每个抽屉中的任意两数之比落在区间-内.3 2例7对一个5X"的格阵用红、蓝两色进行染色.如果对任意一种染色方案总可找到由3行3列相交出的同色的9个方格，求"的最小值.解析对于每一例，我们考虑相对“均匀”的染法：将其中3个方格染上一种颜色，其余2个方格染上另一种颜色.这样的不同染色方法共有2C；=20种.这提示我们，将5x40格阵的前20列用上述20种不同染法染色，后20列也依前20列的方法对应进行染色.这样的话，无法找到满足题意的同色的3x3格阵.故"至少应为41.如果还是上述“均匀”的染法，那么只要再多一列，即“ =41,就必定出现满足题意的3x3的同色格阵.如果不全是“均匀”的染法，是否"=41还能出现3x3的同色格阵呢？我们得换一个思路，若"=41,因每列红、蓝格数必不相等，所以，至少有21列，每列染某种颜色的格数大于染另一种颜色的格数.不妨设至少有21列每列的红格数大于蓝格数，即每列至少有3个红格.可退一步(?)设这21列每列恰好有3个红格，则对应的染色方法有C；=10种.由抽屉原则知21列中必有3列染法相同，这三列的红色方格即构成3x3的同色格阵.故"的最小值为41.例8在区间［1, 1000］里任意取"个不同的数a,, a2,…，a”，为了总可找到两个数a i, a j (i 丰j , l<i, j < n),使得成立，确定"的最小值，并证明之.解析不等式0<《-勺<1 + 3珈玄成立的一个充分条件是令丽W，疤=4,则问题转化为在区间[1, 10]里任意取"个不同的数乙,…，a'n,从中总存在两数/, a] (i壬j , l<i, j < n)使得将区间[1, 10]分成长度小于1且互不重叠的区间，则至少要分出10个这样的区间，如[1, 2), [2, 3), ■■■, [9, 9.5), [9.5, 10].由抽屉原则T 知,z/ = ll 即可.这说明所求"的最小值不超过11.当zz = 10 时，令^G? = z(z=l, 2, ■■■, 10), i>j,那么«, -a, = O'-J)3 + 3zj(z-；)>1 + 3ij , 不适合条件.故所求的“为11.例9 一个圆内有6000个点，其中任意三点都不共线.(1)能否用直线把这个圆分成2000块，使每块恰含有3个点，如何分？(2)若每块中三点满足：两两之间的距离皆为整数且不超过9,则以每块中的三点为顶点作三角形，这些三角形中大小完全一样的三角形至少有多少个？解析(1)圆内6000个点可确定<価条直线，因^^爲.是个有限的数，所以一定存在圆的一条切线，使它不平行于这C爲。

抽屉原理把八个苹果任意地放进七个抽屉里，不论怎样放，至少有一个抽屉放有两个或两个以上的苹果。

抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此,也称为狄利克雷原则.它是组合数学中一个重要的原理。

把它推广到一般情形有以下几种表现形式。

形式一：证明：设把n＋1个元素分为n个集合A1，A2，…，A n，用a1，a2，…,a n 表示这n个集合里相应的元素个数，需要证明至少存在某个a i大于或等于2（用反证法）假设结论不成立，即对每一个a i都有a i＜2，则因为a i是整数，应有a i≤1，于是有：a1＋a2＋…＋a n≤1＋1＋…＋1＝n＜n＋1这与题设矛盾。

所以，至少有一个a i≥2，即必有一个集合中含有两个或两个以上的元素.形式二：设把n·m＋1个元素分为n个集合A1,A2，…，A n,用a1，a2，…，a n表示这n个集合里相应的元素个数,需要证明至少存在某个a i大于或等于m＋1.（用反证法）假设结论不成立,即对每一个a i都有a i＜m＋1，则因为a i是整数,应有a i≤m，于是有:a1＋a2＋…＋a n≤m＋m＋…＋m＝n·mn个m＜n·m＋1这与题设相矛盾。

所以，至少有存在一个a i≥m＋1高斯函数:对任意的实数x，［x］表示“不大于x的最大整数”.例如:[3.5]＝3，[2.9]＝2，［－2。

5]＝－3，[7］＝7，……一般地，我们有:[x]≤x＜[x］＋1形式三:证明：设把n个元素分为k个集合A1，A2,…，A k,用a1，a2，…，a k 表示这k个集合里相应的元素个数,需要证明至少存在某个a i大于或等于[n/k].(用反证法）假设结论不成立,即对每一个a i都有a i＜［n/k]，于是有：a1＋a2＋…＋a k＜［n/k]+[n/k］+…+［n/k]k个[n/k］＝k·[n/k］≤k·（n/k)＝n∴a1＋a2＋…＋a k＜n这与题设相矛盾.所以，必有一个集合中元素个数大于或等于[n/k]形式四：证明：设把q1＋q2＋…＋q n－n＋1个元素分为n个集合A1，A2，…,A n，用a1,a2，…,a n表示这n个集合里相应的元素个数，需要证明至少存在某个i,使得a i大于或等于q i。

浅谈抽屉原理在高中数学竞赛中的运用抽屉原理是数学中一个重要的基本原理，在高中数学竞赛中也有广泛的运用。

抽屉原理的核心思想是，如果有n+1个物体放进n个抽屉，那么至少有一个抽屉中会放置至少两个物体。

这个原理看似简单，却能在许多问题中提供有力的解决方法。

下面就来浅谈抽屉原理在高中数学竞赛中的运用。

在数学竞赛中，抽屉原理可以应用于排除法，数目合理性的讨论，以及不等式证明等方面。

以下将通过具体例题来介绍抽屉原理的运用。

首先考虑一个常见的例题：证明10个正整数中，至少有两个数的差是9的倍数。

我们可以将这10个整数表示为(1+9k)，其中k为整数。

每个整数除以9的余数只能是0、1、2、3、4、5、6、7、8中的一个，共有9个不同的取值。

而我们要放置10个整数，根据抽屉原理，至少有两个整数的余数相同，这样它们相减的结果就是9的倍数。

另一个例子是，证明每个由11个正整数互不相同的数组成的集合中，存在一个子集，其中的元素之和是11的倍数。

我们将这11个数分别除以11，得到的余数只能是0、1、2、3、4、5、6、7、8、9、10这11个数字。

根据抽屉原理，至少有两个数的余数相同，这样它们之差就是11的倍数。

将这两个数从原始集合中去掉，剩下的数仍然可以被11整除。

通过反复应用这个过程，最后这个集合中就会存在元素之和是11的倍数的子集。

在不等式证明中，抽屉原理也有一定的应用。

例如，对于任意的n个整数$a_1, a_2, ..., a_n$，证明存在两个整数$a_i$和$a_j$，它们满足$1 \leq ，i-j， \leq [\sqrt{n}]$，其中$[\sqrt{n}]$表示不超过$\sqrt{n}$的最大整数。

可以将这个问题看作是将整数坐标轴上的n个点分成若干组，每组的两个点的横坐标之差不大于$[\sqrt{n}]$。

将第i个点记作$(i, a_i)$，按$x$轴坐标分组，每组包含同一个横坐标的所有点。

可以发现，如果横坐标的差小于等于$[\sqrt{n}]$，那么这两个点的纵坐标差的绝对值不会超过$[\sqrt{n}]$。

抽屉原理在高中数学竞赛中的应用抽屉原理（也被称为鸽巢原理或鸽笼原理）是组合数学中的重要原理之一，它在高中数学竞赛中有广泛的应用。

该原理由德国数学家戈亨·迈尔发现，意味着如果把若干个物体放进比物体数量少的抽屉里，那么至少有一个抽屉里会放置多于一个物体。

在数学竞赛中，抽屉原理通常用于求解问题的存在性、最大值或最小值。

下面将列举一些抽屉原理在高中数学竞赛中的应用：1.选择问题在一组元素中进行选择时，抽屉原理可用于判断一些特定选择在一些特定情况下是否存在。

例如，当把10个整数放入1到9的九个抽屉中时，至少会存在一个抽屉里放置了两个或多个整数。

2.重复元素抽屉原理对于判断是否存在重复元素在高中数学竞赛中也非常有用。

例如，考虑将10个整数放入1到9的九个抽屉中，如果选择了11个整数，那么肯定会有至少两个整数放在同一个抽屉里。

3.处理奇偶数在一些问题中，抽屉原理被用来分析奇偶性。

例如，如果有n个奇数和n-1个偶数，那么至少有一对奇数之间的和是偶数。

4.关于整数环抽屉原理可以用于处理整数环问题，即把n个数围绕成一个环，计算一些数的相邻差的和。

通过运用抽屉原理，可以证明在这种情况下至少存在一个差为n或n-15.斯特灵数斯特灵数用于计算n个物体可以分成k个非空循环排列的方法数。

通过应用抽屉原理，我们可以证明当n<k时，斯特灵数为0；当n>=k时，斯特灵数为(n-1)C(k-1)+(n-1)Ck。

6.牛顿插值法牛顿插值法用于通过已知的数据点预测未知数据点的值。

通过利用抽屉原理，我们可以得到不同次数的牛顿多项式的性质以及它们的系数。

7.合理打枪问题合理打枪问题是一个经典的用抽屉原理解决的问题。

它以强化学习和统计决策理论为基础，涉及到多个玩家参与的射击游戏。

抽屉原理在这个问题中用来证明每个玩家在一定条件下至少会被命中。

总而言之，抽屉原理在高中数学竞赛中有着广泛的应用。

它不仅可以用于解决问题的存在性、最大值或最小值等问题，还可以用于处理选择问题、重复元素、奇偶数、整数环、斯特灵数、牛顿插值法等各种数学问题。

第九讲 抽屉原理一、 知识点：1． 把27个苹果放进4个抽屉中，能否使每个抽屉中苹果数均小于等于6？那么至少有一个抽屉中的苹果数大于等于几？2． 把25个苹果放进5个抽屉中，能否使每个抽屉中苹果数均小于等于4？那么至少有一个抽屉中的苹果数大于等于几？上述两个结论你是如何计算出来的？★规律：用苹果数除以抽屉数，若余数不为零，则“答案”为商加1，若余数为零，则“答案”为商。

★抽屉原则一：把n 个以上的苹果放到n 个抽屉中，无论怎样放，一定能找到一个抽屉，它里面至少有两个苹果。

★抽屉原则二：把多于m ×n 个苹果放到n 个抽屉中,无论怎样放,一定能找到一个抽屉,它里面至少有(m +1)个苹果。

二、 基础知识训练（再蓝皮书）1、 把98个苹果放到10个抽屉中， 无论怎么放， 我们一定能找到一个含苹果最多的抽屉，它里面至少含有 个苹果。

2、1000只鸽子飞进50个巢，无论怎么飞，我们一定能找到一个含鸽子最多的巢， 它里面至少含有 只鸽子。

3、从8个抽屉中拿出17个苹果，无论怎么拿。

我们一定能找到一个拿苹果最多的 抽屉，从它里面至少拿出了 个苹果。

4、从 个抽屉中（填最大数）拿出25个苹果，才能保证一定能找到一个抽屉， 从它当中至少拿了7个苹果。

三、 思路与方法：在抽屉原理问题，难在有些题目抽屉没有直接给出，要求我们自己根据题意去造抽屉，但我们也不要为此感到困难，往往在题目有一句关键的话，告诉我们抽屉的性质，我们可以根据此性质来构造抽屉即可。

训 练 题1． 六（1）班有49名学生。

数学王老师了解到在期中考试中该班英文成绩除3人外均在86分以上后就说：“我可以断定，本班同学至少有4人成绩相同。

”请问王老师说的对吗？为什么？2． 从100,,3,2,1 这100个数中任意挑选出51个数来，证明在这51个数中，一定：（1）有2个数互质； （2）有两个数的差为50；3． 圆周上有2000个点，在其上任意地标上1999,,2,1,0 （每一点只标一个数，不同的点标上不同的数）。

上海奥数精讲第讲讲义抽屉原理一、引言抽屉原理是奥林匹亚数学竞赛中一个常见的原理，被广泛应用于数学中的排列组合、鸽巢原理等问题的解答中。

本课将通过抽屉原理的解释和示例来帮助学生更好地理解这个概念，并能应用于相关的问题中。

二、抽屉原理的概念1.定义：如果有n个物体放入m个抽屉中，且n>m，则至少有一个抽屉中至少有两个物体。

2.解释：抽屉原理可以理解为，当物体数量多于抽屉数量时，不可能每个抽屉都只有一个物体，至少有一个抽屉里会有多个物体。

三、抽屉原理的证明1.假设有n个物体放入m个抽屉中，且n>m。

2.假设每个抽屉中最多只能放一个物体，即每个抽屉里放的物体数最多为13.总物体数应不超过总抽屉数，即n≤m。

4.由于n≤m，而且n>m，所以不可能每个抽屉都只有一个物体，即至少有一个抽屉中有多个物体。

四、抽屉原理的应用1.应用于排列组合问题：例1：有7只鸽子分别关在8个笼子里，那么至少有一个笼子中有多于一只鸽子。

解析：将7只鸽子依次放入8个笼子里，根据抽屉原理，至少应有一个笼子中有多于一只鸽子。

例2：将10颗彩球放入3个盒子中，那么至少有一个盒子中有多于3颗彩球。

解析：将10颗彩球依次放入3个盒子中，根据抽屉原理，至少应有一个盒子中有多于3颗彩球。

2.应用于集合问题：例3：设有10个整数，它们的平均数与整数部分之和的整数部分相等，证明至少有两个数的小数部分相减的绝对值小于等于0.1解析：设这10个整数的平均数为x，则整数部分之和的整数部分为10x，根据题目中的条件可得10x-10x<0.1，即1<0.1，这是一个矛盾的结论。

根据抽屉原理，至少有两个数的小数部分相减的绝对值小于等于0.1例4：现有9个整数，它们的平均数与整数部分之和的整数部分相等，证明至少有两个数的小数部分相减的绝对值小于等于0.098解析：设这9个整数的平均数为x，则整数部分之和的整数部分为9x，根据题目中的条件可得9x-9x<0.098，即0<0.098，这是一个矛盾的结论。

组合一、方法与例题1．抽屉原理。

例1 设整数n ≥4,a 1,a 2,…,a n 是区间(0,2n)内n 个不同的整数，证明：存在集合{a 1,a 2,…,a n }的一个子集，它的所有元素之和能被2n 整除。

[证明] （1）若n ∉{a 1,a 2,…,a n },则n 个不同的数属于n-1个集合{1,2n-1}，{2,2n-2},…,{n-1,n+1}。

由抽屉原理知其中必存在两个数a i ,a j (i ≠j)属于同一集合，从而a i +a j =2n 被2n 整除；（2）若n ∈{a 1,a 2,…,a n }，不妨设a n =n ，从a 1,a 2,…,a n -1(n-1≥3)中任意取3个数a i , a j , a k (a i ,<a j < a k )，则a j -a i 与a k -a i 中至少有一个不被n 整除，否则a k -a i =(a k -a j )+(a j -a i )≥2n ，这与a k ∈(0,2n)矛盾，故a 1,a 2,…,a n-1中必有两个数之差不被n 整除；不妨设a 1与a 2之差(a 2-a 1>0)不被n 整除，考虑n 个数a 1,a 2,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a n-1。

ⅰ）若这n 个数中有一个被n 整除，设此数等于k n ，若k 为偶数，则结论成立；若k 为奇数，则加上a n =n 知结论成立。

ⅱ）若这n 个数中没有一个被n 整除，则它们除以n 的余数只能取1,2,…,n-1这n-1个值，由抽屉原理知其中必有两个数除以n 的余数相同，它们之差被n 整除，而a 2-a 1不被n 整除，故这个差必为a i , a j , a k-1中若干个数之和，同ⅰ）可知结论成立。

2．极端原理。

例2 在n ×n 的方格表的每个小方格内写有一个非负整数，并且在某一行和某一列的交叉点处如果写有0，那么该行与该列所填的所有数之和不小于n 。