鸽笼原理习题及解答.ppt

《鸽笼原理习题及解答.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章鸽笼原理习题及解答1、在一中学A班有50名学生，其中年龄最小的是15岁，最大的是18岁。证明这个班中至少有两个学生是同年同月生的。证：从15岁到18岁之间总共有48个月，将这48个月看成笼子，将50个学生看成鸽子，50>49=48+1，根据鸽笼原理，将50只鸽子放进48个笼子，必定至少有一个笼子放有2只及以上的鸽子，即这个班中至少有两个学生是同年同月生的。另证：50>49=4（13-1）+1故由鸽笼原理推论知：至少有一盒子中放有13个物体，即至少有13个人是同年生的；而13=12（2-1）+1，至少有一个盒子放入

2、2个物体。即至少有2个人是同月生的。所以这个班中至少有两个学生是同年同月生的。2、某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在a克到（a+0.1）克之间。现需要制成重量相差不超过0.005克的两铁盘来配制一架天平，问该工厂至少要生产多少铁盘才能得到一对符合要求得铁盘。解：将铁盘按重量分类，所有a克到a+0.005克的分为第一类，a+0.005克到a+0.01克的分为一类，a+0.01克到a+0.015克的又为一类，….，最后，a+0.095克到a+0.1克为一类，共计20类，由鸽笼原理知，若该工厂

3、生产21个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量差将不超过0.005克。3、在3*4的长方形内任意放置7个点，则其中至少有两点的距离。提示：分成6个1*2的小矩形，至少有一个小矩形中落入两点。4、在图中，每个方格着红色或蓝色，证明至少存在两列有相同的着色。解：每列着色的方式只可能有2*2=4种，现有5列，由鸽笼原理知，至少有二列着色方式相同。5、任给五个整数，则必能从中选出三个，使得它们的和能被3整除。解：设5个数为a1,a2,…,a5，又设ai被3除后所得余数为bi(i=1,….,5)，当然，0<

4、=bi<=2,于是可将0，1，2看做三个盒子，将b1,b2,….b5看做5个物体。于是可分为三种情况：a.若两个盒子是空的。b.有一个盒子是空的，c.三个盒子都不空。对于a:b1,b2,….b5放于同一盒子中，即这5个余数是相同的，任选三个，它们所对应的ai的和必能被3整除。对于b:b1,b2,….b5放于另外两盒子中，必有一盒子中至少有三个物体，即b1,b2,….b5中必有三个放入同一盒子中，选这三个对应的ai，其和必能被3整除。对于c:每个盒子中选一个，将其对应的ai相加，其和也必然能被3整除。6、一个学生打算用3

5、7天总共60学时自学一本书，他计划每天至少自学1学时，证明：无论他怎样安排自学时间表，必然存在相继的若干天，在这些天内其自学总时数恰好为13学时。解：设a1是第一天自学的时数，a2是第一，二天自学的时数的和，aj是第一，二，…，第j天自学时数的和，j=1,2,…..,37于是，序列a1，a2，….，a37是严格递增序列(每天至少一学时)，而且，a1>=1，a37=60于是序列a1+13，……,a37+13也是严格递增的序列且a37+13=73故74个数a1，……,a37,a1+13，……,a37+13都在1和73这73

6、个整数之间，由鸽笼原理知，这74个数中必有两个是相等的，由于a1，a2，….，a37中任何两数都不相等，故a1+13，……,a37+13中任何两个数也是不相等的，因此，一定存在两个数i,j使得ai=aj+13ai-aj=13因此，在j+1,j+2,…..,i这些天中，这个学生自学总时数恰好为13学时。7、已知n个正整数a1，a2，….，an,证明：在这n数中总是可以选择两个数使得这两个数的和或差能被n整除。解：每个正整数被n除所得的余数必是0，1，2，….,n-1中的一个，n个余数中如果有两个相同，则相对应的两个正整

7、数相减能被n整除。否则，n个余数为0，1，2，…..，n-1，则对应的余数为i与n-i的两个正整数，其和能被n整除。8、设a1，a2，….，an是1，2，…..,n的一个排列，证明：如果n是奇数，则乘积（a1-1）（a2-2）…..(an-n)是一个偶数。证明：因为n是奇数，故1，2，….,n中共有个奇数，故a1，a2，….，an，1，2，…..,n中共有=（n+1）个奇数,放入n个盒子中，必有两个在同一盒子中，其差为偶数，故该结论成立。另证：（反证法）假设（a1-1）（a2-2）…..(an-n)是一个奇数，则它的每

8、一项都是奇数，则与1，3，5，……n对应的a1，a3，a5，……，an都应为偶数（因为只有奇偶数对应相减才能得奇数），则这样的偶数共有个。而由于n是奇数，则在1，2，3，……n中共有个偶数，而a1，a2，a5，……，an为1，2，……n的一个排列，它的偶数个数应与1，2，3，……n的偶数个数相等，即也为个。这与假设推出的有个偶数矛