鸽巢原理例题

《鸽巢原理例题》由会员分享，可在线阅读，更多相关《鸽巢原理例题（7页珍藏版）》请在金锄头文库上搜索。

1、鸽巢原理例题鸽巢原理例题证明1,2n中任意n+1个不同的数中至少有一对数互质设这n+1数为a1a2an+1,令bi=ai+1 (i=1,2,n)。显然，b1b2bn=2n,a1,an+1,b1,bn这2n+1个数中必有二数相等，即存在bi与ai+1相等，即bi=ai+1=ai+1,而ai与ai+1是互质的。另证：2n数中任意间隔取数，最多能取到n个，若再多取一个，必然出现两数相邻情况，此二数必互素。一人以11周时间准备考试，他决定每天至少做一道题，但每周不多于12题。证明：存在连续的若干天，在这些天时他恰好做了21题。改为更少的题数如何？改为22题如何？令ai表示从第一天到第i天所做的题数之和

2、。因为每天至少做一题，有：a1a2a77=12*11=132。考虑序列:a1+21,a2+21,a77+21(=153).两个序列共有154个数，而aiaj(当ij时), 同理，ai+21aj+21(当ij时), 所以，必有某个aj=ai+21,即从第i+1天到第j天共做了21题。原命题改为小于21题，显然是成立的。续：22题的情况若存在某一周没有做满若存在某一周没有做满12题，则题，则a77+22154, ,使得这使得这154个数最多到个数最多到153, ,从而仍有从而仍有aj=ai+22; ;若每周都做满若每周都做满1212题，那么题，那么a1,a2,a77, a1+22, a2+22,

3、,a77+22这这154个数恰在个数恰在1154之间。之间。若不存在若不存在i,j使得使得aj=ai+22, ,则它们取值遍历则它们取值遍历1,2,154。即。即有有a1=1,a2=2,a7=7,a22=22。那么，他在第一周里只做了那么，他在第一周里只做了7题，与每周做满题，与每周做满12题假设题假设矛盾。矛盾。所以，必存在连续的若干天，他恰好做了所以，必存在连续的若干天，他恰好做了22题。题。设a1,a2,an是1,n的一个排列，证明，当n是奇数时，(a1-1)(a2-2)(an-n)是一偶数。证明：只须证明上述因子中有一个是偶数即可。因为只要有一个因子是偶数，则积必为偶数。n是奇数时，1

4、n中有(n+1)/2个奇数， (n-1)/2个偶数。从而，a1,a3,an中至少有一个是奇数,设为a2i+1这样以来，(a2i+1-(2i+1)为偶数。乘积为偶数。证毕。思考题1. 1.一个一个1*11*1的方格里任选的方格里任选5 5个点，则必存在两点，其个点，则必存在两点，其距离距离2/2.2/2.2. 2.空间直角坐标系中，我们把空间直角坐标系中，我们把( (x,y,zx,y,z) )坐标均为整数坐标均为整数的点简称为格点，证明，任意的点简称为格点，证明，任意9 9个格点中，必存个格点中，必存在两点，其连线的中点亦是格点。在两点，其连线的中点亦是格点。3. 3.设西工大在北京的办事处有设西工大在北京的办事处有9090间房间。每次总间房间。每次总是有是有100100人中的人中的9090人到那里出差，试设计一种配人到那里出差，试设计一种配钥匙方案，保证这钥匙方案，保证这100100人中的任意人中的任意9090人到北京出人到北京出差时，至少有一间房间可让其使用。试问在这差时，至少有一间房间可让其使用。试问在这一方案下，共配了多少把钥匙？一方案下，共配了多少把钥匙？结束语结束语谢谢大家聆听！谢谢大家聆听！7