鸽笼原理习题及解答

鸽笼原理习题及解答

ID:39818021

大小:238.00 KB

页数:17页

时间:2019-07-12

鸽笼原理习题及解答_第1页
鸽笼原理习题及解答_第2页
鸽笼原理习题及解答_第3页
鸽笼原理习题及解答_第4页
鸽笼原理习题及解答_第5页
资源描述:

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

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类,由鸽笼原理知,若该工厂生产21个铁盘,那么就能得知有两个铁盘属于同一类

3、,因而它们之间的重量差将不超过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<=bi<=2,于是可将0,1,2看做三个盒子,将b1,b2,….b5看做

4、5个物体。于是可分为三种情况:a.若两个盒子是空的。b.有一个盒子是空的,c.三个盒子都不空。对于a:b1,b2,….b5放于同一盒子中,即这5个余数是相同的,任选三个,它们所对应的ai的和必能被3整除。对于b:b1,b2,….b5放于另外两盒子中,必有一盒子中至少有三个物体,即b1,b2,….b5中必有三个放入同一盒子中,选这三个对应的ai,其和必能被3整除。对于c:每个盒子中选一个,将其对应的ai相加,其和也必然能被3整除。6、一个学生打算用37天总共60学时自学一本书,他计划每天至少自学1学时,证明:无论他怎样安排自学时间表,必然存在相

5、继的若干天,在这些天内其自学总时数恰好为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个整数之间,由鸽笼原理知,这74个数中必有两个是相等的,由于a1,a2,….,a37中任何两数都不相等,故a1+13,…

6、…,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个余数中如果有两个相同,则相对应的两个正整数相减能被n整除。否则,n个余数为0,1,2,…..,n-1,则对应的余数为i与n-i的两个正整数,其和能被n整除。8、设a1,a2,….,an

7、是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)是一个奇数,则它的每一项都是奇数,则与1,3,5,……n对应的a1,a3,a5,……,an都应为偶数(因为只有奇偶数对应相减才能得奇数),则这样的偶数共有个。而由于n是奇数,则在1,2,3

8、,……n中共有个偶数,而a1,a2,a5,……,an为1,2,……n的一个排列,它的偶数个数应与1,2,3,……n的偶数个数相等,即也为个。这与假设推出的有个偶数矛

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。